二叉树的遍历

1. //二叉树结点  
2. typedef struct BiTNode{  
3.     //数据  
4.     char data;  
5.     //左右孩子指针  
6.     struct BiTNode *lchild,*rchild;  
7. }BiTNode,*BiTree;  

1. //按先序序列创建二叉树  
2. int CreateBiTree(BiTree &T){  
3.     char data;  
4.     //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树  
5.     scanf("%c",&data);  
6.     if(data == ‘#‘){  
7.         T = NULL;  
8.     }  
9.     else{  
10.         T = (BiTree)malloc(sizeof(BiTNode));  
11.         //生成根结点  
12.         T->data = data;  
13.         //构造左子树  
14.         CreateBiTree(T->lchild);  
15.         //构造右子树  
16.         CreateBiTree(T->rchild);  
17.     }  
18.     return 0;  
19. }  

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

递归算法：

非递归算法：

<1>先序遍历：

【思路】：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。

【思路】：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
         先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。

【思路】：T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。

<4>层次遍历

【思路】：按从顶向下，从左至右的顺序来逐层访问每个节点，层次遍历的过程中需要用队列。

一、已知二叉树的前序序列和中序序列，求解树。

1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。

2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。

3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。

1.  //由前序和中序求后序
2. #include <iostream>
3. #include <string.h>
4. using namespace std;
5. typedef struct node{
6.  char data;
7.  node *left,*right;
8. }*tree;
9. char preorder[100],inorder[100];
11. /* 由前序、中序构造树
12. * i: 子树的前序序列字符串的首字符在preorder[]中的下标
13. *        j: 子树的中序序列字符串的首字符在inorder[]中的下标
14. *      len: 子树的字符串序列的长度
15. */
16. void CreatTree(tree &t,int i,int j,int len){
17.  if (len<=0)
18.   return;
19.  if (t==NULL){
20.   t=new node;
21.   t->left=t->right=NULL;
22.  }
23.  t->data=preorder[i];
24.  int m=strchr(inorder,preorder[i])-inorder; //preorder[i]在inorder[]第几个字符
25.  CreatTree(t->left,i+1,j,m-j);
26.  CreatTree(t->right,i+(m-j)+1,m+1,len-1-(m-j));
27. }
28. /*后序遍历*/
29. void PostOrder(tree t){  
30.     if(t!=NULL){  
31.         PostOrder(t->left);  //访问左子结点          
32.         PostOrder(t->right);  //访问右子结点          
33.         cout<<(t->data);  //访问根节点
34.     }  
35. }  
36. int main(){
37.  while (cin>>preorder>>inorder){
38.   tree t=NULL;
39.   int len=strlen(preorder);
40.   CreatTree(t,0,0,len);
41.   PostOrder(t);
42.   cout<<endl;
43.  }
44.  return 0;
45. }

二、已知二叉树的后序序列和中序序列，求解树。

1、确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。

2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。

3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。

1. #include <iostream>
2. #include <string.h>
3. using namespace std;
4. typedef struct node{
5.  char data;
6.  node *left,*right;
7. }*tree;
8. char inorder[100],post[100];
9. /* 由中序和后序构造树
10. * i: 子树的后序序列字符串的首字符在post[]中的下标
11. * j: 子树的中序序列字符串的首字符在inorder[]中的下标
12. *  len: 子树的字符串序列的长度
13. */
14. void CreatTree(tree &t,int i,int j,int len){
15.  if (len<=0)
16.   return;
17.  if (t==NULL){
18.   t=new node;
19.   t->left=t->right=NULL;
20.  }
21.  t->data=post[i];
22.  int m=strchr(inorder,post[i])-inorder; //post[i]在inorder[]第几个字符
23.  CreatTree(t->left,i-1-(len-1-(m-j)),j,m-j); //m-j左子树的长度,len-1-(m-j)右子树的长度
24.  CreatTree(t->right,i-1,m+1,len-1-(m-j));
25. }
26. /*前序遍历*/
27. void PreTravelTree(tree t){
28.  if (t){
29.   cout<<t->data;
30.   PreTravelTree(t->left);
31.   PreTravelTree(t->right);
32.  }
33. }
34. int main(){
35.  while (cin>>inorder>>post){
36.   tree t=NULL;
37.   int len=strlen(inorder);
38.   CreatTree(t,len-1,0,len);
39.   PreTravelTree(t);
40.   cout<<endl;
41.  }
42.  return 0;
43. }