二叉树遍历

递归方式（三种）

// 前序遍历 void PreorderTraversal( BinTree BT ) { if( BT ) { printf("%d ", BT->Data ); PreorderTraversal( BT->Left ); PreorderTraversal( BT->Right ); } } // 中序遍历 void InorderTraversal( BinTree BT ) { if( BT ) { InorderTraversal( BT->Left ); /* 此处假设对BT结点的访问就是打印数据 */ printf("%d ", BT->Data); /* 假设数据为整型 */ InorderTraversal( BT->Right ); } } // 后序遍历 void PostorderTraversal( BinTree BT ) { if( BT ) { PostorderTraversal( BT->Left ); PostorderTraversal( BT->Right ); printf("%d ", BT->Data); } }

非递归 需要利用堆栈，利用了递归的原理，可类比深度优先搜索

// 先序遍历 void PreorderTraversal( BinTree BT ){ BinTree T = BT; stack<BinTree> S; while (T || !S.empty()){ while (T){ S.push(T); printf("%d ", T->Data); T = T->Left; } if (!S.empty()){ T = S.top(); S.pop(); T = T->Right; } } } // 中序遍历 void InorderTraversal( BinTree BT ){ BinTree T = BT; stack<BinTree> S; while (T || !S.empty()){ while (T){ S.push(T); T = T->Left; } if (!S.empty()){ T = S.top(); S.pop(); printf("%d ", T->Data); T = T->Right; } } } // 后序遍历 // 使用两个栈，s和s2。使用 【根->右->左】 的方式，在第一次遇到结点时，就压入栈s2中，那么最后遍历完了，根据栈的性质，s2依次弹出的就是【左->右->根】的后续遍历了 void PostorderTraversal( BinTree BT ){ BinTree T = BT; stack<BinTree> s; stack<ElementType> s2; while (T || !s.empty()){ while (T){ s.push(T); s2.push(T->Data); T = T->Right; } if (!s.empty()){ T = s.top(); s.pop(); T = T->Left; } } while (!sr.empty()){ printf("]", s2.top()); s2.pop(); } }

法二

void PostorderTraversal( BinTree BT ) { BinTree T=BT; BinTree Previous=NULL,Curr=NULL; Stack* S=(Stack*)malloc(sizeof(Stack)); S->top=-1; push(T,S); while(!IsEmpty(S)) { Curr=Top(S); if(Previous==NULL||Curr==Previous->Left||Curr==Previous->Right) { if(Curr->Left) push(Curr->Left,S); else if(Curr->Right) push(Curr->Right,S); } else if(Previous==Curr->Left) { if(Curr->Right) push(Curr->Right,S); } else { printf("%d\n",Curr->Data); pop(S); } Previous=Curr; } }