当前位置:   article > 正文

二叉树遍历的递归与非递归算法_第4关:遍历二叉树

第4关:遍历二叉树

二叉树的递归遍历(深度优先遍历)

先来张图,看看各结点遍历时的情况:

二叉树深度优先遍历总结(分别为第一次,第二次,第三次进入某个结点):

  1. 先序遍历:先访问根结点,然后先序遍历左子树,最后先序遍历右子树;根->左->右
  2. 中序遍历:先中序遍历左子树,然后访问根结点,最后中序遍历右子树;左->根->右
  3. 后序遍历:先后序遍历左子树,然后后序遍历右子树,最后访问根结点;左->右->根

递归遍历代码比较简单,先、中、后序遍历递归代码基本相似,总代码:

  1. void r(BTNode *p)
  2. {
  3. if (p != NULL)
  4. {
  5. //第一次进入-先序
  6. r(p->lchild);
  7. //第二次进入-中序
  8. r(p->rchild);
  9. //第三次进入-后序
  10. }
  11. }

1. 先序遍历递归函数:

  1. void r(BTNode *p)
  2. {
  3. if (p != NULL)
  4. {
  5. visit(p);
  6. r(p->lChild);
  7. r(p->rChild);
  8. }
  9. }

2. 中序遍历递归函数:

  1. void r(BTNode *p)
  2. {
  3. if (p != NULL)
  4. {
  5. r(p->lChild);
  6. visit(p);
  7. r(p->rChild);
  8. }
  9. }

3. 后序遍历递归函数:

  1. void r(BTNode *p)
  2. {
  3. if (p != NULL)
  4. {
  5. r(p->lChild);
  6. r(p->rChild);
  7. visit(p);
  8. }
  9. }

二叉树的非递归遍历(深度优先遍历)

须知:非递归需要自定制辅助栈

1. 先序遍历非递归化:

1)利用辅助栈将根节点入栈,出栈操作,访问该节点,将其右、左孩子分别入栈,保证左孩子先出来(每次访问节点后,对其左、右孩子需要做一个检测,为空的孩子无需入栈)
2)左孩子出栈后,访问该节点,将其右、左孩子分别入栈,多次操作!
3)直至栈空为止(出栈是在循环之内执行,即使栈空也会执行右左孩子入栈操作)

栈辅助先序遍历过程:

1入栈、1出栈
3入栈、2入栈、2出栈
5入栈、4入栈、4出栈
4没有孩子结点,5出栈、3出栈
7入栈、6入栈、6出栈
检测到6右孩子为空,左孩子8不空,8入栈、8出栈
7没有孩子结点,直接出栈

  1. void preorderNonrecursion(BTNode *bt)
  2. {
  3. if (bt != NULL) //根节点是否为空
  4. {
  5. BTNode *Stack[maxSize];
  6. int top = -1; //创建栈
  7. BTNode *p = NULL; //遍历指针
  8. Stack[++top] = bt; //节点入栈
  9. while(top != -1) //栈不空时循环
  10. {
  11. p = Stack[top--]; //出栈一个元素
  12. Visit(p); //访问
  13. if(p->rChild != NULL) //右孩子不为空就入栈
  14. Stack[++top] = p->rChild;
  15. if(p->lChild != NULL) //左孩子不为空就入栈
  16. Stack[++top] = p->lChild;
  17. }
  18. }
  19. }

2. 后序遍历非递归化:

根结点:白色
左子树:黄色
右子树:红色

先把黄色245(左子树)与红色3687(右子树)交换得到第二条,然后把黄色68和红色7交换、黄色4和红色5交换得到第三条,即逆后序。

// 先序(根左右),而后序(左右根),将后序逆转为逆后序(根右左),逆后序的左右交换即可成为前序(根左右)
// 在这我们可以使用逆后序(根右左),把逆后序的结果压入一个新栈,出栈就得到后序遍历序列

1)将根节点入辅助栈(栈1),出栈操作,将出栈后的该元素入逆序栈(栈2),将其左、右孩子分别入辅助栈,保证右孩子先出栈(每次对其左、右孩子需要做一个检测,为空的孩子无需入栈);
2)右孩子出辅助栈(栈1),将出栈后的该元素入逆序栈(栈2),将其左、右孩子分别入辅助栈(栈1),多次操作;
3)直至辅助栈空为止,出栈是在循环之内执行,即使栈空也会执行左右孩子入栈操作;
4)逆序栈(栈2)中元素逐个出栈并访问

  1. void postorderNonrecursion(BTNode *bt)
  2. {
  3. if (bt != NULL) //根节点不为空
  4. {
  5. BTNode *Stack1[maxSize];
  6. int top1= -1; //创建栈1(辅助遍历的栈)
  7. BTNode *Stack2[maxSize];
  8. int top2= -1; //创建栈2(结果逆序的栈)
  9. BTNode *p = NULL; //遍历指针
  10. Stack1[++top1] = bt; //节点入栈1
  11. while(top1 != -1) //栈不空时循环
  12. {
  13. p = Stack1[top1--]; //栈1出栈一个元素
  14. Stack2[++top2] = p; //出栈元素入栈2
  15. if(p->lChild != NULL) //左孩子不为空就入栈
  16. Stack[++top] = p->lChild;
  17. if(p->rChild != NULL) //右孩子不为空就入栈
  18. Stack[++top] = p->rChild;
  19. }
  20. while(top2 != -1)
  21. {
  22. p = Stack2[top2--]; //栈2元素逐个出栈
  23. Visit(p); //访问
  24. }
  25. }
  26. }

3. 中序遍历非递归化:

1)从根节点开始,一直左走,并把途径的左孩子节点入栈;
2)遇到左孩子为空时,栈顶元素出栈,访问该节点,p指向该节点的右孩子;
3)直到栈空或者P为NULL则遍历结束

栈辅助中序遍历过程:

1入栈、2入栈、4入栈
4左孩子为空,4出栈、2出栈
取2的右孩子5入栈,5左孩子为空,5出栈
1出栈,取其右孩子3入栈、其左孩子6入栈、8入栈
8左孩子为空,8出栈、6出栈、3出栈
最后取7入栈、7出栈

  1. void inorderNonrecursion(BTNode *bt)
  2. {
  3. if(bt != NULL) //树不空
  4. {
  5. BTNode *Stack[maxSize];
  6. int top = -1; //创建栈
  7. BTNode *p = NULL; //遍历指针
  8. p = bt; //节点入栈1
  9. while(top != -1 || p != NULL) //栈不空或者p不空
  10. {
  11. while(p != NULL)
  12. {
  13. Stack[++top] = p; //入栈
  14. p = p->lChild; //左走
  15. }
  16. if(top != -1)
  17. {
  18. p = Stack[top--]; //出栈
  19. Visit(p); //访问该节点
  20. p = p->rChild; //右走
  21. }
  22. }
  23. }
  24. }

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/737678
推荐阅读
相关标签
  

闽ICP备14008679号