描述
树的非递归遍历主要是利用栈来模拟递归的实现，跟递归一样，空间复杂度为O(h=lg(n)) （），时间复杂度为O(n)（每个节点都被压入栈一次，弹出栈一次，，访问一次）
前序遍历
前序是先访问，再入栈
void PreorderTraverse(pTree T){if(T == NULL)return;stack<pTree> Stk;Stk.push(T);while(!Stk.empty()){pTree p = Stk.top();Stk.pop();cout << p->data << ” “;if(p->Right != NULL)Stk.push(p->Right);if(p->Left != NULL)Stk.push(p->Left);}}/*前序是先访问，再入栈；1、如果T非空，访问栈顶元素，把T入栈，T指向左儿子。。2、如果T为空，说明已经向左走到尽头了，弹出当前栈顶元素，T指向右儿子。*/void PreorderTraverse2(pTree T){if(T == NULL)return;stack<pTree> Stk;while(T || !Stk.empty()){//如果T非空，访问栈顶元素，把T入栈，T指向左儿子。if(T){cout << T->data << ” “;Stk.push(T);T = T->Left;}//如果T为空，说明已经向左走到尽头了，弹出当前栈顶元素，T指向右儿子。else{T = Stk.top();Stk.pop();T = T->Right;}}}中序遍历
中序遍历则是先入栈，弹栈后再访问。
/*中序则是先入栈，弹栈后再访问。1、如果T非空，则把T入栈，T指向左儿子。2、如果T为空，说明已经向左走到尽头了，弹出当前栈顶元素，进行访问，并把T指向其右儿子。*/void InorderTraverse2(pTree T){if(T == NULL)return;stack<pTree> Stk;while(T || !Stk.empty()){if(T){Stk.push(T);T = T->Left;}else{T = Stk.top();Stk.pop();cout << T->data << ” “;T = T->Right;}}}后序遍历
第一种采用两个栈来实现，跟前序遍历的第一种类似，不过就是先压入当前节点的左子树，后压入当前节点的右子树。得到的顺序是根节点-右子树-左子树，刚好是后序遍历的逆序，所以再利用一个栈解决就可以倒过来。
void PostorderTraverse(pTree T){if(T == NULL)return;stack<pTree> Stk,Stk2;Stk.push(T);while(!Stk.empty()){pTree p = Stk.top();Stk.pop();Stk2.push(p);if(p->Left != NULL)Stk.push(p->Left);if(p->Right != NULL)Stk.push(p->Right);}while(!Stk2.empty()){cout << Stk2.top()->data << ” “;Stk2.pop();}}
第二站采用标记的方法，一直访问左子树并压入栈，直至为空，判断栈顶节点的右子树是否存在或是否已访问过，如果已访问过或不存在，则访问该节点元素，否则指向右子树
void PostorderTraverse3(pTree T){if(T == NULL)return;stack<pTree> Stk;pTree Curr = T;pTree Previsited = NULL;Stk.empty()){){Stk.push(Curr);Curr = Curr->Left;}Curr = Stk.top();Curr->Right == Previsited){cout ;Stk.pop();Previsited = Curr;Curr = NULL;}else{Curr = Curr->Right;}}}层序遍历
层序遍历就是从上到下从左到右访问树的节点。采用FIFO(先进先出)的数据结构-队列
void LeverTraverse(pTree T){if(T == NULL)return;queue<pTree> Que;Que.push(T);while(!Que.empty()){pTree p = Que.front();cout << p->data << ” “;Que.pop();if(p->Left != NULL)Que.push(p->Left);if(p->Right != NULL)Que.push(p->Right);}}
整个测试程序如下
;ElementChar;typedef int Status;typedef struct TreeNode{ElementChar data;struct TreeNode *Left;struct TreeNode *Right;bool bMark;}TreeNode, *pTree;int index = 0;char str[] = “ABDH#K###E##CFI###G#J##”;Status InitTree(pTree *T){*T = NULL;return OK;}Status Visit(pTree T){if(T == NULL)return ERROR;//printf(“%c “,T->data);cout << T->data << ” “;return OK;}int TreeIsEmpty(pTree T){if(T)return FALSE;elsereturn TRUE;}void DeleteTree(pTree *T){if(*T){if((*T)->Left)DeleteTree(&(*T)->Left);if((*T)->Right)DeleteTree(&(*T)->Right);free(*T);*T = NULL;}}void CreateTree(pTree *T){ElementChar ch;ch = str[index++];if(ch == ‘#’)*T = NULL;else{*T = (pTree)malloc(sizeof(TreeNode));if((*T) == NULL)exit(0);(*T)->data = ch;CreateTree(&(*T)->Left);CreateTree(&(*T)->Right);}}void PreorderTraverse1(pTree T){if(T == NULL)return;cout << T->data << ” “;PreorderTraverse1(T->Left);PreorderTraverse1(T->Right);}void InorderTraversel(pTree T){if(T == NULL)return;InorderTraversel(T->Left);cout << T->data << ” “;InorderTraversel(T->Right);}void PostorderTraversel(pTree T){if(T == NULL)return;PostorderTraversel(T->Left);PostorderTraversel(T->Right);cout << T->data << ” “;}void PreorderTraverse3(pTree T){if(T == NULL)return;stack<pTree> Stk;Stk.push(T);while(!Stk.empty()){pTree p = Stk.top();Stk.pop();cout << p->data << ” “;if(p->Right != NULL)Stk.push(p->Right);if(p->Left != NULL)Stk.push(p->Left);}}/*preOrder2每次都将遇到的节点压入栈，当左子树遍历完毕后才从栈中弹出最后一个访问的节点，访问其右子树。在同一层中，不可能同时有两个节点压入栈，因此栈的大小空间为O(h)，h为二叉树高度。时间方面，每个节点都被压入栈一次，弹出栈一次，访问一次，复杂度为O(n)*//*前序是先访问，再入栈；1、如果T非空，访问栈顶元素，把T入栈，T指向左儿子。。2、如果T为空，说明已经向左走到尽头了，弹出当前栈顶元素，T指向右儿子。*/void PreorderTraverse2(pTree T){if(T == NULL)return;stack<pTree> Stk;while(T || !Stk.empty()){//如果T非空，访问栈顶元素，把T入栈，T指向左儿子。if(T){cout << T->data << ” “;Stk.push(T);T = T->Left;}//如果T为空，说明已经向左走到尽头了，弹出当前栈顶元素，T指向右儿子。else{T = Stk.top();Stk.pop();T = T->Right;}}}/*中序则是先入栈，弹栈后再访问。1、如果T非空，则把T入栈，T指向左儿子。2、如果T为空，说明已经向左走到尽头了，弹出当前栈顶元素，进行访问，并把T指向其右儿子。*/void InorderTraverse2(pTree T){if(T == NULL)return;stack<pTree> Stk;while(T || !Stk.empty()){if(T){Stk.push(T);T = T->Left;}else{T = Stk.top();Stk.pop();cout << T->data << ” “;T = T->Right;}}}/*因为后序遍历的顺序是：左子树->右子树->根节点，于是我们在前序遍历的代码中，当访问完当前节点后，先把当前节点的左子树入栈，再把右子树入栈，这样最终得到的顺序为：根节点->右子树->左子树，刚好是后序遍历倒过来的版本，于是把这个结果做一次翻转即为真正的后序遍历。而翻转可以通过使用另外一个栈简单完成，这样的代价是需要两个栈，但就复杂度而言，空间复杂度仍然是O(h)。*/void PostorderTraverse2(pTree T){if(T == NULL)return;stack<pTree> Stk,Stk2;Stk.push(T);while(!Stk.empty()){pTree p = Stk.top();Stk.pop();Stk2.push(p);if(p->Left != NULL)Stk.push(p->Left);if(p->Right != NULL)Stk.push(p->Right);}while(!Stk2.empty()){cout << Stk2.top()->data << ” “;Stk2.pop();}}void PostorderTraverse3(pTree T){if(T == NULL)return;stack<pTree> Stk;pTree Curr = T;pTree Previsited = NULL;while(Curr != NULL || !Stk.empty()){//一直访问左子树，直至为空while(Curr != NULL){Stk.push(Curr);Curr = Curr->Left;}Curr = Stk.top();//当前节点的右子树不存在或已经访问过，则访问该节点if(Curr->Right == NULL || Curr->Right == Previsited){cout << Curr->data << ” “;Stk.pop();Previsited = Curr;Curr = NULL;}else{Curr = Curr->Right;}}}void LeverTraverse(pTree T){if(T == NULL)return;queue<pTree> Que;Que.push(T);while(!Que.empty()){pTree p = Que.front();cout << p->data << ” “;Que.pop();if(p->Left != NULL)Que.push(p->Left);if(p->Right != NULL)Que.push(p->Right);}}int main(){pTree Tree;InitTree(&Tree);CreateTree(&Tree);if(TreeIsEmpty(Tree)){cout << “Tree is Empty!” << endl;}cout << “前序遍历：” << endl;cout << “PreorderTraverse1(递归) is :”;PreorderTraverse1(Tree);cout << endl;cout << “PreorderTraverse2is :”;PreorderTraverse2(Tree);cout << endl;cout << “PreorderTraverse3is :”;PreorderTraverse3(Tree);cout << endl;cout << endl;cout << “中序遍历：” << endl;cout << “InorderTraversel(递归) is :”;InorderTraversel(Tree);cout << endl;cout << “InorderTraverse2is :”;InorderTraverse2(Tree);cout << endl;cout << endl;cout << “后序遍历：” << endl;cout << “PostorderTraversel(递归)is :”;PostorderTraversel(Tree);cout << endl;cout << “PostorderTraverse2(双栈)is :”;PostorderTraverse2(Tree);cout << endl;cout << “PostorderTraverse3is :”;PostorderTraverse3(Tree);cout << endl;cout << endl;cout << “层序遍历：” << endl;cout << “LeverTraverseis :”;LeverTraverse(Tree);cout << endl;return 0;}
运行结果如下：
才能做到人在旅途，感悟人生，享受人生。
