二叉树的遍历

1.二叉树结点的定义

1 typedef char ElemType;
2 typedef struct node
3 {
4     ElemType data;
5     struct node *lchild;
6     struct node *rchild;
7 }BiTree;

View Code

2.建树

 1 void CreateBiTree(BiTree *&T)
 2 {
 3     char ch;
 4     //按先序次序输入二叉树中节点的值（一个字符），空格字符表示空树
 5     scanf("%c",&ch); 
 6     if(ch==' ')  
 7         T=NULL;
 8     else
 9     {
10         T=(BiTree *)malloc(sizeof(BiTree));
11         T->data=ch;               //生成根结点 
12         CreateBiTree(T->lchild);  //构造左子树 
13         CreateBiTree(T->rchild);  //构造右子树 
14     }
15 }

View Code

例如如果要建一棵如下图的二叉树，需要输入ABC××D××E×F××(×表示空格)

3.先序遍历递归算法（中序、后序遍历递归算法类似）

1 void PreOrder(BiTree *T)
2 {
3     if(T!=NULL)
4     {
5         printf("%c",T->data);
6         PreOrder(T->lchild);
7         PreOrder(T->rchild);
8     }
9 }

View Code

4.先序遍历非递归算法

 1 void PreOrderTraverse(BiTree *T)
 2 {
 3     stack<BiTree*> s;
 4     if(T==NULL)
 5     {
 6         printf("空树
");
 7         return;
 8     }
 9     while(T||!s.empty())
10     {    
11         //让根结点先进栈(用来还原)，然后一直向左边搜索 
12         while(T)
13         {
14             s.push(T);
15             printf("%c",T->data);
16             T=T->lchild;
17         }
18         //把最近的根结点还原，遍历其右子树 
19         T=s.top();
20         s.pop();
21         T=T->rchild;
22     }
23 }

View Code

5.中序遍历非递归算法，跟先序遍历非递归算法唯一的不同是访问结点的时间不一样

 1 void InOrderTraverse(BiTree *T)
 2 {
 3     stack<BiTree *> s;
 4     if(T==NULL)
 5     {
 6         printf("空树
");
 7         return;
 8     }
 9     while(T||!s.empty())
10     {    
11         //让根结点先进栈(用来还原)，然后一直向左边搜索 
12         while(T)
13         {
14             s.push(T);
15             T=T->lchild;
16         }
17         //把最近的根结点还原，遍历其右子树 
18         T=s.top();
19         s.pop();
20         //在出栈之后访问该结点 
21         printf("%c",T->data);
22         T=T->rchild;
23     }
24 }

View Code

6.后序遍历非递归算法，添加一个pre指针来判断右子树是否被访问。

 1 void PostOrderTraverse(BiTree *T)
 2 {
 3     stack<BiTree *> s;    
 4     BiTree *pre=NULL;     //指向前一个被访问的节点 
 5     if(T==NULL)
 6     {
 7         printf("空树
");
 8         return;
 9     }
10     while(T||!s.empty()) 
11     {
12         //一直向左走直到为空 
13         while(T)
14         {
15             s.push(T);
16             T=T->lchild;
17         }
18         T=s.top();
19         //当前节点的右孩子如果为空或者已经被访问过，则访问当前节点 
20         if(T->rchild==NULL||T->rchild==pre)
21         {
22             printf("%c",T->data);
23             pre=T;
24             s.pop();
25             T=NULL;
26         }
27         //否则访问右孩子 
28         else
29             T=T->rchild;
30     }
31 }

View Code

二叉搜索树是二叉树的其中一个重要的应用。可以查看之前关于二叉搜索树的笔记：http://www.cnblogs.com/runnyu/p/4677902.html