知識點總結報告

知識點：

中序遍歷

（原理）中序遍歷二叉樹過程

（1）中序遍歷左子樹

（2）訪問根結點

（3）中序遍歷右子樹

　　中序遍歷遞歸算法

void InOrder(BTNode *b)???????? //中序遍歷的遞歸算法

{　　if (b!=NULL)

　　{　　InOrder(b->lchild);???? //遞歸訪問左子樹

?　　　　?printf("%c ",b->data);? //訪問根節點
　　　　??InOrder(b->rchild);???? //遞歸訪問右子樹
?　　}
}

　　中序遍歷非遞歸算法

void InOrder1(BTNode *b)　　　　　　　　　　　　　　//中序遍歷非遞歸算法

{　　BTNode *p;

　　SqStack *st;　　　　　　　　　　　　　　　　　　　//定義一個順序棧指針st

　　InitStack(st);　　　　　　　　　　　　　　　　　　　//初始化棧st

　　p=b;

　　while(!StackEmpty(st)||p!=NULL)

　　{　　while(p!=NULL)　　　　　　　　　　　　　　　//掃描結點p的所有左下結點并進棧

　　　　　{　　Push(st,p);　　　　　　　　　　　　　　//結點p進棧

　　　　　　　p=p->lchild;　　　　　　　　　　　　　　//移動到左孩子

　　　　　}

　　　　　if(!StackEmpty(st))　　　　　　　　　　　　　//若棧不空

　　　　　{　　Pop(st,p);　　　　　　　　　　　　　　//出棧結點p

　　　　　　　　printf("%c",p->data);　　　　　　　　　　//訪問結點p

　　　　　　　p=p->rchild;　　　　　　　　　　　　　　//轉向處理其右子樹

　　　　　}

　　}

　　printf("\n");

　　DestroyStack(st);　　　　　　　　　　　　　　　　//銷毀棧

}　

?

?

后序遍歷

（原理）后序遍歷二叉樹過程

（1）后序遍歷左子樹

（2）后序遍歷右子樹

（3）訪問根結點

　　后序遍歷遞歸算法

void PostOrder(BTNode *b)?????? //后序遍歷的遞歸算法

{　　if (b!=NULL)

　　?{　　PostOrder(b->lchild);?? //遞歸訪問左子樹
??　　　　PostOrder(b->rchild);?? //遞歸訪問右子樹
??　　　　printf("%c ",b->data);? //訪問根節點
?　　}
}

　　后序遍歷非遞歸算法

void PostOrder1(BTNode *b)　　　　　　　　　　　　　　//后序遍歷非遞歸算法

{　　BTNode *p,*r;

　　SqStack *st;　　　　　　　　　　　　　　　　　　　//定義一個順序棧指針st

　　InitStack(st);　　　　　　　　　　　　　　　　　　　//初始化棧st

　　p=b;

　　do

　　{　　while(p!=NULL)　　　　　　　　　　　　　　　//掃描結點p的所有左下結點并進棧

　　　　　{　　Push(st,p);　　　　　　　　　　　　　　//結點p進棧

　　　　　　　p=p->lchild;　　　　　　　　　　　　　　//移動到左孩子

　　　　　}

　　　　　r=NULL;　　　　　　　　　　　　　　　　　　//r指向剛訪問的結點，初始時為空

　　　　　Flag=true;　　　　　　　　　　　　　　　　　　//flag為真表示正在處理棧頂結點

　　　　　while(!StackEmpty(st)&&flag)

　　　　　{　　GetTop(st,p);　　　　　　　　　　　　　　//取出當前的棧頂結點p

　　　　　　　　if(p->rchild==r)　　　　　　　　　　　　　//若結點p的右孩子為空或者為剛剛訪問過的結點

　　　　　　　　{　　printf("%c",p->data);　　　　　　　　//訪問結點p

　　　　　　　　　　Pop(st,p);

　　　　　　　　　　r=p;　　　　　　　　　　　　　　　//r指向剛訪問過的結點

　　　　　　　　}

　　　　　　　　else

　　　　　　　　{　　p=p->rchild;　　　　　　　　　　//轉向處理其右子樹

　　　　　　　　　　flag=false;　　　　　　　　　　　//表示當前不是處理棧頂結點

　　　　　　　　}

　　　　　}

　　}while(!StackEmpty(st));　　　　　　　　　　　　//棧不空循環

　　printf("\n");

　　DestroyStack(st);　　　　　　　　　　　　　　　　　　//銷毀棧

}

?

?

轉載于:https://www.cnblogs.com/li1997/p/8409205.html

總結

以上是生活随笔為你收集整理的中序后序遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。