数据结构——二叉树的遍历
在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。对于二叉树，有先序、中序和后序三种方法，而每一种遍历方法又分为递归遍历与非递归遍历，因为树的定义本身就是递归定义，所以递归容易理解也很简洁，但递归的开销是很大的，所以我们需要了解非递归遍历的方法。
先序遍历访问顺序：根结点——左子结点——右子结点
中序遍历访问顺序：左子结点——根结点——右子结点
后序遍历访问顺序：左子结点——右子结点——根结点
其中最复杂的是后序遍历非递归版本，这里用栈来维护，我们需要保证结点访问时即出栈时该结点左右子结点都已被访问过，并且先访问左子结点，后访问右子结点。
实现代码及测试如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <malloc.h> 6 #include <string> 7 #include <vector> 8 #include <stack> 9 #include <queue> 10 #include <set> 11 #include <map> 12 13 #define FRER() freopen("in.txt", "r", stdin); 14 15 using namespace std; 16 17 //函数状态码定义 18 #define TRUE 1 19 #define FALSE 0 20 #define OK 1 21 #define ERROR 0 22 #define INFEASIBLE -1 23 #define OVERFLOW -2 24 25 typedef int TElemType; 26 typedef int Status; 27 28 typedef struct BiNode { 29 TElemType data; 30 struct BiNode *lchild, *rchild; 31 }BiNode, *BiTree; 32 33 Status CreateBiTree(BiTree &, int [], int &, int); //递归建树 34 35 Status PreOrderTraverse(BiTree); //先序递归遍历 36 Status _PreOrderTraverse(BiTree); //先序非递归遍历 37 Status InOrderTraverse(BiTree); //中序递归遍历 38 Status _InOrderTraverse(BiTree); //中序非递归遍历 39 Status PostOrderTraverse(BiTree); //后续递归遍历 40 Status _PostOrderTraverse(BiTree); //后续非递归遍历 41 42 /* 测试数据 43 15 44 1 2 3 -1 -1 3 7 -1 8 -1 -1 9 -1 -1 -1 45 */ 46 47 int main() 48 { 49 FRER() 50 int n, m, num[100]; 51 while(cin >> n) { 52 for (int i = 0; i < n; ++i) 53 cin >> num[i]; 54 BiTree root; 55 m = 0; 56 CreateBiTree(root, num, m, n); 57 PreOrderTraverse(root); 58 cout << endl; 59 _PreOrderTraverse(root); 60 cout << endl; 61 InOrderTraverse(root); 62 cout << endl; 63 _InOrderTraverse(root); 64 cout << endl; 65 PostOrderTraverse(root); 66 cout << endl; 67 _PostOrderTraverse(root); 68 cout << endl; 69 } 70 return 0; 71 } 72 73 Status CreateBiTree(BiTree &root, int num[], int &idx, int n) { 74 if(idx >= n || num[idx] == -1) 75 root = NULL; 76 else { 77 if(!(root = (BiNode *)malloc(sizeof(BiNode)))) 78 exit(OVERFLOW); 79 root->data = num[idx]; 80 CreateBiTree(root->lchild, num, ++idx, n); 81 CreateBiTree(root->rchild, num, ++idx, n); 82 } 83 return OK; 84 } 85 86 Status PreOrderTraverse(BiTree root) { 87 if(root == NULL) 88 return OK; 89 cout << root->data << ' '; 90 PreOrderTraverse(root->lchild); 91 PreOrderTraverse(root->rchild); 92 return OK; 93 } 94 95 Status _PreOrderTraverse(BiTree root) { 96 stack<BiNode *> q; 97 BiNode *p = root; 98 while(p != NULL || !q.empty()) { 99 if(p != NULL) { 100 cout << p->data << ' '; 101 q.push(p->rchild); 102 p = p->lchild; 103 } 104 else { 105 p = q.top(); 106 q.pop(); 107 } 108 } 109 return OK; 110 } 111 112 Status InOrderTraverse(BiTree root) { 113 if(root == NULL) 114 return OK; 115 InOrderTraverse(root->lchild); 116 cout << root->data << ' '; 117 InOrderTraverse(root->rchild); 118 return OK; 119 } 120 121 Status _InOrderTraverse(BiTree root) { 122 stack<BiNode *> q; 123 BiNode *p = root; 124 while(p != NULL || !q.empty()) { 125 if(p != NULL) { 126 q.push(p); 127 p = p->lchild; 128 } 129 else { 130 p = q.top(); 131 q.pop(); 132 cout << p->data << ' '; 133 p = p->rchild; 134 } 135 } 136 return OK; 137 } 138 139 Status PostOrderTraverse(BiTree root) { 140 if(root == NULL) 141 return OK; 142 PostOrderTraverse(root->lchild); 143 PostOrderTraverse(root->rchild); 144 cout << root->data << ' '; 145 return OK; 146 } 147 148 Status _PostOrderTraverse(BiTree root) { 149 stack<BiNode *> q; 150 BiNode *p = root, *pre = NULL; 151 q.push(root); 152 while(!q.empty()) { 153 p = q.top(); 154 if((p->lchild == NULL && p->rchild == NULL) || (pre != NULL && (pre == p->lchild || pre == p->rchild))) { //该节点左右子节点都被访问过 155 cout << p->data << ' '; 156 q.pop(); 157 pre = p; 158 } 159 else { 160 if(p->rchild != NULL) 161 q.push(p->rchild); 162 if(p->lchild != NULL) 163 q.push(p->lchild); 164 } 165 } 166 return OK; 167 }
版权声明：本文为fan-jiaming原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。