數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)任課教師：劉晉萍Email：785297343@QQ:

785297343第六講樹(shù)和二叉樹(shù)樹(shù)的基本概念樹(shù)的定義樹(shù)的基本術(shù)語(yǔ)二叉樹(shù)二叉樹(shù)的定義二叉樹(shù)的性質(zhì)二叉樹(shù)的基本操作二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的遍歷樹(shù)與二叉樹(shù)樹(shù)與二叉樹(shù)的轉(zhuǎn)換樹(shù)的遍歷二叉樹(shù)的遍歷二叉樹(shù)的遍歷二叉樹(shù)遍歷的概念二叉樹(shù)的遍歷二叉樹(shù)遍歷的概念二叉樹(shù)遍歷的方法二叉樹(shù)的遍歷二叉樹(shù)遍歷的概念二叉樹(shù)遍歷的方法二叉樹(shù)遍歷的應(yīng)用二叉樹(shù)的遍歷二叉樹(shù)遍歷的概念二叉樹(shù)遍歷的方法二叉樹(shù)遍歷的應(yīng)用二叉樹(shù)遍歷的實(shí)現(xiàn)算法結(jié)束二叉樹(shù)遍歷的概念遍歷的含義訪問(wèn)結(jié)構(gòu)中的所有元素且只訪問(wèn)一次二叉樹(shù)遍歷的定義按一定規(guī)律對(duì)二叉樹(shù)中每個(gè)結(jié)點(diǎn)訪問(wèn)且僅訪問(wèn)一次二叉樹(shù)遍歷的目的在對(duì)二叉樹(shù)的很多處理中，需要二叉樹(shù)結(jié)點(diǎn)的一個(gè)線性序列實(shí)質(zhì)而言，遍歷的目的就是對(duì)二叉樹(shù)進(jìn)行線性化處理，以得到一個(gè)結(jié)點(diǎn)的線性序列對(duì)二叉樹(shù)處理而言，遍歷的目的是為二叉樹(shù)的其他運(yùn)算奠定基礎(chǔ)非線性結(jié)構(gòu)遍歷結(jié)點(diǎn)的訪問(wèn)序列線性化回去二叉樹(shù)遍歷的方法有哪些方法二叉樹(shù)由三個(gè)基本部分組成：根結(jié)點(diǎn)

左子樹(shù)

右子樹(shù)遍歷二叉樹(shù)實(shí)質(zhì)就是完成如下三項(xiàng)工作：訪問(wèn)根結(jié)點(diǎn)D遍歷左子樹(shù)L遍歷右子樹(shù)R這三項(xiàng)工作按順序組合可以得到6種遍歷方案：DLRDRLLDRRDLLRDRLD對(duì)這6種方案加上“先左后右”的限定，則得到如下3種遍歷方案：DLR稱(chēng)為先（根）序遍歷LDR稱(chēng)為中（根）序遍歷LRD稱(chēng)為后（根）序遍歷遍歷方法的描述根左子樹(shù)右子樹(shù)看圖路徑DLRDRLLDRRDLLRDRLDDLRDRLLDRRDLLRDRLDDLR

DRLLDRRDLLRDRLDDLR

DRL

LDR

RDL

LRD

RLD訪問(wèn)根結(jié)點(diǎn)、遍歷左子樹(shù)、遍歷右子樹(shù)訪問(wèn)根結(jié)點(diǎn)、遍歷右子樹(shù)、遍歷左子樹(shù)遍歷左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)、遍歷右子樹(shù)遍歷右子樹(shù)、訪問(wèn)根結(jié)點(diǎn)、遍歷左子樹(shù)遍歷左子樹(shù)、遍歷右子樹(shù)、訪問(wèn)根結(jié)點(diǎn)遍歷右子樹(shù)、遍歷左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)回去二叉樹(shù)遍歷的方法有哪些方法二叉樹(shù)由三個(gè)基本部分組成：根結(jié)點(diǎn)

左子樹(shù)

右子樹(shù)遍歷二叉樹(shù)實(shí)質(zhì)就是完成如下三項(xiàng)工作：訪問(wèn)根結(jié)點(diǎn)D遍歷左子樹(shù)L遍歷右子樹(shù)R這三項(xiàng)工作按順序組合可以得到6種遍歷方案：DLRDRLLDRRDLLRDRLD對(duì)這6種方案加上“先左后右”的限定，則得到如下3種遍歷方案：DLR稱(chēng)為先（根）序遍歷LDR稱(chēng)為中（根）序遍歷LRD稱(chēng)為后（根）序遍歷遍歷方法的描述根左子樹(shù)右子樹(shù)看圖三種遍歷方案的遍歷路徑一樣，只是訪問(wèn)根結(jié)點(diǎn)的時(shí)機(jī)不同二叉樹(shù)遍歷的方法有哪些方法遍歷方法的描述先序遍歷二叉樹(shù)若二叉樹(shù)為空，則空操作；否則

(1)訪問(wèn)根結(jié)點(diǎn)；

(2)先序遍歷左子樹(shù)；

(3)先序遍歷右子樹(shù)。中序遍歷二叉樹(shù)若二叉樹(shù)為空，則空操作；否則

(1)中序遍歷左子樹(shù)；

(2)訪問(wèn)根結(jié)點(diǎn)；

(3)中序遍歷右子樹(shù)。后序遍歷二叉樹(shù)若二叉樹(shù)為空，則空操作；否則

(1)后序遍歷左子樹(shù)；

(2)后序遍歷右子樹(shù);(3)訪問(wèn)根結(jié)點(diǎn)。根左子樹(shù)右子樹(shù)看例先序序列中序序列后序序列（根、左、右）（左、根、右）（左、右、根）二叉樹(shù)遍歷方法例1先序序列中序序列后序序列ABCDEFGHK待遍歷的二叉樹(shù)根右子樹(shù)左子樹(shù)ABCEFGDHK回去CDBAEHGKFDCBHKGFEA二叉樹(shù)遍歷的應(yīng)用輸出二叉樹(shù)中的所有結(jié)點(diǎn)輸出二叉樹(shù)中的葉子結(jié)點(diǎn)求二叉樹(shù)的深度對(duì)每一個(gè)應(yīng)用問(wèn)題：確定“訪問(wèn)”的具體操作是什么分析對(duì)遍歷順序的要求，確定用先序遍歷、中序遍歷還是后序遍歷給出解決問(wèn)題的算法描述思考練習(xí)：用何種遍歷實(shí)現(xiàn)對(duì)二叉樹(shù)左右子樹(shù)的交換？在交換二叉樹(shù)左右子樹(shù)的遍歷中，“訪問(wèn)”操作是什么？寫(xiě)出一個(gè)實(shí)現(xiàn)二叉樹(shù)左右子樹(shù)交換的算法描述。回去先序遍歷二叉樹(shù)若二叉樹(shù)為空，則空操作；

否則，依次做如下操作：

(1)訪問(wèn)根結(jié)點(diǎn)；

(2)先序遍歷左子樹(shù)；

(3)先序遍歷右子樹(shù)。輸出二叉樹(shù)中的所有結(jié)點(diǎn)分析：該問(wèn)題需要對(duì)二叉樹(shù)進(jìn)行遍歷，即：對(duì)所有結(jié)點(diǎn)進(jìn)行“訪問(wèn)”，且只訪問(wèn)一次這里的“訪問(wèn)”就是“結(jié)點(diǎn)的輸出”“訪問(wèn)”順序的確定只要能對(duì)所有結(jié)點(diǎn)進(jìn)行輸出，沒(méi)有結(jié)點(diǎn)輸出順序的要求，因此，按先序、中序和后序都可以這里以先序?yàn)槔惴枋觯ɑ谙刃虮闅v）若二叉樹(shù)為空，則空操作；否則，依次做如下操作：

(1)輸出根結(jié)點(diǎn)；

(2)輸出左子樹(shù)中的所有結(jié)點(diǎn)；

(3)輸出右子樹(shù)中的所有結(jié)點(diǎn)。思考：若基于中序遍歷或基于后序遍歷，則該問(wèn)題的算法應(yīng)該是怎樣的？看例子回去基于中序遍歷基于后序遍歷輸出二叉樹(shù)中的所有結(jié)點(diǎn)算法描述（基于中序遍歷）若二叉樹(shù)為空，則空操作；否則，依次做如下操作：

(1)輸出左子樹(shù)中的所有結(jié)點(diǎn)；

(2)輸出根結(jié)點(diǎn)；

(3)輸出右子樹(shù)中的所有結(jié)點(diǎn)。中序遍歷二叉樹(shù)若二叉樹(shù)為空，則空操作；

否則，依次做如下操作：

(1)中序遍歷左子樹(shù)；

(2)訪問(wèn)根結(jié)點(diǎn)；

(3)中序遍歷右子樹(shù)?；厝ポ敵龆鏄?shù)中的所有結(jié)點(diǎn)算法描述（基于后序遍歷）若二叉樹(shù)為空，則空操作；否則，依次做如下操作：

(1)輸出左子樹(shù)中的所有結(jié)點(diǎn)；

(2)輸出右子樹(shù)中的所有結(jié)點(diǎn)；

(3)輸出根結(jié)點(diǎn)。后序遍歷二叉樹(shù)若二叉樹(shù)為空，則空操作；

否則，依次做如下操作：

(1)后序遍歷左子樹(shù)；

(2)后序遍歷右子樹(shù)；

(3)訪問(wèn)根結(jié)點(diǎn)?；厝ポ敵龆鏄?shù)中的所有結(jié)點(diǎn)例ABCEFGDHK待輸出的二叉樹(shù)基于先序遍歷結(jié)點(diǎn)的輸出序列：ABCDEFGHK基于中序遍歷結(jié)點(diǎn)的輸出序列：基于后序遍歷結(jié)點(diǎn)的輸出序列：CDBAEHGKFDCBHKGFEA回去輸出二叉樹(shù)中的葉子結(jié)點(diǎn)分析：該問(wèn)題需要對(duì)二叉樹(shù)中所有結(jié)點(diǎn)進(jìn)行“訪問(wèn)”，且只訪問(wèn)一次這里的“訪問(wèn)”是“帶判斷的輸出”，也就是：“是葉子結(jié)點(diǎn)就輸出”“訪問(wèn)”順序的確定只要能對(duì)所有葉子結(jié)點(diǎn)進(jìn)行輸出，沒(méi)有結(jié)點(diǎn)輸出順序的要求，因此，按先序、中序和后序都可以算法描述若二叉樹(shù)為空，則空操作；否則，依次做如下操作：（1）如果根結(jié)點(diǎn)既沒(méi)有左孩子也沒(méi)有右孩子，則輸出根結(jié)點(diǎn)（2）輸出左子樹(shù)中的葉子結(jié)點(diǎn)（3）輸出右子樹(shù)中的葉子結(jié)點(diǎn)算法描述（基于中序遍歷）算法描述（基于后序遍歷）（基于先序遍歷）思考：該算法是基于先序的？中序的？還是后序的？看例子（1）如果根結(jié)點(diǎn)是葉子結(jié)點(diǎn)，則輸出根結(jié)點(diǎn)?；厝ポ敵龆鏄?shù)中的葉子結(jié)點(diǎn)分析：該問(wèn)題需要對(duì)二叉樹(shù)中所有結(jié)點(diǎn)進(jìn)行“訪問(wèn)”，且只訪問(wèn)一次這里的“訪問(wèn)”是“判斷+輸出”，也就是：“是葉子結(jié)點(diǎn)就輸出”需要按某種順序進(jìn)行“訪問(wèn)”只要能對(duì)所有葉子結(jié)點(diǎn)進(jìn)行輸出，沒(méi)有結(jié)點(diǎn)輸出順序的要求，因此，按先序、中序和后序都可以算法描述若二叉樹(shù)為空，則空操作；否則，依次做如下操作：（1）如果當(dāng)前二叉樹(shù)的根既沒(méi)有左孩子也沒(méi)有右孩子，則輸出根結(jié)點(diǎn)（2）輸出左子樹(shù)中的葉子結(jié)點(diǎn)（3）輸出右子樹(shù)中的葉子結(jié)點(diǎn)算法描述（基于中序遍歷）算法描述（基于后序遍歷）（基于先序遍歷）看例子輸出二叉樹(shù)中的葉子結(jié)點(diǎn)分析：該問(wèn)題需要對(duì)二叉樹(shù)中所有結(jié)點(diǎn)進(jìn)行“訪問(wèn)”，且只訪問(wèn)一次這里的“訪問(wèn)”是“判斷+輸出”，也就是：“是葉子結(jié)點(diǎn)就輸出”需要按某種順序進(jìn)行“訪問(wèn)”只要能對(duì)所有葉子結(jié)點(diǎn)進(jìn)行輸出，沒(méi)有結(jié)點(diǎn)輸出順序的要求，因此，按先序、中序和后序都可以算法描述算法描述（基于中序遍歷）若二叉樹(shù)為空，則空操作；否則，依次做如下操作：（1）輸出左子樹(shù)中的葉子結(jié)點(diǎn)（2）如果當(dāng)前二叉樹(shù)的根既沒(méi)有左孩子也沒(méi)有右孩子，則輸出根結(jié)點(diǎn)（3）輸出右子樹(shù)中的葉子結(jié)點(diǎn)算法描述（基于后序遍歷）（基于先序遍歷）看例子輸出二叉樹(shù)中的葉子結(jié)點(diǎn)分析：該問(wèn)題需要對(duì)二叉樹(shù)中所有結(jié)點(diǎn)進(jìn)行“訪問(wèn)”，且只訪問(wèn)一次這里的“訪問(wèn)”是“判斷+輸出”，也就是：“是葉子結(jié)點(diǎn)就輸出”需要按某種順序進(jìn)行“訪問(wèn)”只要能對(duì)所有葉子結(jié)點(diǎn)進(jìn)行輸出，沒(méi)有結(jié)點(diǎn)輸出順序的要求，因此，按先序、中序和后序都可以算法描述算法描述（基于中序遍歷）算法描述（基于后序遍歷）若二叉樹(shù)為空，則空操作；否則，依次做如下操作：（1）輸出左子樹(shù)中的葉子結(jié)點(diǎn)（2）輸出右子樹(shù)中的葉子結(jié)點(diǎn)（3）如果當(dāng)前二叉樹(shù)的根既沒(méi)有左孩子也沒(méi)有右孩子，則輸出根結(jié)點(diǎn)（基于先序遍歷）看例子輸出二叉樹(shù)中的葉子結(jié)點(diǎn)例ABCEFGDHK待輸出的二叉樹(shù)基于先序遍歷葉子結(jié)點(diǎn)的輸出序列：DHKDHKDHK基于后序遍歷葉子結(jié)點(diǎn)的輸出序列：基于中序遍歷葉子結(jié)點(diǎn)的輸出序列：思考：輸出二叉樹(shù)葉子結(jié)點(diǎn)的算法，不論基于先序、中序和后序，葉子結(jié)點(diǎn)的輸出順序都一樣嗎？為什么？回去求二叉樹(shù)的深度二叉樹(shù)深度的定義：結(jié)點(diǎn)的最大層次數(shù)MAX{左子樹(shù)的深度，右子樹(shù)的深度}+1求二叉樹(shù)深度的算法描述：若二叉樹(shù)為空，則返回0；否則，依次做如下操作：求左子樹(shù)的深度lh求右子樹(shù)的深度rh返回max{lh，rh}+1思考：基于什么遍歷順序后序遍歷這里，對(duì)結(jié)點(diǎn)訪問(wèn)的操作是什么求以該結(jié)點(diǎn)為根的二叉樹(shù)的深度根左子樹(shù)右子樹(shù)lhrh二叉樹(shù)的深度？二叉樹(shù)的深度=MAX{lh，rh}+1看例子回去思考：根據(jù)”二叉樹(shù)的深度=MAX{lh，rh}+1“這個(gè)定義，求二叉樹(shù)深度能否按先序或中序進(jìn)行？為什么？求二叉樹(shù)的深度例求二叉樹(shù)深度的算法描述：若二叉樹(shù)為空，則返回0；否則，依次做如下操作：求左子樹(shù)的深度lh求右子樹(shù)的深度rh返回max{lh，rh}+1ABCEFGDHK0120003000000112345回去思考與練習(xí)交換二叉樹(shù)的左右子樹(shù)用何種遍歷實(shí)現(xiàn)對(duì)二叉樹(shù)左右子樹(shù)的交換？在交換二叉樹(shù)左右子樹(shù)的遍歷中，”訪問(wèn)“操作是什么？寫(xiě)出一個(gè)實(shí)現(xiàn)二叉樹(shù)左右子樹(shù)交換的算法描述根據(jù)：二叉樹(shù)的深度=MAX{lh，rh}+1

這個(gè)定義，求二叉樹(shù)深度能否按先序或中序進(jìn)行？為什么？輸出二叉樹(shù)葉子結(jié)點(diǎn)的算法，不論基于先序、中序和后序，葉子結(jié)點(diǎn)的輸出順序都一樣嗎？為什么？二叉樹(shù)遍歷的實(shí)現(xiàn)算法先序遍歷的遞歸實(shí)現(xiàn)算法中序遍歷的遞歸實(shí)現(xiàn)算法后序遍歷的遞歸實(shí)現(xiàn)算法解決應(yīng)用問(wèn)題的實(shí)現(xiàn)算法返回P7先序遍歷的遞歸實(shí)現(xiàn)算法先序遍歷以root為根的二叉樹(shù)void

PreOrder(BiTree

root){

if(root!=NULL)

{

Visit(root->data);

/*訪問(wèn)根結(jié)點(diǎn)*/

PreOrder(root->lchild);

/*先序遍歷左子樹(shù)*/

PreOrder(root->rchild);

/*先序遍歷右子樹(shù)*/

}}返回P26中序遍歷的遞歸實(shí)現(xiàn)算法中序遍歷以root為根的二叉樹(shù)void

InOrder(BiTree

root)

{

if(root!=NULL)

{

InOrder(root->lchild);

/*中序遍歷左子樹(shù)*/

Visit(root->data);

/*訪問(wèn)根結(jié)點(diǎn)*/

InOrder(root->rchild);

/*中序遍歷右子樹(shù)*/

}}返回P26后序遍歷的遞歸實(shí)現(xiàn)算法后序遍歷以root為根的二叉樹(shù)void

PostOrder(BiTree

root)

{

if(root!=NULL)

{

PostOrder(root->lchild);/*后序遍歷左子樹(shù)*/

PostOrder(root->rchild);/*后序遍歷右子樹(shù)*

Visit(root->data);

/*訪問(wèn)根結(jié)點(diǎn)*/

}}返回P26解決應(yīng)用問(wèn)題的實(shí)現(xiàn)算法輸出二叉樹(shù)中結(jié)點(diǎn)的實(shí)現(xiàn)算法輸出二叉樹(shù)中葉子結(jié)點(diǎn)的實(shí)現(xiàn)算法求二叉樹(shù)深度的實(shí)現(xiàn)算法二叉樹(shù)的創(chuàng)建算法算法閱讀返回P26輸出二叉樹(shù)中結(jié)點(diǎn)的實(shí)現(xiàn)算法輸出以root為根的二叉樹(shù)中的結(jié)點(diǎn)。基于先序遍歷的實(shí)現(xiàn)算法void

OutBiTree(BiTree

root){

if(root!=NULL)

{

printf(root->data);

/*輸出根結(jié)點(diǎn)*/

OutBiTree(root->lchild);

/*輸出左子樹(shù)中的結(jié)點(diǎn)*/

OutBiTree(root->rchild);

/*輸出右子樹(shù)中的結(jié)點(diǎn)*/

}}返回P30輸出二叉樹(shù)中葉子結(jié)點(diǎn)的實(shí)現(xiàn)算法輸出以root為根的二叉樹(shù)中葉子結(jié)點(diǎn)基于先序遍歷的實(shí)現(xiàn)算法void

OutLeaf(BiTree

root){

if(root!=NULL)

{

if(root->lchild==NULL&&root->rchild==NULL)

printf(root->data);

/*輸出葉子結(jié)點(diǎn)*/

OutLeaf(root->lchild);

/*輸出左子樹(shù)中的葉子結(jié)點(diǎn)*/

OutLeaf(root->rchild);

/*輸出右子樹(shù)中的葉子結(jié)點(diǎn)*/

}}返回P30求二叉樹(shù)深度的實(shí)現(xiàn)算法求以root為根的二叉樹(shù)的深度int

BiTreeDepth(BiTree

root)

{

if(root!=NULL)

{

hl=BiTreeDepth(root->lchild);

/*求左子樹(shù)的深度*/

hr=BiTreeDepth(root->rchild);

/*求右子樹(shù)的深度*/max=hl>hr?hl:hr;

/*得到左、右子樹(shù)深度較大者*/return(max+1);

/*返回樹(shù)的深度*/

}

elsereturn(0);

/*如果是空樹(shù)，則返回0*/}返回P30關(guān)于二叉樹(shù)的創(chuàng)建給定一棵二叉樹(shù)，可以得到它的遍歷序列反之，給定一棵二叉樹(shù)的遍歷序列，也可以畫(huà)出該二叉樹(shù)能畫(huà)出就意味著能創(chuàng)建二叉樹(shù)已知二叉樹(shù)的“擴(kuò)展的遍歷序列，畫(huà)出該二叉樹(shù)在二叉樹(shù)的遍歷序列中，用特定的元素表示空子樹(shù)，就得到相應(yīng)的擴(kuò)展遍歷序列例如，下圖

中二叉樹(shù)的“擴(kuò)展先序遍歷序列”為：AB.DF..G..C.E.H..（這里以‘.’表示空子樹(shù)）繼續(xù)關(guān)于二叉樹(shù)的創(chuàng)建畫(huà)出擴(kuò)展先序序列為：ACF.GK..H…B.FE…

的二叉樹(shù)將此過(guò)程作為創(chuàng)建二叉樹(shù)的過(guò)程,即:創(chuàng)建二叉鏈表的過(guò)程則對(duì)應(yīng)此過(guò)程的實(shí)現(xiàn)算法見(jiàn)：“利用‘?dāng)U展先序遍歷序列‘創(chuàng)建二叉鏈表的算法”ACFBFGEKH繼續(xù)利用“擴(kuò)展先序遍歷序列”創(chuàng)建二叉鏈表的算法voidCreateBiTree(BiTree

&root){

ch=getchar();

if(ch=='.')root=NULL;

else{root=(BiTree)malloc(sizeof(BiTNode));

root->data=ch;

CreateBiTree(root->lchild);

CreateBiTree(root->rchild);

}}繼續(xù)ABFECFGKHrootACF.GK..H…B.FE…關(guān)于二叉樹(shù)的創(chuàng)建已知某二叉樹(shù)的先序序列和中序序列如下：先序序列：ABDGCEHF

中序序列：BGDAEHCF

畫(huà)出該二叉樹(shù)，并寫(xiě)出其后序序列。ABDGCEFH后序序列：GDBHEFCA由先序序列確定根是A由中序序列確定：（1）A有左、右子樹(shù)；（2）左子樹(shù)中的結(jié)點(diǎn)有BDG；右子樹(shù)中的結(jié)點(diǎn)有CEFH再由先序序列確定左子樹(shù)的結(jié)點(diǎn)BDG中B是根由中序序列確定B沒(méi)有左子樹(shù)，但有右子樹(shù)，其中右子樹(shù)中的結(jié)點(diǎn)有DG依此類(lèi)推，直到A的左子樹(shù)的結(jié)構(gòu)確定。用同樣的方法分析右子樹(shù)的結(jié)構(gòu)。繼續(xù)關(guān)于二叉樹(shù)的創(chuàng)建已知某二叉樹(shù)的中序序列和后序序列如下：中序序列：EGHCFAD

后序序列：EGCADFH

畫(huà)出該二叉樹(shù)，并寫(xiě)出其先序序列。由后序序列確定根是H由中序序列確定：（1）H有左、右子樹(shù)；（2）左子樹(shù)中的結(jié)點(diǎn)有GE；右子樹(shù)中的結(jié)點(diǎn)有FDCA再由后序序列確定左子樹(shù)的結(jié)點(diǎn)GE中G是根，由中序序列確定G有左子樹(shù)，但沒(méi)有右子樹(shù)，其中左子樹(shù)中的結(jié)點(diǎn)有E。用同樣的方法分析右子樹(shù)的結(jié)構(gòu)：根：F且F有左子樹(shù)，也有右子樹(shù)。左子樹(shù)有結(jié)點(diǎn)：C右子樹(shù)有結(jié)點(diǎn)：DA……先序序列：HGEFCDAHGFEDCA繼續(xù)關(guān)于二叉樹(shù)的創(chuàng)建思考：利用二叉樹(shù)的先序和中序或者中序和后序，創(chuàng)建該二叉樹(shù)對(duì)應(yīng)的二叉鏈表的過(guò)程，給出算法