二叉樹遍歷及C語言實現(xiàn)

1、二叉樹遍歷及C語言實現(xiàn)（2009-12-2320:47:26）轉載已知中序和前序序列，或者已知中序和后序序列，都能夠構造一棵二叉樹。在本例中，本人用C語言寫程序解答了下面兩個算法題：（1）給出一棵二叉樹的中序與后序遍歷序列，求出它的先序遍歷序列。（2）給出一棵二叉樹的中序與先序遍歷序列，求出它的后序遍歷序列。知識點扼要回顧：所謂二叉樹的遍歷，是指按一定的順序對二叉樹中的每個結點均訪問一次，且僅訪問一。按照根結點訪問位置的不同，通常把二叉樹的遍歷分為六種：TLR（根左右），TRL（根右左），LTR（左根右）RTL（右根左），LRT（左右根），RLT（右左根）其中，TRL、RTL和RLT三種順序在

2、左右子樹之間均是先右子樹后左子樹，這與人們先左后右的習慣不同，因此，往往不予采用。余下的三種順序TLR、LTR和LRT根據(jù)根訪問的位置不同分別被稱為前序遍歷、中序遍歷和后序遍歷。前序遍歷的規(guī)律是：輸出根結點，輸出左子樹，輸出右子樹；中序遍歷的規(guī)律是：輸出左子樹，輸出根結點，輸出右子樹；后序遍歷的規(guī)律是：輸出左子樹，輸出右子樹，輸出根結點；不多說了，看代碼吧：）#include#includeusingnamespacestd;/存儲節(jié)點數(shù)據(jù)，為簡便起見，這里選用字符typedefcharDATA_TYPE;typedefstructtagBINARY_TREE_NODEBINARY_TREE_

3、NODE，*LPBINARY_TREE_NODE;structtagBINARY_TREE_NODEDATA_TYPEdata;/節(jié)點數(shù)據(jù)LPBINARY_TREE_NODEpLeftChild;/左孩子指針LPBINARY_TREE_NODEpRightChild;/右孩子指針;/函數(shù)名稱：TreeFromMidPost/函數(shù)功能：給出一棵二叉樹的中序與后序序列，構造這棵二叉樹。輸入?yún)?shù)：LPBINARY_TREE_NODE&lpNode：二叉樹的結點/stringmid:存儲了二叉樹的中序序列的字符串/stringpost:存儲了二叉樹的后序序列的字符串/intlm,intrm：二叉樹的中

4、序序列在數(shù)組mid中的左右邊界/intlp,intrp：二叉樹的后序序列在數(shù)組post中的左右邊界/voidTreeFromMidPost(LPBINARY_TREE_NODE&lpNode,stringmid,stringpost,intlm,intrm,intlp,intrp)/構造二叉樹結點lpNode=newBINARY_TREE_NODE;lpNode-data=postrp;lpNode-pLeftChild=NULL;lpNode-pRightChild=NULL;intpos=lm;while(midpos!=postrp)pos+;intiLeftChildLen=pos-l

5、m;if(poslm)有左孩子，遞歸構造左子樹TreeFromMidPost(lpNode-pLeftChild,mid,post,lm,pos-1,lp,lp+iLeftChildLen-1);if(pospRightChild,mid,post,pos+1,rm,lp+iLeftChildLen,rp-1);/函數(shù)名稱：TreeFromMidPre/函數(shù)功能：給出一棵二叉樹的先序與中序序列，構造這棵二叉樹。輸入?yún)?shù):BINARY_TREE_NODE&lpNode：二叉樹的結點/stringmid:存儲了二叉樹的中序序列的字符串/stringpre:存儲了二叉樹的先序序列的字符串/intlm

6、,intrm：二叉樹的中序序列在數(shù)組mid中的左右邊界/intlp,intrp：二叉樹的先序序列在數(shù)組pre中的左右邊界/voidTreeFromMidPre(LPBINARY_TREE_NODE&lpNode,stringmid,stringpre,intlm,intrm,intlp,intrp)/構造二叉樹結點lpNode=newBINARY_TREE_NODE;lpNode-data=prelp;lpNode-pLeftChild=NULL;lpNode-pRightChild=NULL;intpos=lm;while(midpos!=prelp)pos+;intiLeftChildLe

7、n=pos-lm;if(poslm)有左孩子，遞歸構造左子樹TreeFromMidPre(lpNode-pLeftChild,mid,pre,lm,pos-1,lp+1,lp+iLeftChildLen);if(pospRightChild,mid,pre,pos+1,rm,lp+iLeftChildLen+1,rp);/先序遍歷voidPreOrder(LPBINARY_TREE_NODEp)if(p!=NULL)coutdata;/輸出該結點PreOrder(p-pLeftChild);/遍歷左子樹PreOrder(p-pRightChild);/遍歷右子樹/中序遍歷voidMidOrde

8、r(LPBINARY_TREE_NODEp)if(p!=NULL)MidOrder(p-pLeftChild);/遍歷左子樹coutdata;/輸出該結點MidOrder(p-pRightChild);/遍歷右子樹stringstringstringpost;/存儲后序序列/后序遍歷voidPostOrder(LPBINARY_TREE_NODEp)if(p!=NULL)PostOrder(p-pLeftChild);/遍歷左子樹PostOrder(p-pRightChild);/遍歷右子樹coutdata;/輸出該結點/釋放二叉樹voidRelease(LPBINARY_TREE_NODEl

9、pNode)if(lpNode!=NULL)Release(lpNode-pLeftChild);Release(lpNode-pRightChild);deletelpNode;lpNode=NULL;intmain(intargc,char*argv)pre;/存儲先序序列mid;/存儲中序序列LPBINARY_TREE_NODElpRoot;/二叉樹根節(jié)點指針coutvv程序1已知二叉樹的中序與后序序列，求先序序列vvendl;coutvv請先輸入中序序列，回車后輸入后序序列：vvendl;cinmid;cinpost;TreeFromMidPost(lpRoot,mid,post,0,

10、mid.size()-1,0,post.size()-1);coutvv先序遍歷結果：;PreOrder(lpRoot);coutendl;coutvv中序遍歷結果：”；MidOrder(lpRoot);coutpre;cinmid;TreeFromMidPre(lpRoot,mid,pre,0,mid.size()-1,0,pre.size()-1);coutvv先序遍歷結果：;PreOrder(lpRoot);coutvvendl;coutvv中序遍歷結果：;MidOrder(lpRoot);coutvvendl;coutvv后序遍歷結果：;PostOrder(lpRoot);coutvv

11、endl;Release(lpRoot);coutvvendl;system(pause);return0;#includeviostream#includevstringusingnamespacestd;/存儲節(jié)點數(shù)據(jù)，為簡便起見，這里選用字符typedefcharDATA_TYPE;typedefstructtagBINARY_TREE_NODEBINARY_TREE_NODE,*LPBINARY_TREE_NODE;structtagBINARY_TREE_NODEDATA_TYPEdata;/節(jié)點數(shù)據(jù)LPBINARY_TREE_NODEpLeftChild;/左孩子指針LPBINAR

12、Y_TREE_NODEpRightChild;/右孩子指針;/函數(shù)名稱：TreeFromMidPost/函數(shù)功能：給出一棵二叉樹的中序與后序序列，構造這棵二叉樹。輸入?yún)?shù)：LPBINARY_TREE_NODE&lpNode：二叉樹的結點/stringmid:存儲了二叉樹的中序序列的字符串/stringpost:存儲了二叉樹的后序序列的字符串/intlm,intrm：二叉樹的中序序列在數(shù)組mid中的左右邊界/intlp,intrp：二叉樹的后序序列在數(shù)組post中的左右邊界/voidTreeFromMidPost(LPBINARY_TREE_NODE&lpNode,stringmid,strin

13、gpost,intlm,intrm,intlp,intrp)/構造二叉樹結點lpNode=newBINARY_TREE_NODE;lpNode-data=postrp;lpNode-pLeftChild=NULL;lpNode-pRightChild=NULL;intpos=lm;while(midpos!=postrp)pos+;intiLeftChildLen=pos-lm;if(poslm)有左孩子，遞歸構造左子樹TreeFromMidPost(lpNode-pLeftChild,mid,post,lm,pos-1,lp,lp+iLeftChildLen-1);if(pospRightC

14、hild,mid,post,pos+1,rm,lp+iLeftChildLen,rp-1);/函數(shù)名稱：TreeFromMidPre/函數(shù)功能：給出一棵二叉樹的先序與中序序列，構造這棵二叉樹。輸入?yún)?shù):BINARY_TREE_NODE&lpNode：二叉樹的結點/stringmid:存儲了二叉樹的中序序列的字符串/stringpre:存儲了二叉樹的先序序列的字符串/intlm,intrm：二叉樹的中序序列在數(shù)組mid中的左右邊界/intlp,intrp：二叉樹的先序序列在數(shù)組pre中的左右邊界/voidTreeFromMidPre(LPBINARY_TREE_NODE&lpNode,strin

15、gmid,stringpre,intlm,intrm,intlp,intrp)/構造二叉樹結點lpNode=newBINARY_TREE_NODE;lpNode-data=prelp;lpNode-pLeftChild=NULL;lpNode-pRightChild=NULL;intpos=lm;while(midpos!=prelp)pos+;intiLeftChildLen=pos-lm;if(poslm)有左孩子，遞歸構造左子樹TreeFromMidPre(lpNode-pLeftChild,mid,pre,lm,pos-1,lp+1,lp+iLeftChildLen);if(pospR

16、ightChild,mid,pre,pos+1,rm,lp+iLeftChildLen+1,rp);/先序遍歷voidPreOrder(LPBINARY_TREE_NODEp)if(p!=NULL)coutdata;/輸出該結點PreOrder(p-pLeftChild);/遍歷左子樹PreOrder(p-pRightChild);/遍歷右子樹/中序遍歷voidMidOrder(LPBINARY_TREE_NODEp)if(p!=NULL)MidOrder(p-pLeftChild);/遍歷左子樹coutdata;/輸出該結點MidOrder(p-pRightChild);/遍歷右子樹/后序遍

17、歷voidPostOrder(LPBINARY_TREE_NODEp)if(p!=NULL)PostOrder(p-pLeftChild);/遍歷左子樹PostOrder(p-pRightChild);/遍歷右子樹coutdata;/輸出該結點/釋放二叉樹voidRelease(LPBINARY_TREE_NODElpNode)if(lpNode!=NULL)Release(lpNode-pLeftChild);Release(lpNode-pRightChild);deletelpNode;lpNode=NULL;intmain(intargc,char*argv)stringpre;/存儲

18、先序序列stringmid;/存儲中序序列stringpost;/存儲后序序列LPBINARY_TREE_NODElpRoot;/二叉樹根節(jié)點指針coutvv程序1已知二叉樹的中序與后序序列，求先序序列vvendl;coutvv請先輸入中序序列，回車后輸入后序序列：vvendl;cinmid;cinpost;TreeFromMidPost(lpRoot,mid,post,0,mid.size()-1,0,post.size()-1);coutvv先序遍歷結果：；PreOrder(lpRoot);coutvvendl;coutvv中序遍歷結果：；MidOrder(lpRoot);coutvvendl;coutvv后序遍歷結果：；PostOrder(lpRoot);coutvvendl;Release(lpRoot);coutpre;cinmid;TreeFromMidPre(lpRoot,mid,pre,0,mid.size()-1,0,pre.size()-1);coutvv先序遍歷結果：；PreOrder(lpRoot);coutvvendl;coutvv中序遍歷結果：；MidOrder(lpRoot);coutvvendl;coutvv后序遍歷結果：；PostOrde