二叉树遍历算法递归非递归 (C C++语言实现)

女爷i 2022-04-10 06:37 232阅读 0赞

# [我非英雄][Link 1] #

# #

*  [博客园][Link 2]
 *  [首页][Link 1]
 *  [新随笔][Link 3]
 *  [联系][Link 4]
 *  [管理][Link 5]
 *  [订阅][Link 6][![订阅][20181228120453921]][Link 6]

随笔- 4  文章- 0  评论- 1

# [二叉树的递归遍历与非递归算法实现][Link 7][ (C语言实现)][Link 7] #

通过递归算法与非递归算法的比较，更好地理解各自的特点。非递归其实就是调用栈的基本操作，进栈，出栈等。

这里面也正好复习了下栈的基本算法的实现。

栈和队列的实现在我的前一篇博文里。

基本数据结构

typedef struct BiNode

char data;   //此处，二叉树中节点值类型为字符型

struct BiNode \*lchild,\*rchild;     //左右孩子节点

\}BiNode,\*BiTree;

二叉树的创建

先申请根节点的空间，然后赋值，然后分别递归建立其左子树和右子树

//按照先序序列输入构建一棵二叉树![20181228120453968][]

![复制代码][201812281204549]

1 //按照先序序列输入构建一棵二叉树
     2 void Create(BiTree &T)
     3 {
     4     char ch;
     5     scanf("%c",&ch);
     6     if( '#' == ch )
     7     {
     8         T = NULL;
     9     }
    10     else
    11     {
    12         T=(BiNode *)malloc(sizeof(BiNode));
    13         T->data=ch;
    14         Create(T->lchild);
    15         Create(T->rchild);
    16     }
    17 }

![复制代码][201812281204549]

二叉树的递归遍历算法

//二叉树的遍历，三种顺序的递归遍历，其实就是访问根节点的顺序不同,这里的访问操作是打印结点，也可以是对结点其他的操作

![20181228120453968][]

![复制代码][201812281204549]

1 //二叉树的先序遍历
     2 
     3 void PreOrder(BiTree T)
     4 
     5 {
     6 
     7       if(T)
     8 
     9      {
    10 
    11            printf( "%c ",T->data);
    12 
    13            PreOrder(T->lchild);
    14 
    15            PreOrder(T->rchild);
    16 
    17      }
    18 
    19 }
    20 
    21 //二叉树的中序遍历
    22 
    23 void InOrder(BiTree T)
    24 
    25 {
    26 
    27       if(T)
    28 
    29      {
    30 
    31            InOrder(T->lchild);
    32 
    33            printf( "%c ",T->data);
    34 
    35            InOrder(T->rchild);
    36 
    37      }
    38 
    39 }
    40 
    41  
    42 
    43 //二叉树的后序遍历
    44 
    45 void PostOrder(BiTree T)
    46 
    47 {
    48 
    49       if(T)
    50 
    51      {
    52 
    53            PostOrder(T->lchild);
    54 
    55            PostOrder(T->rchild);
    56 
    57            printf( "%c ",T->data);
    58 
    59      }
    60 
    61 }

![复制代码][201812281204549]

二叉树的非递归遍历算法

二叉树先序遍历的非递归算法

![复制代码][201812281204549]

/* 设置一个存放结点指针的栈 S ，从根结点开始，每访问一结点后，按先序规则走左子树，若右子树存在，
    
    则将右子树指针进栈，以便以后能正确地返回到该右子树上进行遍历访问。
    
    */
    
    void PreTraverse(BiTree T)
    
    {
    
         BiNode *p;
    
         Stack S;
    
         S=InitStack();
    
          if (T)
    
         {
    
               Push(S,T);  // 根结点指针进栈
    
                while (!StackEmpty(S))
    
               {
    
                    p=Pop(S);  // 出栈，栈顶元素赋给 p
    
                     while (p)
    
                    {
    
                         printf( "%c\t" ,p->data);  // 访问 p结点
    
                          if (p->rchild)
    
                               Push(S,p->rchild);  // 右子树存在时，进栈
    
                         p=p->lchild;            // 继续沿着左子树往下走
    
                    }
    
               }
    
         }
    
    }

![复制代码][201812281204549]

/\*

说明：内部循环是从 p 结点出发一直走到最左，走的过程中保存了每一个右子树的地址，

（因为右子树还没有被访问）而且是先进后出的，即先保存的比后保存的更先被用作返回地址，

所以是用栈。外循环正好是当内部循环不下去的时候，退一栈的情形。即换成他的右子树。

\*/

// 二叉树的中序遍历的非递归算法

![复制代码][201812281204549]

/*
    
    同前序遍历 , 栈S 存放结点指针。对每棵子树 ( 开始是整棵二叉树 ),沿左找到该子树在中序下的第一结点
    
    ( 但寻找路径上的每个结点指针要进栈 ), 访问之; 然后遍历该结点的右子树 ,
    
    又寻找该子树在中序下的第一结点， .. …直到栈S 空为止。
    
    */
    
    
    void InTraverse(BiTree T)
    
    {
    
         BiNode *p;
    
         Stack S;
    
         S=InitStack();
    
         Push(S,T);  // 根结点指针进栈
    
          while (!StackEmpty(S))
    
         {
    
                while ((p=GetsTop(S))&&p)  //取栈顶元素且存在，赋给 p
    
                    Push(S,p->lchild);    //p 的左子树进栈
    
               p=Pop(S);               // 去掉最后的空指针
    
                if (!StackEmpty(S))
    
               {
    
                    p=Pop(S);       // 弹出栈顶元素，赋给 p
    
                    printf( "%c\t" ,p->data);   // 访问 p结点
    
                    Push(S,p->rchild);     // 右子树进栈，然后遍历右子树
    
               }
    
         }
    
    }

![复制代码][201812281204549]

/\*

说明：和前序不一样，这里的栈保存的是根结点的地址（因为中序遍历先访问左子树，

而根结点没有被访问到。而前序遍历不一样，他一开始就访问根结点，

所以他不保存根结点的地址而是保存右子树的地址，因为右子树还没有被访问。

总之，用栈就是为了帮我们保存还没有被访问的地址，以便将来我们能找到返回的地址）。

\*/

/\* 后序遍历二叉树的非递归算法 \*/

![复制代码][201812281204549]

/* 对一个结点是否能访问，要看他的左、右子树是否遍历完， */
    
    /* 所以每一个结点对应一个标志位 -tag 。tag=0 ，表示该结点暂不能访问； tag=1 ，表示该结点可以访问 */
    
    /* 其实是区分这次返回是遍历完左子树返回的还是遍历完右子树返回的，如果是左子树返回的那么就不能访问根结点， */
    
    /* 如果是右子树返回的就能访问根结点。当搜索到某 P 结点时，先要遍历其左子树，因而将结点地址 P 及tag=0 进栈； */
    
    /* 当P 结点的左子树遍历完之后，再遍历其右子树，又将地址 P 及tag=1 进栈；当 P结点右子树遍历完之后（ tag=1 ），便可对 P结点进行访问 */
    
    void PostTraverse(BiTree T)
    
    {
    
          int tag;
    
         BiNode *p;
    
         Stacks S;
    
         SNode sdata;
    
         S=InitStacks();
    
         p=T;
    
          while (p||!StacksEmpty(S))
    
         {
    
                while (p)
    
               {
    
                    sdata.q=p;
    
                    sdata.tag=0;
    
                    Pushs(S,&sdata);   //(p,0) 进栈
    
                    p=p->lchild;      // 遍历p 之左子树
    
               }
    
               sdata=*Pops(S);  // 退栈
    
               p=sdata.q;     // 取指针
    
               tag=sdata.tag; // 状态位
    
                if (tag==0)     //从左子树返回时，根的 tag=0
    
               {
    
                    sdata.q=p;
    
                    sdata.tag=1;      // 这时要进入根的右子树了，所以根的 tag=1 ，下次碰到根时就可以访问了
    
                    Pushs(S,&sdata);   //(p,1) 进栈，根还得进一次栈
    
                    p=p->rchild;     // 遍历右子树
    
               }
    
                else           //tag=1，这是说明了右子树访问完了返回，所以这次要对根进行访问了
    
               {
    
                    printf( "%c\t" ,p->data);
    
                    p=NULL;
    
               }
    
         }
    
    }

![复制代码][201812281204549]

**二叉树的层次遍历**

![复制代码][201812281204549]

// 二叉树的层次遍历
    
    void LevelTraverse(BiTree T)
    
    {
    
         BiNode *p;
    
         LinkQueue *Q;
    
         InitQueue(Q);
    
         EnQueue(Q,T);
    
          while (!QueueEmpty(Q))
    
         {
    
               p=DeQueue(Q);
    
               printf( "%c\t" ,p->data);
    
                if (p->lchild!=NULL)
    
                    EnQueue(Q,p->lchild);
    
                if (p->rchild!=NULL)
    
                    EnQueue(Q,p->rchild);
    
         }
    
    }

![复制代码][201812281204549]

下面是完整代码：

![20181228120454542][]

/\*测试数据\*/

/\* 分别是构建二叉树的输入数据以及先序、中序、后序、层次遍历序列：

ABE\#\#C\#D\#\#F\#GH\#I\#\#J\#\#

ABECDFGHIJ

EBCDAFHIGJ

EDCBIGJGFA

ABFECGDHJI

\*/

![20181228120454583][]

图画得有点丑，见笑了。

标签: [数据结构][Link 8], [队列][Link 9], [二叉树][Link 10], [遍历][Link 11], [递归][Link 12], [非递归][Link 13]

好文要顶 关注我 收藏该文 ![20181228120454623][] ![20181228120454662][]

[![20181228120454704][]][20181228120454704 1]

[我非英雄][20181228120454704 1]  
[关注 - 58][- 58]  
[粉丝 - 6][- 6]

\+加关注

[« ][Link 14]上一篇：[二叉树遍历非递归算法所用到的栈以及层次遍历所用到的队列的基本操作算法的实现][Link 14]

posted @ 2013-12-05 11:25 [我非英雄][Link 1] 阅读(9309) 评论(1) [编辑][Link 15] [收藏][Link 16]

[https://www.cnblogs.com/pkg313133/p/3459171.html][Link 7]

# 二叉树的三种遍历（一）--- 链式存储[ (C语言实现)][Link 7] #

2018年05月26日 11:12:27 [zhuoya\_][zhuoya] 阅读数：368

如下有一颗树：

![70][]

树的三种遍历结果分别为：

先序遍历：==》根、左、右

ABCDEFGH

中序遍历：==》左、根、右

CBEDFAGH

后序遍历：==》左、右、根

CEFDBHGA

将代码贴上来以便好查找^O^：

链式存储的二叉树长这样，如下：

![70 1][]

二叉树的定义：

1.  `typedef char elemtype;`
2.  `#define END '#'`
3.  `typedef struct BtNode`
4.  `{`
5.  `struct BtNode* leftchild;`
6.  `struct BtNode* rightchild;`
7.  `elemtype data;`
8.  `}BtNode,*pBtNode;`

创建一颗树：（利用先序的方法，将空结点用\#表示）

1.  `BtNode* BuyNode()`
2.  `{`
3.  `BtNode* bt=(pBtNode)malloc(sizeof(BtNode));`
4.  `if(bt==NULL)`
5.  `exit(1);`
6.   
7.  `return bt;`
8.  `}`
9.   
10. `BtNode* Create()`
11. `{`
12. `BtNode* bt=NULL;`
13. `//bt=BuyNode();//ERROR`
14. `elemtype elem;`
15.  
16. `cin>>elem;`
17.  
18. `if(elem!=END)`
19. `{`
20. `bt=BuyNode();//OK一定要放在使用之前`
21.  
22. `bt->data=elem;`
23. `bt->leftchild=Create();`
24. `bt->rightchild=Create();`
25. `}`
26. `return bt;`
27. `}`

三种遍历的递归写法：

1.  `void PreTraval(BtNode* ptr)//先序遍历`
2.  `{`
3.  `if(ptr!=NULL)`
4.  `{`
5.  `cout<<ptr->data<<" ";//根结点`
6.  `PreTraval(ptr->leftchild);//左子树`
7.  `PreTraval(ptr->rightchild);//右子树`
8.  `}`
9.  `return ;`
10. `}`
11.  
12. `void OrderTraval(BtNode* ptr)//中序遍历`
13. `{`
14. `if(ptr!=NULL)`
15. `{`
16. `OrderTraval(ptr->leftchild);//左子树`
17. `cout<<ptr->data<<" ";根结点`
18. `OrderTraval(ptr->rightchild);右子树`
19. `}`
20. `return ;`
21. `}`
22.  
23. `void PostTraval(BtNode* ptr)//后序遍历`
24. `{`
25. `if(ptr!=NULL)`
26. `{`
27. `PostTraval(ptr->leftchild);//左子树`
28. `PostTraval(ptr->rightchild);//右子树`
29. `cout<<ptr->data<<" ";根结点`
30. `}`
31. `return ;`
32. `}`

三种遍历的非递归写法：

1.  `void NicePreTraval(BtNode *ptr)//非递归的先序遍历`
2.  `{`
3.  `//方法一：依旧是利用栈来实现，代码有点冗余`
4.  `//if(ptr==NULL)`
5.  `// return ;`
6.   
7.  `//stack<pBtNode> st;`
8.  `//pBtNode pCur=ptr;`
9.  `//while(1)`
10. `//{`
11. `// if(pCur==NULL && st.empty())`
12. `// break;`
13. `// else if(pCur!=NULL)`
14. `// {`
15. `// cout<<pCur->data<<" ";`
16. `// st.push(pCur);`
17. `// pCur=pCur->leftchild;`
18. `// }`
19. `// else if(pCur==NULL)`
20. `// {`
21. `// pCur=st.top();`
22. `// st.pop();`
23. `// pCur=pCur->rightchild;`
24. `// }`
25. `//}`
26.  
27. `//方法二：利用队列，先让右子树入队，再让左子树入队，完美！！！`
28. `stack<BtNode*> st;`
29. `if(ptr!=NULL)`
30. `st.push(ptr);`
31. `while(!st.empty())`
32. `{`
33. `ptr=st.top();st.pop();//一定要放在这，放在后面就会死循环,因为后边有其他元素入栈。`
34. `cout<<ptr->data<<" ";`
35.  
36. `if(ptr->rightchild!=NULL)`
37. `st.push(ptr->rightchild);`
38. `if(ptr->leftchild!=NULL)`
39. `st.push(ptr->leftchild);`
40.  
41. `}`
42.  
43. `}`
44. `void NiceOrderTraval(BtNode *ptr)//非递归的中序遍历`
45. `{`
46. `//方法一：用死循环，代码看起来不是特别整洁`
47. `//if(ptr==NULL)`
48. `// return ;`
49.  
50. `//stack<pBtNode> st;`
51. `//pBtNode pCur=ptr;`
52. `//while(1)`
53. `//{`
54. `// if(pCur==NULL && st.empty())`
55. `// break;`
56. `// else if(pCur!=NULL)`
57. `// {`
58. `// st.push(pCur);`
59. `// pCur=pCur->leftchild;`
60. `// }`
61. `// else if(pCur==NULL)`
62. `// {`
63. `// pCur=st.top();`
64. `// cout<<pCur->data<<" ";`
65. `// st.pop();`
66. `// pCur=pCur->rightchild;`
67. `// }`
68. `//}`
69.  
70. `//方法二：两层while循环，代码比较整洁`
71. `stack<BtNode*> st;`
72. `while(ptr!=NULL || !st.empty())`
73. `{`
74. `while(ptr!=NULL)`
75. `{`
76. `st.push(ptr);`
77. `ptr=ptr->leftchild;`
78. `}`
79. `ptr=st.top();`
80. `cout<<ptr->data<<" ";`
81. `st.pop();`
82. `ptr=ptr->rightchild;`
83. `}`
84.  
85. `}`
86. `void NicePostTraval(BtNode *ptr)//非递归的后序遍历`
87. `{`
88. `//如果给树的节点上添加一个标志域，是不可行的，因为添加的标志位在一次访问之后全部都会被改变，在进行第二次访问时就无法达到预期的效果。`
89. `//方法是在中序的非递归上进行改进，采用的是两个指针来进行标志`
90. `stack<BtNode*> st;`
91. `BtNode *tag=NULL;`
92. `while(ptr!=NULL || !st.empty())`
93. `{`
94. `while(ptr!=NULL)`
95. `{`
96. `st.push(ptr);`
97. `ptr=ptr->leftchild;`
98. `}`
99. `ptr=st.top();`
100. `st.pop();`
101. `if(ptr->rightchild==tag || ptr->rightchild==NULL)`
102. `{`
103. `cout<<ptr->data<<" ";`
104. `tag=ptr;`
105. `ptr=NULL;//必须得写！！！！！！否则ptr!=NULL，程序将一直无限死循环下去`
106. `}`
107. `else`
108. `{`
109. `st.push(ptr);`
110. `ptr=ptr->rightchild;`
111. `}`
112. `}`
113. `}`

![70 2][]

END……

[https://blog.csdn.net/zhuoya\_/article/details/80459751][https_blog.csdn.net_zhuoya_article_details_80459751]

原

# 二叉树（bitree）相关基本算法C语言实现 #

2018年05月25日 22:52:21 [此生无分起相思][Link 17] 阅读数：219

备考期间写的二叉树类数据结构相关基本算法的C语言实现，为以后使用方便，现记录如下：

**全局定义和依赖：**

1.  `#include <stdio.h>`
2.  `#include <stdlib.h>`
3.  `#define elemType int`
4.  `#define ERROR 0`
5.  `#define OK 1`
6.  `#define END NULL`

**二叉树结点：**

1.  `typedef struct BTree //二叉树结点`
2.  `{`
3.  `elemType data;`
4.  `struct BTree *Lchild,*Rchild;`
5.  `} BiNode,*BiTree;`

**初始化二叉树：**

1.  `BiTree initBiTree(elemType root) //初始化二叉树`
2.  `{`
3.  `BiNode *bt;`
4.  `bt = (BiNode*)malloc(sizeof(BiNode));`
5.  `if(bt==NULL){printf("Init BiTree Failed!\n");}`
6.  `else{`
7.  `bt->data = root;`
8.  `bt->Lchild = bt->Rchild = NULL;`
9.  `printf("Init BiTree Succeed!\n");`
10. `return bt;`
11. `}`
12. `}`

**递归式生成二叉树（前序）：**

1.  `//递归式`
2.  `/*****************`
3.  `递归的要点->1：确定基准情形（即有可能出现的所有情形）2：进行递归`
4.  `******************/`
5.  `//扩展二叉树先序遍历生成二叉树 以0为结束标志 输入时应按先序序列输入，且原本的叶子节点需要用 0 补全`
6.  `BiTree preCreateBiTree(BiTree &root)`
7.  `{`
8.  `elemType e;`
9.  `scanf("%d",&e);`
10. `if(e==0)`
11. `{`
12. `root = NULL;`
13. `}`
14. `else`
15. `{`
16. `root = (BiTree)malloc(sizeof(BiNode));`
17. `root->data = e;`
18. `preCreateBiTree(root->Lchild);`
19. `preCreateBiTree(root->Rchild);`
20. `}`
21. `return root;`
22. `}`

**三种顺序递归式遍历二叉树：**

1.  `//先序遍历二叉树`
2.  `void preTraversalBiTree(BiTree root)`
3.  `{`
4.  `if(root==NULL)`
5.  `{`
6.  `return;`
7.  `}`
8.  `else{`
9.  `printf("%d ",root->data);`
10. `preTraversalBiTree(root->Lchild);`
11. `preTraversalBiTree(root->Rchild);`
12. `}`
13. `}`
14.  
15. `//中序遍历二叉树`
16. `void midTraversalBiTree(BiTree root)`
17. `{`
18. `if(root)`
19. `{`
20. `midTraversalBiTree(root->Lchild);`
21. `printf("%d ",root->data);`
22. `midTraversalBiTree(root->Rchild);`
23. `}`
24. `}`
25.  
26. `//后序遍历二叉树`
27. `void lastTraversalBiTree(BiTree root)`
28. `{`
29. `if(root)`
30. `{`
31. `lastTraversalBiTree(root->Lchild);`
32. `lastTraversalBiTree(root->Rchild);`
33. `printf("%d ",root->data);`
34. `}`
35. `}`

**统计二叉树中结点的数目（递归）：**

1.  `//统计二叉树节点的总数目`
2.  `int calculateNodeOfBiTree(BiTree root)`
3.  `{`
4.  `if(root==NULL)`
5.  `{`
6.  `return 0;`
7.  `}`
8.  `else{`
9.  `return 1+calculateNodeOfBiTree(root->Lchild) + calculateNodeOfBiTree(root->Rchild);`
10. `}`
11. `}`

**递归计算二叉树的深度（约定根节点为第一层）：**

1.  `//统计二叉树的深度 设根节点为第1层`
2.  `int depthOfBiTree(BiTree root)`
3.  `{`
4.  `if(root)`
5.  `{`
6.  `return depthOfBiTree(root->Lchild) > depthOfBiTree(root->Rchild)?depthOfBiTree(root->Lchild)+1:depthOfBiTree(root->Rchild)+1;`
7.  `}`
8.  `else{`
9.  `return 0;`
10. `}`
11. `}`

**统计二叉树中叶子节点数目（递归）：**

1.  `//统计二叉树叶子节点数 递归`
2.  `int calculateLeafNodesOfBiTree(BiTree root)`
3.  `{`
4.  `if(root == NULL)`
5.  `{`
6.  `return 0;`
7.  `}`
8.  `else if((root->Lchild==NULL)&&(root->Rchild==NULL))`
9.  `{`
10. `return 1;`
11. `}`
12. `else{`
13. `return (calculateLeafNodesOfBiTree(root->Lchild) + calculateLeafNodesOfBiTree(root->Rchild));`
14. `}`
15. `}`

***---------------------------------- BiTree    STACK ---------------------------------***

为实现二叉树的非递归操作，需要预先定义可存储二叉树结点的栈（BiTree Stack）

1.  `//定义BiStack节点`
2.  `typedef struct biStack`
3.  `{`
4.  `BiNode *data;`
5.  `struct biStack *next;`
6.  `}BiSNode,*BiStack;`
7.   
8.  `//初始化BiStack`
9.  `void initStack(BiStack &s)`
10. `{`
11. `s = NULL;`
12. `}`
13.  
14. `//判栈空`
15. `int stackIsEmpty(BiStack &s)`
16. `{`
17. `if(s==NULL){return OK;}`
18. `else{return ERROR;}`
19. `}`
20.  
21. `//入栈`
22. `int pushStack(BiStack &s,BiNode *e)`
23. `{`
24. `BiSNode *t = (BiSNode *)malloc(sizeof(BiSNode));`
25. `if(t==NULL){return ERROR;}`
26. `t->data = e;`
27. `t->next = s;`
28. `s = t;`
29. `return OK;`
30. `}`
31.  
32. `//出栈`
33. `int popStack(BiStack &s,BiNode* &e)`
34. `{`
35. `if(stackIsEmpty(s)){return ERROR;}`
36. `BiNode *t = NULL;`
37. `e = s->data;`
38. `s = s->next;`
39. `free(t);`
40. `return OK;`
41. `}`
42.  
43. `//取栈顶元素`
44. `BiNode* getStackTop(BiStack s)`
45. `{`
46. `if(stackIsEmpty(s)){exit(ERROR);}`
47. `return s->data;`
48. `}`
49.  
50. `//计算栈的当前元素个数`
51. `int getStackLength(BiStack s)`
52. `{`
53. `if(stackIsEmpty(s)){return 0;}`
54. `BiSNode *p = s;`
55. `int length = 0;`
56. `while(p)`
57. `{`
58. `length++;`
59. `p = p->next;`
60. `}`
61. `return length;`
62. `}`

**非递归先序遍历：**

1.  `//非递归实现先序遍历`
2.  `/*给定二叉树的根节点R：`
3.  `(a)并将根节点R入栈；`
4.   
5.  `(b)判断栈是否为空，若不为空，取栈顶元素cur访问并出栈。然后先将cur的右子节点入栈，再将cur的左子节点入栈；`
6.   
7.  `(c)重复(b)直到栈为空，则遍历结束。*/`
8.  `void preTraversalBiTreeByStack(BiTree root)`
9.  `{`
10. `if(root==NULL){return ;}`
11. `BiStack s = NULL;`
12. `initStack(s);`
13. `BiNode *cur = NULL;`
14.  
15. `pushStack(s,root);`
16. `while(!stackIsEmpty(s))`
17. `{`
18. `popStack(s,cur);`
19. `printf("%d ",cur->data);`
20. `if(cur->Rchild!=NULL){pushStack(s,cur->Rchild);}`
21. `if(cur->Lchild!=NULL){pushStack(s,cur->Lchild);}`
22. `}`
23. `}`

**非递归中序遍历：**

1.  `/*非递归实现中序遍历`
2.  `对于给定的二叉树根节点R，`
3.  `(a)若其左孩子不为空，循环将R以及R左子树中的所有节点的左孩子入栈；`
4.  `(b)取栈顶元素cur，访问cur并将cur出栈。然后对cur的右子节点进行步骤（a）那样的处理；`
5.  `(c)重复（a）和（b）的操作，直到cur为空切栈或当前所取节点为空为止。*/`
6.  `//中根非递归遍历，需要使用栈`
7.  `void midTraversalBiTreeByStack(BiTree root)`
8.  `{`
9.  `if(root==NULL){return ;}`
10. `BiStack s = NULL;`
11. `initStack(s);`
12.  
13. `while(root||!stackIsEmpty(s))`
14. `{`
15. `while(root)`
16. `{`
17. `pushStack(s,root);`
18. `root = root->Lchild;`
19. `}`
20. `popStack(s,root);`
21. `printf("%d ",root->data);`
22. `root = root->Rchild;`
23. `}`
24. `}`

**非递归后序遍历（此处有两种思路，第一种仅给出思路和参考代码，第二种给出思路和完整代码）：**

1.  `/*非递归后序遍历`
2.  `后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，`
3.  `要保证左孩子和右孩子都已被访问并且左孩子要在右孩子前被访问，`
4.  `才能访问根节点。这就为流程的控制带来了难题。下面介绍两种思路。`
5.  `第一种思路：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，`
6.  `直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。`
7.  `所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，`
8.  `此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，`
9.  `只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。*/`
10.  
11. `//非递归后序遍历，版本1`
12. `/*参考代码：`
13. `void PostOrderTraverse(BiTree T)//非递归后序遍历,用一个标记标记右子树是否访问过`
14. `{`
15. `int flag[20];`
16. `stack<BiTree> Stack;`
17. `if(!T)`
18. `{`
19. `printf("空树！\n");`
20. `return;`
21. `}`
22. `while(T)`
23. `{`
24. `Stack.push(T);`
25. `flag[Stack.size()]=0;`
26. `T=T->lchild;`
27. `}`
28. `while(!Stack.empty())`
29. `{`
30. `T=Stack.top();`
31. `while(T->rchild && flag[Stack.size()]==0)`
32. `{`
33. `flag[Stack.size()]=1;`
34. `T=T->rchild;`
35. `while(T)`
36. `{`
37. `Stack.push(T);`
38. `flag[Stack.size()]=0;`
39. `T=T->lchild;`
40. `}`
41. `}`
42. `T=Stack.top();`
43. `printf("%c",T->data);`
44. `Stack.pop();`
45. `}`
46. `} */`
47.  
48. `/*第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点R，`
49. `（a）先将R入栈。如果P不存在左孩子和右孩子，则可以直接访问它并出栈；`
50. `（b）如果R存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点并出栈；`
51. `（c）若非上述两种情况，则将R的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在父结点前面被访问。*/`
52.  
53. `//非递归后根遍历,版本2`
54. `void lastTraversalBiTreeByStack(BiTree root)`
55. `{`
56. `if(root==NULL){return;}`
57.  
58. `BiStack s = NULL;`
59. `initStack(s);`
60. `BiNode *cur = NULL; //当前结点`
61. `BiNode *pre = NULL; //前一次访问的结点`
62. `pushStack(s,root);`
63. `while(!stackIsEmpty(s))`
64. `{`
65. `cur = getStackTop(s);`
66. `if((cur->Lchild==NULL&&cur->Rchild==NULL)||(pre!=NULL&&(pre==cur->Lchild||pre==cur->Rchild))) //在判断当前节点时，左孩子和右孩子都在根结点前已经被访问`
67. `{`
68. `printf("%d ",cur->data); //如果当前结点没有孩子结点或者孩子节点都已被访问过`
69. `popStack(s,cur);`
70. `pre = cur;`
71. `}`
72. `else`
73. `{`
74. `if(cur->Rchild!=NULL)`
75. `pushStack(s,cur->Rchild);`
76. `if(cur->Lchild!=NULL)`
77. `pushStack(s,cur->Lchild);`
78. `}`
79. `}`
80. `}`

**基于深度优先搜索算法统计二叉树节点总数目(先序遍历) 非递归 基于栈：**

1.  `void calculateNodeOfBiTreeByStack(BiTree root)`
2.  `{`
3.  `if(root==NULL){exit(ERROR);}`
4.   
5.  `BiStack s = NULL;`
6.  `initStack(s);`
7.  `BiNode * cur = NULL;`
8.  `int count = 0;`
9.   
10. `pushStack(s,root);`
11. `while(!stackIsEmpty(s))`
12. `{`
13. `popStack(s,cur);`
14. `count++;`
15. `if(cur->Lchild!=NULL){pushStack(s,cur->Lchild);}`
16. `if(cur->Rchild!=NULL){pushStack(s,cur->Rchild);}`
17. `}`
18. `printf("The number of all nodes :");`
19. `printf("%d\n",count);`
20. `}`

**基于深度优先计算二叉树深度 栈（中序遍历）：**

1.  `void depthOfTreeByStack(BiTree root)`
2.  `{`
3.  `if(root==NULL){return ;}`
4.  `BiStack s = NULL;`
5.  `initStack(s);`
6.  `int depth = 0;`
7.   
8.  `while(root||!stackIsEmpty(s))`
9.  `{`
10. `while(root)`
11. `{`
12. `pushStack(s,root);`
13. `root = root->Lchild;`
14. `}`
15. `depth = depth>getStackLength(s)?depth:getStackLength(s);`
16. `popStack(s,root);`
17. `root = root->Rchild;`
18. `}`
19. `printf("%d\n",depth);`
20. `}`

***为实现对二叉树的广度优先搜索算法，需要预先定义可存放二叉树节点的队列---------------------------------（queue）-----------------------------------------***

1.  `//队列节点 存放BiTree指针`
2.  `typedef struct biQNode`
3.  `{`
4.  `BiNode *data;`
5.  `struct biQNode *next;`
6.  `} BiQNode,*BiTreeQueue;`
7.   
8.  `typedef struct biPointer`
9.  `{`
10. `BiTreeQueue front;`
11. `BiTreeQueue rear;`
12. `}linkBiQueue;`
13.  
14. `//初始化指针 注意初始化队列前应先初始化头尾指针`
15. `linkBiQueue* initPointer()`
16. `{`
17. `linkBiQueue *point = (linkBiQueue*)malloc(sizeof(biPointer));`
18. `if(point==NULL){return NULL;`
19. `printf("Init Queue Pointer Failed!\n");}`
20. `return point;`
21. `}`
22.  
23. `//初始化队列`
24. `int initQueue(linkBiQueue* &Queue)`
25. `{`
26. `Queue->front = Queue->rear = (BiTreeQueue)malloc(sizeof(biQNode));`
27. `if(Queue->front == NULL){return ERROR; }`
28. `Queue->front->next = Queue->rear->next = NULL;`
29. `return OK;`
30. `}`
31.  
32. `//销毁队列`
33. `int destroyQueue(linkBiQueue* &Queue)`
34. `{`
35. `while(Queue->front)`
36. `{`
37. `Queue->rear = Queue->front->next;`
38. `free(Queue->front);`
39. `Queue->front = Queue->rear;`
40. `}`
41. `free(Queue);`
42. `return OK;`
43. `}`
44.  
45. `//队列判空`
46. `int queueIsEmpty(linkBiQueue* &Queue)`
47. `{`
48. `if(Queue->front == Queue->rear){return OK;}`
49. `else{return ERROR;}`
50. `}`
51.  
52. `//将元素插入队列`
53. `int pushQueue(linkBiQueue* &Queue,BiNode *e)`
54. `{`
55. `BiTreeQueue p = (BiTreeQueue)malloc(sizeof(BiQNode));`
56. `if(p==NULL){return ERROR; }`
57. `p->data = e;`
58. `p->next = NULL;`
59. `Queue->rear->next = p;`
60. `Queue->rear = p;`
61. `Queue->rear->next = NULL;`
62. `return OK;`
63. `}`
64.  
65. `//出队`
66. `int popQueue(linkBiQueue* &Queue,BiNode* &e)`
67. `{`
68. `if(queueIsEmpty(Queue)){return ERROR; }`
69. `BiTreeQueue p = Queue->front->next;`
70. `e = p->data;`
71. `if(Queue->rear==Queue->front->next){Queue->rear = Queue->front;`
72. `Queue->front->next = NULL;}`
73. `else{Queue->front->next = Queue->front->next->next;}`
74. `free(p);`
75. `return OK;`
76. `}`
77.  
78. `//求队列长度`
79. `int getQueueLength(linkBiQueue* &Queue)`
80. `{`
81. `if(queueIsEmpty(Queue)){return 0;}`
82. `int length = 0;`
83. `BiTreeQueue p = Queue->front->next;`
84. `while(p)`
85. `{`
86. `length++;`
87. `p = p->next;`
88. `}`
89. `return length;`
90. `}`

**基于以上队列的二叉树层次遍历：**

1.  `//用队列实现二叉树的层次遍历`
2.  `/*（1）首先把二叉树的根节点送入队列；`
3.  `2）队首的节点出队列并访问之，然后把它的左子节点和右子节点分别入队列；`
4.  `（3）重复上面两步操作，直至队空*/`
5.  `void breadthTraversalBiTree(BiTree root)`
6.  `{`
7.  `if(root==NULL){return ;}`
8.  `linkBiQueue* Queue = initPointer(); //初始化队列指针`
9.  `initQueue(Queue); //初始化队列`
10.  
11. `BiNode *e = NULL;`
12. `pushQueue(Queue,root);`
13. `while(!queueIsEmpty(Queue))`
14. `{`
15. `popQueue(Queue,e);`
16. `printf("%d ",e->data);`
17. `if(e->Lchild!=NULL){pushQueue(Queue,e->Lchild);}`
18. `if(e->Rchild!=NULL){pushQueue(Queue,e->Rchild);}`
19. `}`
20. `destroyQueue(Queue); //队列用完后将队列销毁`
21. `}`

**用以上队列实现基于广度优先的非递归计算二叉树叶子节点 非递归：**

1.  `//用队列实现基于广度优先的非递归计算二叉树叶子节点 非递归`
2.  `/*算法思想`
3.  `（1）首先把二叉树的根节点送入队列`
4.  `（2）队首元素出队列，若其左子树和右子树均为空，则将计数变量加1，否则将其左子树和右子树分别送入队列`
5.  `（3）重复（1）（2）操作直至队空，输出计数变量即为所求*/`
6.  `void bradthCalculateLeafNode(BiTree root)`
7.  `{`
8.  `if(root==NULL){return ;}`
9.  `linkBiQueue* Queue = initPointer();`
10. `initQueue(Queue);`
11. `int count = 0;`
12. `BiNode *e = NULL;`
13.  
14. `pushQueue(Queue,root);`
15. `while(!queueIsEmpty(Queue))`
16. `{`
17. `popQueue(Queue,e);`
18. `if(e->Lchild==NULL&&e->Rchild==NULL){count++;}`
19. `else {`
20. `if(e->Lchild!=NULL){pushQueue(Queue,e->Lchild);}`
21. `if(e->Rchild!=NULL){pushQueue(Queue,e->Rchild);}`
22. `}`
23. `}`
24. `destroyQueue(Queue);`
25. `printf("The number of leaf nodes:");`
26. `printf("%d\n",count);`
27. `}`

**广度优先统计二叉树中所有节点个数 非递归 通过队列：**

1.  `//广度优先统计二叉树中所有节点个数 非递归 通过队列`
2.  `void bradthCalculateNodeOfBiTree(BiTree root)`
3.  `{`
4.  `if(root==NULL){exit(ERROR);}`
5.  `linkBiQueue* Queue = initPointer();`
6.  `initQueue(Queue);`
7.  `int count = 0;`
8.  `BiNode* e = NULL;`
9.   
10. `pushQueue(Queue,root);`
11. `while(!queueIsEmpty(Queue))`
12. `{`
13. `popQueue(Queue,e);`
14. `count++;`
15. `if(e->Lchild!=NULL){pushQueue(Queue,e->Lchild);}`
16. `if(e->Rchild!=NULL){pushQueue(Queue,e->Rchild);}`
17. `}`
18. `destroyQueue(Queue);`
19. `printf("The number of all nodes:");`
20. `printf("%d\n",count);`
21. `}`

**广度优先计算二叉树的深度 基于队列 非递归：**

1.  `//广度优先计算二叉树的深度 基于队列 非递归`
2.  `void breadthDepthOfTree(BiTree root)`
3.  `{`
4.  `if(root==NULL){exit(ERROR);}`
5.  `linkBiQueue* Queue = initPointer();`
6.  `initQueue(Queue);`
7.  `BiNode *cur = NULL;`
8.  `int depth = 0;`
9.  `int length = 0;`
10.  
11. `pushQueue(Queue,root);`
12. `while(!queueIsEmpty(Queue))`
13. `{`
14. `length = getQueueLength(Queue);`
15. `depth++;`
16. `while(length--)`
17. `{`
18. `popQueue(Queue,cur);`
19. `if(cur->Lchild!=NULL){pushQueue(Queue,cur->Lchild);}`
20. `if(cur->Rchild!=NULL){pushQueue(Queue,cur->Rchild);}`
21. `}`
22. `}`
23. `printf("%d\n",depth);`
24. `}`

**测试代码：**

1.  `int main()`
2.  `{`
3.  `/*BiStack s = NULL;`
4.  `initStack(s);`
5.  `BiNode *t1 = (BiNode *)malloc(sizeof(BiNode));`
6.  `t1->data = 1;`
7.  `BiNode *t2 = (BiNode *)malloc(sizeof(BiNode));`
8.  `t2->data = 2;`
9.  `pushStack(s,t1);`
10. `pushStack(s,t2);`
11. `BiNode *et;`
12. `popStack(s,et);`
13. `printf("%d\n",et->data);`
14. `popStack(s,et);`
15. `printf("%d\n",et->data);*/`
16.  
17. `/*linkBiQueue* que = initPointer();`
18. `initQueue(que);`
19. `BiNode *t1 = (BiNode *)malloc(sizeof(BiNode));`
20. `t1->data = 1;`
21. `BiNode *t2 = (BiNode *)malloc(sizeof(BiNode));`
22. `t2->data = 2;`
23. `pushQueue(que,t1);`
24. `pushQueue(que,t2);`
25. `BiNode * et;`
26. `popQueue(que,et);`
27. `printf("%d\n",et->data);`
28. `popQueue(que,et);`
29. `printf("%d\n",et->data);`
30. `destroyQueue(que);*/`
31.  
32. `BiTree tree;`
33. `printf("请按先序序列输入扩展二叉树：\n") ; //参考数据 12 13 15 0 0 0 14 16 0 0 19 0 0`
34. `preCreateBiTree(tree);`
35. `preTraversalBiTree(tree);`
36. `printf("\n");`
37. `midTraversalBiTree(tree);`
38. `printf("\n");`
39. `lastTraversalBiTree(tree);`
40. `printf("\n");`
41. `printf("%d",calculateNodeOfBiTree(tree));`
42. `printf("\n");`
43. `printf("%d",depthOfBiTree(tree));`
44. `printf("\n");`
45. `printf("%d",calculateLeafNodesOfBiTree(tree));`
46. `printf("\n");`
47. `breadthTraversalBiTree(tree);`
48. `printf("\n");`
49. `bradthCalculateLeafNode(tree);`
50. `preTraversalBiTreeByStack(tree);`
51. `printf("\n");`
52. `midTraversalBiTreeByStack(tree);`
53. `printf("\n");`
54. `lastTraversalBiTreeByStack(tree);`
55. `printf("\n");`
56. `calculateNodeOfBiTreeByStack(tree);`
57. `bradthCalculateNodeOfBiTree(tree);`
58. `depthOfTreeByStack(tree);`
59. `breadthDepthOfTree(tree);`
60. `findRoadInBiTree(tree,19);`
61. `findRoadInBiTree(tree,16);`
62. `findRoadInBiTree(tree,15);`
63. `findRoadInBiTree(tree,14);`
64. `findRoadInBiTree(tree,20);`
65.  
66. `//STACK s;`
67. `//initStack(s);`
68. `//pushStack(s,10);`
69. `//pushStack(s,12);`
70. `//popStack(s);`
71. `//clearStack(s);`
72. `//popStack(s);`
73.  
74. `return 0;`
75. `}`

[https://blog.csdn.net/cswfqxs\_/article/details/80457502][https_blog.csdn.net_cswfqxs_article_details_80457502]

# 二叉树三种遍历算法递归和非递归实现 (C++语言实现) #

2016年02月28日 10:49:01 [一支兰州][Link 18] 阅读数：1391更多

个人分类： [复习总结][Link 19]

//二叉树 三种遍历方式的 递归非递归实现

\#include  
\#include

using namespace std;

typedef struct BiTreeNode  
\{

int data;  
    BiTreeNode \*left;  
    BiTreeNode \*right;

BiTreeNode()  
    \{  
       left = NULL;  
       right =NULL;  
    \}  
\}BitTreeNode,\*LinkBiTree;

//--------------------先序  
void preTraverse( LinkBiTree root) //先序--非递归  
\{  
   if(root == NULL)  
    return ;

BiTreeNode \*p = root;  
   stack stNode;

while( p!=NULL || !stNode.empty() )  
   \{  
        while(p != NULL)  
        \{  
           cout << p->data << " ";

stNode.push(p);//将每一个遍历的节点入栈，用于遍历右孩子  
           p=p->left;  
        \}

p=stNode.top();//取栈顶元素  
        stNode.pop();//出栈

p = p->right;  
   \}  
\}

void preTraverse2(LinkBiTree root) //先序--递归  
\{  
   if(root == NULL)  
      return;

BiTreeNode \*p = root;

cout << p->data << " ";  
    
   preTraverse2(p->left);

preTraverse2(p->right);  
\}

//------中序  
void MidTraverse( LinkBiTree root) //中序--非递归  
\{  
   if(root == NULL)  
    return;  
    
   BiTreeNode \*p=root;  
   stack stNode;

while( p!= NULL || !stNode.empty() )  
   \{  
       while(p!=NULL)  
       \{  
           stNode.push(p);//从根节点到最左边叶子节点入栈  
           p=p->left;  
       \}  
       p =stNode.top();//取栈顶元素  
       
       cout << p->data << " ";

stNode.pop();//出栈  
       p=p->right;  
   \}  
\}

void MidTraverse2(LinkBiTree root) //中序--递归  
\{  
   if(root == NULL)  
      return;  
    
   BiTreeNode \*p = root;

MidTraverse2(p->left);  
    
   cout << p->data << " ";

MidTraverse2(p->right);  
\}

void postTraverse( LinkBiTree root)//后序 非递归  
\{  
    if(root == NULL)  
        return;  
   
    stack stNode;   
    BiTreeNode \*p = root;  
    BiTreeNode \*pre = NULL;//记录上次出栈的节点，若是当前节点的右孩子，当前节点出栈，若不是，将当 前节点的右孩子入栈

while(p!=NULL || !stNode.empty())  
    \{  
          while(p!=NULL)//从根节点开始到最左边叶子节点入栈  
          \{  
             stNode.push(p);  
             p=p->left;  
           \}  
          p=stNode.top();  
          
          if(p->right!= NULL && p->right != pre)//存在右孩子，并且有孩子没有入栈（还没访问过）  
          \{  
             p=p->right;  
          \}  
          else  
          \{  
              cout << p->data << " ";  
              pre = stNode.top(); //记录本次出栈的元素  
              stNode.pop();  
              p=NULL;//防止再次入栈  
          \}  
     \}  
\}

void postTraverse2(LinkBiTree root)//后序-递归  
\{  
   if(root == NULL)  
    return ;  
   BiTreeNode \*p = root;  
    
   postTraverse2(p->left);

postTraverse2(p->right);

cout << p->data << " ";  
\}

int main()  
\{   
    BiTreeNode \*node = new BiTreeNode\[5\];  
    BiTreeNode \*root = node;

root->left = &node\[1\];  
    root->right = &node\[2\];  
    node\[1\].right = &node\[3\];  
    node\[3\].left = &node\[4\];

for(int i=0;i!=5;++i)  
        node\[i\].data = i;

preTraverse(root);  
     preTraverse2(root);

cout <<endl;

MidTraverse(root);  
    MidTraverse2(root);  
   
    cout <<endl;

postTraverse(root);  
    postTraverse2(root);  
    return 0;  
\}

[https://blog.csdn.net/w616589292/article/details/50759122][https_blog.csdn.net_w616589292_article_details_50759122]

[Link 1]: https://www.cnblogs.com/pkg313133/
[Link 2]: https://www.cnblogs.com/
[Link 3]: https://i.cnblogs.com/EditPosts.aspx?opt=1
[Link 4]: https://msg.cnblogs.com/send/%E6%88%91%E9%9D%9E%E8%8B%B1%E9%9B%84
[Link 5]: https://i.cnblogs.com/
[Link 6]: /images/20220402/f3931cf778cc46b68acb6cc8481fd8f9.png
[20181228120453921]: https://img-blog.csdnimg.cn/20181228120453921
[Link 7]: https://www.cnblogs.com/pkg313133/p/3459171.html
[20181228120453968]: /images/20220402/3f7ae5ee2e304e3f9f1a5b830dc42fe0.png
[201812281204549]: /images/20220402/3c4ad4fad9304e52ac36d0c46a5eb881.png
[20181228120454542]: /images/20220402/842761ebd85649e8baf6415f14c18d63.png
[20181228120454583]: /images/20220402/267835f51d33458fa525d690243d211a.png
[Link 8]: https://www.cnblogs.com/pkg313133/tag/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/
[Link 9]: https://www.cnblogs.com/pkg313133/tag/%E9%98%9F%E5%88%97/
[Link 10]: https://www.cnblogs.com/pkg313133/tag/%E4%BA%8C%E5%8F%89%E6%A0%91/
[Link 11]: https://www.cnblogs.com/pkg313133/tag/%E9%81%8D%E5%8E%86/
[Link 12]: https://www.cnblogs.com/pkg313133/tag/%E9%80%92%E5%BD%92/
[Link 13]: https://www.cnblogs.com/pkg313133/tag/%E9%9D%9E%E9%80%92%E5%BD%92/
[20181228120454623]: https://img-blog.csdnimg.cn/20181228120454623
[20181228120454662]: /images/20220402/e1bf567a28164fc5b5e67b27e43f6e3d.png
[20181228120454704]: /images/20220402/633bd3f4a6bc42a3a8d6e1ecd3b7b7ac.png
[20181228120454704 1]: http://home.cnblogs.com/u/pkg313133/
[- 58]: http://home.cnblogs.com/u/pkg313133/followees
[- 6]: http://home.cnblogs.com/u/pkg313133/followers
[Link 14]: https://www.cnblogs.com/pkg313133/p/3458986.html
[Link 15]: https://i.cnblogs.com/EditPosts.aspx?postid=3459171
[Link 16]: https://www.cnblogs.com/pkg313133/p/3459171.html#
[zhuoya]: https://me.csdn.net/zhuoya_
[70]: /images/20220402/43c2f51ba2354858b7191c63cf265955.png
[70 1]: /images/20220402/95c14cfdbcf1401c9811ea7f609272e5.png
[70 2]: /images/20220402/7dc85394c49942bf9943a87647df3102.png
[https_blog.csdn.net_zhuoya_article_details_80459751]: https://blog.csdn.net/zhuoya_/article/details/80459751
[Link 17]: https://me.csdn.net/cswfqxs_
[https_blog.csdn.net_cswfqxs_article_details_80457502]: https://blog.csdn.net/cswfqxs_/article/details/80457502
[Link 18]: https://me.csdn.net/w616589292
[Link 19]: https://blog.csdn.net/w616589292/article/category/5829137
[https_blog.csdn.net_w616589292_article_details_50759122]: https://blog.csdn.net/w616589292/article/details/50759122