{
front++;
}
if (front==rear)
break;
if(rear%2==0)
Q[front]->lchild=S; //新结点为父结点的左孩子else
{
Q[front]->rchild=S; //新结点为父结点的右孩子
front++;
}
}
cin>>ch;
}
return root;
}
（2）前序遍历
伪代码：
1.设置递归边界条件：if root==null则停止递归
2．打印起始节点的值，并先后在左子数右子数上递归调用打印函数
if(root==NULL) return;
else{
cout<data<<" ";
PreOrder(root->lchild);
PreOrder(root->rchild);
}
时间复杂度：O(n)
（3）中序遍历
伪代码：
1.设置递归边界条件：if root==null则停止递归
2.递归遍历左子树
3.打印根节点数据域内容
4.递归遍历右子树
if (root==NULL) return; //递归调用的结束条件
else{
InOrder(root->lchild); //中序递归遍历root的
左子树
cout<data<<" "; //访问根结点的数据域
InOrder(root->rchild); //中序递归遍历root的
右子树
}
时间复杂度：O(n)
（4）后序遍历
伪代码：
1.设置递归边界条件：if root==null则停止递归
2.递归遍历左子树
3.递归遍历右子树
4.访问根结点数据域
if (root==NULL) return; //递归调用的结
束条件
else{
PostOrder(root->lchild); //后序递归遍历
root的左子树
PostOrder(root->rchild); //后序递归遍历
root的右子树
cout<data<<" "; //访问根结点的
数据域
}
时间复杂度：O(n)
（5）层序遍历
1.队列Q及所需指针的定义和初始化
2.如果二叉树非空，将根指针入队
3.循环直到队列Q为空
3.1 q=队列Q的队头元素出队
3.2 访问节点q的数据域 cout<data<<" ";
3.3 若节点q存在左孩子，则将左孩子指针入队
if (q->lchild != NULL)
Q[rear++] = q->lchild;
3.4若节点q存在右孩子，则将右孩子指针入队
if (q->rchild != NULL)
时间复杂度：O(n)
（6）计算二叉树深度
伪代码：
1. 定义和初始化计数深度的参数
2．如果根节点为空，return0
3．如果根节点为非空，递归调用自身的到叶子节点到根的路径长度，输出其中较大的作为树的深度
if(!root)
return 0; //空二叉子树深度为0
if(ldeep > rdeep) //ldeep就是每个“二叉
树”的左子树深度。
return ldeep + 1; //rdeep就是每个“二叉树”
的右子树深度。
时间复杂度：O(n)
(7)计算树的叶结点数
