关于二叉树的遍历梳理(递归、非递归、线索二叉…

2018-06-17 20:58:30来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

  二叉树作为的基本数据结构,应用广泛,在生活中处处可见,而遍历二叉树在二叉树应用中十分常见。与线性存储结构不同,二叉树每个节点都有可能有两棵子树,从二叉树的存储结构可知:

1 template <typename T>
2 typedef struct BiTNode
3 {
4     T data;
5     struct BiTNode *lchild, *rchild;
6 }BiTree;

  根节点、左子树、右子树——二叉树的基本组成单位。那么,根据的递归的思想(数据结构严蔚敏版):当一个复杂的问题可以分解成若干子问题来处理时,其中某些子问题与原问题有相同的特征属性,则可利用和原问题相同的分析处理方法;反之,这些子问题解决了,原问题也就迎刃而解了。递归遍历就是将原二叉树分解为若干子树。

 1 template <typename T>
 2 int PreOrderTraverse(BiTree & Tree, int (*Visit)(T & e))
 3 {
 4     //Visit函数理解为打印e,若成功返回1,否则返回0。
 5     if (Tree) //判断树是否为空树
 6     {
 7         if (Visit(Tree.data)) //打印节点数据
 8             if (PreOrderTraverse(Tree.lchild, Visit) //向左遍历
 9                 if (PreOrderTraverse(Tree.rchild, Visit) return 1; //左遍历退出遍历右侧
10         return 0;
11     }
12     else return 1;
13 }

  从递归工作过程可以看出,第i层栈顶,左子树返回i-1层进行右子树遍历,而右子树返回则直接删除栈顶返回(这取决于遍历的方式:先序遍历,中序遍历,后序遍历)。

  由此,可以模仿递归算法写出非递归算法的遍历函数。

  

 1 template <typename T>
 2 void PreOrderTraverse(BiTNode & Tree, int (*Visit(T e))
 3 {
 4     InitStack(S); //初始化栈S
 5     BiTree p; 
 6     Push(S, Tree); //根节点入栈
 7     while (!StackEmpty(S))
 8     {
 9         while (GetTop(S, p) && p) 
10         {
11             Visit(p.data);
12             Push(S,(p.lchild); //左子树压栈
13         } //while
14         Pop(S, *p); //空指针出栈,用p返回其节点---------1
15         if (!StackEmpty(S))
16         {
17             Pop(S, p); //-------------------------------2
18             Push(S,p.rchild);
19         } //if
20     } //while
21 }

  使用栈来管理遍历的过程,由于是先序遍历,所以每向左压一次栈时便Visit一次节点,到达最左端时(依次从根节点Visit了左子树各子树的根节点)向右压栈,到达右叶子节点时回退,由于第17行的退栈,会使得栈顶变为上上层的根节点。也就是遍历右子树时不需要保存当前层的根指针,可直接修改栈顶的指针。说的有些不清楚,但这和递归算法思路一致,不过是自己管理栈的进出。

  注意,粗略一看可能会产生疑惑:Pop退栈p多退了一层。这里第一个Pop函数退出空指针,p是其返回值也为空,经过第二个Pop函数p才为有效栈顶。就比如,小红组装某个物件将步骤列了个清单,她将要着手去做这一步骤时,将该步骤从清单划去,划去的这一时刻是上一件事产生的影响。

  这两种遍历是对非线性结构进行线性化操作,引用双向链表的前驱后继的思想,修改二叉树的现有数据结构,新增两个标志域——LTag和RTag。

 1 template <typename T>
 2 typedef struct BiThrNide
 3 {
 4     T data;
 5     int LTag,RTag;
 6     BiThrTree *lchild, *rchild;
 7 }BiThrTree;
 8 
 9 void InOrderTraverse(BiThrTree & Tree, int (*Visit(T e)))
10 {
11     //Tree的lchild指向树的根节点
12     //标志符LTag、RTag为0则指针域指向孩子节点,为1指向前驱或后继
13     BiThrTree p;
14     while (p != Tree)
15     {
16         while (p.LTag == 0) p = p.lchild; //向左遍历
17         if (!Visit(p.data)) exit(ERROR);
18         while (p.RTag == 1 && p.rchild != Tree) //没有右子树,指向后继,且后继不为头结点
19         {
20             P = P.rchild; //向后继遍历
21             Visit(p.data);
22         }
23         p = p.rchild;
24     }
25 }

  由于线索二叉树存储结构较普通二叉树丰满,所以遍历过程也更为好理解,此处不做赘述。

  

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++教程之初识编程

下一篇:17.C++-string字符串类(详解)