二叉树的递归操作

1，二叉树的遍历

二叉树的遍历操作分为常见的前序遍历（Preorder transversal），中序遍历（Inorder transversal）以及后序遍历（Postorder transversal）。

前序遍历：根----->左子树----->右子树

1 void preorder_transversal(BinTree& root){
2     if(root){
3         cout<<root->data<<" ";
4         preorder_transversal(root->left);
5         preorder_transversal(root->right);
6     }
7 }

View Code

中序遍历：左子树------>根---->右子树

1 void inorder_transversal(BinTree& root){
2     if(root){
3         inorder_transversal(root->left);
4         cout<<root->data<<" ";
5         inorder_transversal(root->right);
6     }
7 }

View Code

后序遍历：左子树---->右子树------>根

1 void postorder_transversal(BinTree& root){
2     if(root){
3         postorder_transversal(root->left);
4         postorder_transversal(root->right);
5         cout<<root->data<<" ";
6     }
7 }

View Code

2，二叉树的层高

层高就是取左子树和右子树的层高的最大值加一（加上根所在的层）： max( height( root->left ), height( root->right ) ) +1。

1 int height(BinTree root){
2     if(root==NULL)
3         return 0;
4     else
5         return height(root->left) > height(root->right)? height(root->left)+1:height(root->right)+1;
6 }

View Code

3，二叉树的层次遍历

用递归按层遍历二叉树不好理解。

1，该函数应该有两个参数：二叉树的根节点以及要遍历的层数；

2，遍历第0层，应该直接访问根节点的数据；

3，遍历第N层，相对于遍历root的左子树和右子树的第N-1层。

 1 void printNodeAtLevel1(BinTree root, int level){
 2     if(!root || level < 0)
 3         return ;
 4     else if(level == 0)
 5     {
 6         cout << root->data <<" ";
 7     }
 8     else{
 9         printNodeAtLevel1(root->left, level - 1);
10         printNodeAtLevel1(root->right, level - 1);
11     }
12 }

View Code

1 Preorder transversal: 
2 0 2 1 8 6 11 5 9 7 10 
3 Inorder transversal: 
4 1 2 6 8 11 0 5 7 9 10 
5 Postorder transversal: 
6 1 6 11 8 2 7 10 9 5 0

View Code