正文

C++ 二叉树遍历实现

IP云
IP云V管理员/6 阅读
08/13
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示
  1. 原文：http://blog.csdn.net/nuaazdh/article/details/7032226
  2. //二叉树遍历
  3. //作者：nuaazdh
  4. //时间：2011年12月1日
  5. #include<stdio.h>
  6. #include<stdlib.h>
  7. //二叉树结点结构
  8. typedef struct BiTNode{
  9. char ch;            //结点数据
  10. struct BiTNode *lchild;        //左孩子
  11. struct BiTNode *rchild;        //右孩子
  12. }BiTNode,*BiTree;
  13. void AddBiTree(BiTree ,BiTNode *);//创建二叉树
  14. void PreOrderTraverse(BiTNode *); //前序遍历
  15. void InOrderTraverse(BiTNode *);   //中序遍历
  16. void PostOrderTraverse(BiTNode *);  //后序遍历
  17. void main()
  18. {
  19. char ch;//结点数据
  20. BiTree T,p;//树T，和临时树p
  21. printf("请输入结点内容(以空格未结束标识):");
  22. scanf("%c",&ch);//读入用户输入
  23. T=NULL;
  24. while(ch!=' '){//判断输入
  25. //创建新结点
  26. if(p=(BiTNode *)malloc(sizeof(BiTNode))){
  27. p->ch = ch;
  28. p->lchild = NULL;
  29. p->rchild = NULL;
  30. }
  31. else
  32. {
  33. printf("内存分配出错.\n");
  34. exit(0);
  35. }
  36. if(T==NULL)
  37. T=p;
  38. else
  39. AddBiTree(T,p);
  40. scanf("%c",&ch);//读入用户输入
  41. }
  42. //输出遍历结果
  43. printf("前序遍历：\n");
  44. PreOrderTraverse(T);
  45. printf("\n中序遍历：\n");
  46. InOrderTraverse(T);
  47. printf("\n后序遍历：\n");
  48. PostOrderTraverse(T);
  49. }
  50. //创造二叉树
  51. void AddBiTree(BiTree T,BiTree p)
  52. {
  53. if((p->ch <= T->ch)&&(T->lchild!=NULL))
  54. AddBiTree(T->lchild,p);
  55. else if((p->ch <= T->ch)&&(T->lchild==NULL))
  56. T->lchild=p;
  57. else if(T->rchild!=NULL)
  58. AddBiTree(T->rchild,p);
  59. else T->rchild=p;
  60. }
  61. //前序遍历
  62. void PreOrderTraverse(BiTree T)
  63. {
  64. if(T){
  65. printf("%c ",T->ch);
  66. PreOrderTraverse(T->lchild);
  67. PreOrderTraverse(T->rchild);
  68. }
  69. }
  70. //中序遍历
  71. void InOrderTraverse(BiTree T)
  72. {
  73. if(T){
  74. InOrderTraverse(T->lchild);
  75. printf("%c ",T->ch);
  76. InOrderTraverse(T->rchild);
  77. }
  78. }
  79. //后序遍历
  80. void PostOrderTraverse(BiTree T)
  81. {
  82. if(T){
  83. PostOrderTraverse(T->lchild);
  84. PostOrderTraverse(T->rchild);
  85. printf("%c ",T->ch);
  86. }
  87. }

原文：http://blog.csdn.net/oohaha_123/article/details/25902697

二叉树的非递归遍历

最近看书上说道要掌握二叉树遍历的6种编写方式，之前只用递归方式编写过，这次就用非递归方式编写试一试。

C++编程练习(8)----“二叉树的建立以及二叉树的三种遍历方式“（前序遍历、中序遍历、后续遍历）

递归的思想也就是栈的思想，既然不用递归，那就改用栈的方式。

“递归=栈”

1、前序遍历

前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。

a）递归实现前序遍历：

  1. void PreOrderTraverse(BiTNode *T)   /*递归前序遍历*/
  2. {
  3. if (T==NULL)
  4. return;
  5. std::cout<<T->data<<"\t";
  6. PreOrderTraverse(T->lchild);
  7. PreOrderTraverse(T->rchild);
  8. }

b）非递归实现前序遍历：

对于根结点P：
1)访问结点P，并将结点P入栈;
2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;
3)直到P为NULL并且栈为空，则遍历结束。

  1. void nPreOrderTraverse(BiTNode *T)  /*非递归前序遍历*/
  2. {
  3. if (T==NULL)
  4. return;
  5. BiTNode *p;
  6. p = T;
  7. std::stack<BiTNode*> stk;
  8. while(p!=NULL||!stk.empty())
  9. {
  10. while(p!=NULL)
  11. {
  12. std::cout<<p->data<<"\t";
  13. stk.push(p);
  14. p = p->lchild;
  15. }
  16. if(!stk.empty())
  17. {
  18. p = stk.top();
  19. stk.pop();
  20. p = p->rchild;
  21. }
  22. }
  23. }

2、中序遍历

中序遍历按照“左孩子-根结点-右孩子”的顺序进行访问。

a）递归实现中序遍历

  1. void InOrderTraverse(BiTNode *T)    /*递归中序遍历*/
  2. {
  3. if (T==NULL)
  4. return;
  5. InOrderTraverse(T->lchild);
  6. std::cout<<T->data<<"\t";
  7. InOrderTraverse(T->rchild);
  8. }

b）非递归实现中序遍历

对于根结点P：
1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
3)直到P为NULL并且栈为空则遍历结束。

  1. void nInOrderTraverse(BiTNode *T)   /*非递归中序遍历*/
  2. {
  3. if(T==NULL)
  4. return;
  5. std::stack<BiTNode*> stk;
  6. BiTNode* p;
  7. p = T;
  8. while(p!=NULL || !stk.empty())
  9. {
  10. while(p!=NULL)
  11. {
  12. stk.push(p);
  13. p = p->lchild;
  14. }
  15. if(!stk.empty())
  16. {
  17. p = stk.top();
  18. stk.pop();
  19. std::cout<<p->data<<"\t";
  20. p = p->rchild;
  21. }
  22. }
  23. }

3、后序遍历

后序遍历按照“左孩子-右孩子-根结点”的顺序进行访问。

a）递归实现后序遍历

  1. void PostOrderTraverse(BiTNode *T)  /*递归后序遍历*/
  2. {
  3. if(T==NULL)
  4. return;
  5. PostOrderTraverse(T->lchild);
  6. PostOrderTraverse(T->rchild);
  7. std::cout<<T->data<<"\t";
  8. }

b）非递归实现后序遍历

这里实现略复杂，当初想出来的方法过于笨重，后参考http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html，改写如下：

要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

对于根结点P：

1)将P入栈，设置当前结点 cur ；

2)将当前的 cur 置为栈顶结点，如果 cur 不存在左孩子和右孩子，或者 cur 存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则可以直接访问该结点并进行出栈操作。否则将 cur 的右孩子和左孩子依次入栈；

3)直到栈为空则遍历结束。

  1. void nPostOrderTraverse(BiTNode *T)     /*非递归后序遍历*/
  2. {
  3. if(T==NULL)
  4. return;
  5. BiTNode* cur;       /*当前结点*/
  6. BiTNode* pre = NULL;        /*前一次输出的结点*/
  7. std::stack<BiTNode*> stk;
  8. stk.push(T);
  9. while(!stk.empty())
  10. {
  11. cur = stk.top();
  12. if((cur->lchild==NULL && cur->rchild==NULL) ||
  13. (pre!=NULL && (cur->lchild==pre || cur->rchild==pre)))
  14. {                               /*如果当前结点没有孩子结点或者孩子节点都已被访问过*/
  15. std::cout<<cur->data<<"\t";
  16. stk.pop();
  17. pre = cur;
  18. }
  19. else
  20. {
  21. if(cur->rchild!=NULL)
  22. stk.push(cur->rchild);
  23. if(cur->lchild!=NULL)
  24. stk.push(cur->lchild);
  25. }
  26. }
  27. }

4、完整测试代码

1)BiTree.h头文件

  1. /* BiTree.h头文件 */
  2. #include<iostream>
  3. #include<stack>
  4. typedef char TElemType;
  5. class BiTNode{                  /*创建结点类，使用的是左右孩子表示法*/
  6. public:
  7. BiTNode():data(0),lchild(NULL),rchild(NULL){}
  8. TElemType data;
  9. BiTNode *lchild,*rchild;
  10. };
  11. void CreateBiTree(BiTNode **T)      /*二叉树的建立，这里形参用的是双指针，需要注意*/
  12. {                                           /*这里输入的是一个扩展二叉树，每个结点若有空指针，*/
  13. TElemType ch;                               /*则将其值设为一个特定值，本代码中是'#'*/
  14. std::cin>>ch;
  15. std::cin.clear();
  16. if(ch=='#')
  17. *T=NULL;
  18. else
  19. {
  20. *T=new BiTNode;
  21. if(!*T)
  22. exit(1);
  23. (*T)->data=ch;
  24. CreateBiTree(&(*T)->lchild);
  25. CreateBiTree(&(*T)->rchild);
  26. }
  27. }
  28. void PreOrderTraverse(BiTNode *T)   /*递归前序遍历*/
  29. {
  30. if (T==NULL)
  31. return;
  32. std::cout<<T->data<<"\t";
  33. PreOrderTraverse(T->lchild);
  34. PreOrderTraverse(T->rchild);
  35. }
  36. void nPreOrderTraverse(BiTNode *T)  /*非递归前序遍历*/
  37. {
  38. if (T==NULL)
  39. return;
  40. BiTNode *p;
  41. p = T;
  42. std::stack<BiTNode*> stk;
  43. while(p!=NULL||!stk.empty())
  44. {
  45. while(p!=NULL)
  46. {
  47. std::cout<<p->data<<"\t";
  48. stk.push(p);
  49. p = p->lchild;
  50. }
  51. if(!stk.empty())
  52. {
  53. p = stk.top();
  54. stk.pop();
  55. p = p->rchild;
  56. }
  57. }
  58. }
  59. void InOrderTraverse(BiTNode *T)    /*递归中序遍历*/
  60. {
  61. if (T==NULL)
  62. return;
  63. InOrderTraverse(T->lchild);
  64. std::cout<<T->data<<"\t";
  65. InOrderTraverse(T->rchild);
  66. }
  67. void nInOrderTraverse(BiTNode *T)   /*非递归中序遍历*/
  68. {
  69. if(T==NULL)
  70. return;
  71. std::stack<BiTNode*> stk;
  72. BiTNode* p;
  73. p = T;
  74. while(p!=NULL || !stk.empty())
  75. {
  76. while(p!=NULL)
  77. {
  78. stk.push(p);
  79. p = p->lchild;
  80. }
  81. if(!stk.empty())
  82. {
  83. p = stk.top();
  84. stk.pop();
  85. std::cout<<p->data<<"\t";
  86. p = p->rchild;
  87. }
  88. }
  89. }
  90. void PostOrderTraverse(BiTNode *T)  /*递归后序遍历*/
  91. {
  92. if(T==NULL)
  93. return;
  94. PostOrderTraverse(T->lchild);
  95. PostOrderTraverse(T->rchild);
  96. std::cout<<T->data<<"\t";
  97. }
  98. void nPostOrderTraverse(BiTNode *T)     /*非递归后序遍历*/
  99. {
  100. if(T==NULL)
  101. return;
  102. BiTNode* cur;       /*当前结点*/
  103. BiTNode* pre = NULL;        /*前一次输出的结点*/
  104. std::stack<BiTNode*> stk;
  105. stk.push(T);
  106. while(!stk.empty())
  107. {
  108. cur = stk.top();
  109. if((cur->lchild==NULL && cur->rchild==NULL) ||
  110. (pre!=NULL && (cur->lchild==pre || cur->rchild==pre)))
  111. {                               /*如果当前结点没有孩子结点或者孩子节点都已被访问过*/
  112. std::cout<<cur->data<<"\t";
  113. stk.pop();
  114. pre = cur;
  115. }
  116. else
  117. {
  118. if(cur->rchild!=NULL)
  119. stk.push(cur->rchild);
  120. if(cur->lchild!=NULL)
  121. stk.push(cur->lchild);
  122. }
  123. }
  124. }

2)main文件

  1. #include"BiTree.h"
  2. using namespace std;
  3. int main()
  4. {
  5. BiTNode *T=new BiTNode;
  6. std::cout<<"请前序遍历输入各节点：";
  7. CreateBiTree(&T);
  8. cout<<"\n该树的前序遍历输出为："<<endl;
  9. PreOrderTraverse(T);
  10. cout<<endl;
  11. nPreOrderTraverse(T);
  12. cout<<"\n该树的中序遍历输出为："<<endl;
  13. InOrderTraverse(T);
  14. cout<<endl;
  15. nInOrderTraverse(T);
  16. cout<<"\n该树的后序遍历输出为："<<endl;
  17. PostOrderTraverse(T);
  18. cout<<endl;
  19. nPostOrderTraverse(T);
  20. cout<<endl;
  21. return 0;
  22. }

5、测试结果