二叉樹遍歷算法總結
本文根據《數據結構與算法》(C語言版)(第三版) 整理。
void PreOrderTraverse(BiTree BT) { if(BT) { printf("%c",BT->data); //訪問根結點 PreOrderTraverse(BT->lchild); //前序遍歷左子樹 PreOrderTraverse(BT->rchild); //前序遍歷右子樹 } }
(1)當樹為空時,將指針p指向根結點,p為當前結點指針。
(2)先訪問當前結點p,並將p壓入棧S中。
(3)令p指向其左孩子。
(4)重復執行步驟(2)、(3),直到p為空為止。
(5)從棧S中彈出棧頂元素,將p指向此元素的右孩子。
(6)重復執行步驟(2)~(5),直到p為空並且棧S也為空。
(7)遍歷結束。
使用棧的前序遍歷的非遞歸算法:
void PreOrderNoRec(BiTree BT) { stack S; BiTree p=BT->root; while((NULL!=p)||!StackEmpty(S)) { if(NULL!=p) { printf("%c",p->data); Push(S,p); p=p->lchild; } else { p=Top(S); Pop(S); p=p->rchild; } } }
void PreOrder(pBinTreeNode pbnode) { pBinTreeNode stack[100]; pBinTreeNode p; int top; top=0; p=pbnode; do { while(p!=NULL) { printf("%d\n",p->data); //訪問結點p top=top+1; stack[top]=p; p=p->llink; //繼續搜索結點p的左子樹 } if(top!=0) { p=stack[top]; top=top-1; p=p->rlink; //繼續搜索結點p的右子樹 } }while((top!=0)||(p!=NULL)); }
void InOrderTraverse(BiTree BT) { if(BT) { InOrderTraverse(BT->lchild); //中序遍歷左子樹 printf("%c",BT->data); //訪問根結點 InOrderTraverse(BT->rchild); //中序遍歷右子樹 } }
void IneOrderNoRec(BiTree BT) { stack S; BiTree p=BT->root; while((NULL!=p)||!StackEmpty(S)) { if(NULL!=p) { Push(S,p); p=p->lchild; } else { p=Top(S); Pop(S); printf("%c",p->data); p=p->rchild; } } }
void InOrder(pBinTreeNode pbnode) { pBinTreeNode stack[100]; pBinTreeNode p; int top; top=0; p=pbnode; do { while(p!=NULL) { top=top+1; stack[top]=p; //結點p進棧 p=p->llink; //繼續搜索結點p的左子樹 } if(top!=0) { p=stack[top]; //結點p出棧 top=top-1; printf("%d\n",p->data); //訪問結點p p=p->rlink; //繼續搜索結點p的右子樹 } }while((top!=0)||(p!=NULL)); }
void PostOrderTraverse(BiTree BT) { if(BT) { PostOrderTraverse(BT->lchild); //後序遍歷左子樹 PostOrderTraverse(BT->rchild); //後序遍歷右子樹 printf("%c",BT->data); //訪問根結點 } }
void PostOrderNoRec(BiTree BT) { stack S; stack tag; BiTree p=BT->root; while((NULL!=p)||!StackEmpty(S)) { while(NULL!=p) { Push(S,p); Push(tag,0); p=p->lchild; } if(!StackEmpty(S)) { if(Pop(tag)==1) { p=Top(S); Pop(S); printf("%c",p->data); Pop(tag); //棧tag要與棧S同步 } else { p=Top(S); if(!StackEmpty(S)) { p=p->rchild; Pop(tag); Push(tag,1); } } } } }
void PosOrder(pBinTreeNode pbnode) { pBinTreeNode stack[100]; //結點的指針棧 int count[100]; //記錄結點進棧次數的數組 pBinTreeNode p; int top; top=0; p=pbnode; do { while(p!=NULL) { top=top+1; stack[top]=p; //結點p首次進棧 count[top]=0; p=p->llink; //繼續搜索結點p的左子樹 } p=stack[top]; //結點p出棧 top=top-1; if(count[top+1]==0) { top=top+1; stack[top]=p; //結點p首次進棧 count[top]=1; p=p->rlink; //繼續搜索結點p的右子樹 } else { printf("%d\n",p->data); //訪問結點p p=NULL; } }while((top>0)); }
typedef struct node { DataType data; struct node *lchild, *rchild; //左、右孩子指針 int ltag, rtag; //左、右線索 }TBinTNode; //結點類型 typedef TBinTNode *TBinTree;在線索化二叉樹中,一個結點是葉子結點的充分必要條件是其左、右標志均為1.
void InOrderThreading(TBinTree p) { if(p) { InOrderThreading(p->lchild); //左子樹線索化 if(p->lchild) p->ltag=0; else p->ltag=1; if(p->rchild) p->rtag=0; else p->rtag=1; if(*(pre)) //若*p的前驅*pre存在 { if(pre->rtag==1) pre->rchild=p; if(p->ltag==1) p->lchild=pre; } pre=p; //另pre是下一訪問結點的中序前驅 InOrderThreading(p->rchild); //右子樹線索化 } }
TBinTNode *InOrderSuc(BiThrTree p) { TBinTNode *q; if(p->rtag==1) //第①情況 return p->rchild; else //第②情況 { q=p->rchild; while(q->ltag==0) q=q->lchild; return q; } }中序線索化二叉樹求前驅結點的算法:
TBinTNode *InOrderPre(BiThrTree p) { TBinTNode *q; if(p->ltag==1) return p->lchild; else { q=p->lchild; //從*p的左孩子開始查找 while(q->rtag==0) q=q->rchild; return q; } }
void TraversInOrderThrTree(BiThrTree p) { if(p) { while(p->ltag==0) p=p->lchild; while(p) { printf("%c",p->data); p=InOrderSuc(p); } } }