第五章 樹和二叉樹(2)

1、二叉樹的遍歷二叉樹的遍歷1 1、遍歷二叉樹遍歷二叉樹：是指按指定的規(guī)律對(duì)二叉樹中的每個(gè)是指按指定的規(guī)律對(duì)二叉樹中的每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。結(jié)點(diǎn)訪問一次且僅訪問一次。2、二叉樹的遍歷方法二叉樹的遍歷方法：若以若以L L、D D、R R分別表示遍歷左分別表示遍歷左子樹、遍歷根結(jié)點(diǎn)和遍歷右子樹，則有六種遍歷方案：子樹、遍歷根結(jié)點(diǎn)和遍歷右子樹，則有六種遍歷方案：DLRDLR、LDRLDR、LRDLRD、DRLDRL、RDLRDL、RLDRLD。若規(guī)定先左后右，。若規(guī)定先左后右，則只有前三種情況三種情況，分別是：則只有前三種情況三種情況，分別是：DLRDLR先先( (根根) )序遍歷；序遍歷；LD

2、RLDR中中( (根根) )序遍歷；序遍歷；LRDLRD后后( (根根) )序遍歷；序遍歷；另外，也可以按層序遍歷。另外，也可以按層序遍歷。3 3、二叉樹的遍歷算法二叉樹的遍歷算法：a.a.先序遍歷先序遍歷：一、遞歸算法。算法的遞歸定義是：若二叉樹為空，一、遞歸算法。算法的遞歸定義是：若二叉樹為空，則遍歷結(jié)束；否則則遍歷結(jié)束；否則 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； 先序遍歷左子樹先序遍歷左子樹( (遞歸調(diào)用本算法遞歸調(diào)用本算法) )； 先序遍歷右子樹先序遍歷右子樹( (遞歸調(diào)用本算法遞歸調(diào)用本算法) )。算法程序算法程序：二、非遞歸算法。算法定義是：若二叉樹為空，則返二、非遞歸算法。算法定義是：若二叉

3、樹為空，則返回；否則，令回；否則，令p=Tp=T； 訪問訪問p p所指向的結(jié)點(diǎn)；所指向的結(jié)點(diǎn)； q=p-q=p-rchildrchild ，若，若q q不為空，則不為空，則q q進(jìn)棧；進(jìn)棧； p=p-p=p-lchildlchild ，若，若p p不為空，轉(zhuǎn)不為空，轉(zhuǎn)(1)(1)，否則轉(zhuǎn)，否則轉(zhuǎn)(4)(4)； 退棧到退棧到p p ，轉(zhuǎn)，轉(zhuǎn)(1)(1)，直到?？諡橹埂?，直到?？諡橹?。算法程序算法程序：b.b.中序遍歷中序遍歷：一、遞歸算法。算法的遞歸定義是：若二叉樹為空，一、遞歸算法。算法的遞歸定義是：若二叉樹為空，則遍歷結(jié)束；否則則遍歷結(jié)束；否則 中序遍歷左子樹中序遍歷左子樹( (遞歸調(diào)用本算

4、法遞歸調(diào)用本算法) )； 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； 中序遍歷右子樹中序遍歷右子樹( (遞歸調(diào)用本算法遞歸調(diào)用本算法) )。算法程序算法程序：二、非遞歸算法。算法定義是：若二叉樹為空，則返二、非遞歸算法。算法定義是：若二叉樹為空，則返回；否則，令回；否則，令p=Tp=T 若若p p不為空，不為空，p p進(jìn)棧，進(jìn)棧， p=p-p=p-lchildlchild ； 否則否則( (即即p p為空為空) )，退棧到，退棧到p p，訪問，訪問p p所指向的結(jié)點(diǎn)；所指向的結(jié)點(diǎn)； p=p-p=p-rchildrchild ，轉(zhuǎn)，轉(zhuǎn)(1)(1)；直到棧空為止。；直到?？諡橹埂Ｋ惴ǔ绦蛩惴ǔ绦颍篶.c.后序遍歷后

5、序遍歷：一、遞歸算法。算法的遞歸定義是：若二叉樹為空，一、遞歸算法。算法的遞歸定義是：若二叉樹為空，則遍歷結(jié)束；否則則遍歷結(jié)束；否則 后序遍歷左子樹后序遍歷左子樹( (遞歸調(diào)用本算法遞歸調(diào)用本算法) )； 后序遍歷右子樹后序遍歷右子樹( (遞歸調(diào)用本算法遞歸調(diào)用本算法) )； 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) 。算法程序算法程序：二、非遞歸算法，算法定義是：若二叉樹為空，則返二、非遞歸算法，算法定義是：若二叉樹為空，則返回；否則，令回；否則，令p=Tp=T；p p進(jìn)棧進(jìn)棧S S ， tag =1tag =1，p=p-p=p-lchildlchild 。若若p p不為空，轉(zhuǎn)不為空，轉(zhuǎn)(1)(1)，否則，取棧

6、頂元素，否則，取棧頂元素tag tag ：若若tag=1tag=1：不出棧；棧頂元素：不出棧；棧頂元素tag=2 tag=2 ，取棧頂元，取棧頂元素的右子樹，即素的右子樹，即p=p-p=p-rchilerchile ，轉(zhuǎn)，轉(zhuǎn)(1)(1)；若若tag=2tag=2：退棧，訪問該結(jié)點(diǎn)；直到?？諡橹埂＃和藯?，訪問該結(jié)點(diǎn)；直到?？諡橹埂Ｋ惴ǔ绦蛩惴ǔ绦颍篸.d.層次遍歷層次遍歷：層次遍歷算法是：若二叉樹為空，則返回；否則，令層次遍歷算法是：若二叉樹為空，則返回；否則，令p=Tp=T，p p入隊(duì)；入隊(duì)；隊(duì)首元素出隊(duì)到隊(duì)首元素出隊(duì)到p p；訪問訪問p p所指向的結(jié)點(diǎn)；所指向的結(jié)點(diǎn)； 將將p p所指向的結(jié)點(diǎn)

7、的左、右子結(jié)點(diǎn)依次入隊(duì)。直到所指向的結(jié)點(diǎn)的左、右子結(jié)點(diǎn)依次入隊(duì)。直到隊(duì)空為止。隊(duì)空為止。算法程序算法程序：4 4、基于二叉樹的遍歷的常用算法基于二叉樹的遍歷的常用算法：a.a.基于二叉樹遍歷的遞歸算法基于二叉樹遍歷的遞歸算法：求二叉樹中求二叉樹中結(jié)點(diǎn)的個(gè)數(shù)；結(jié)點(diǎn)的個(gè)數(shù)；求二叉樹中求二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)；葉子結(jié)點(diǎn)的個(gè)數(shù)；按先序的逆序打印葉子結(jié)點(diǎn)；按先序的逆序打印葉子結(jié)點(diǎn)；復(fù)制一棵二叉樹；復(fù)制一棵二叉樹；求二叉樹的深度；求二叉樹的深度；交換二叉樹中每個(gè)結(jié)點(diǎn)的左右子樹；交換二叉樹中每個(gè)結(jié)點(diǎn)的左右子樹；在二叉樹中查找是否有結(jié)點(diǎn)的值為在二叉樹中查找是否有結(jié)點(diǎn)的值為x;x;在二叉樹中刪除以在二叉樹中刪除

8、以x x為根的子樹；為根的子樹；b.b.基于二叉樹層次遍歷的算法基于二叉樹層次遍歷的算法：求二叉樹中第求二叉樹中第k層層(k1)葉子結(jié)點(diǎn)的個(gè)數(shù)；葉子結(jié)點(diǎn)的個(gè)數(shù)；求二叉樹中每一層節(jié)點(diǎn)的個(gè)數(shù)。求二叉樹中每一層節(jié)點(diǎn)的個(gè)數(shù)。c.c.基于順序存儲(chǔ)結(jié)構(gòu)的二叉樹遍歷算法基于順序存儲(chǔ)結(jié)構(gòu)的二叉樹遍歷算法：一棵完全二叉樹存儲(chǔ)在數(shù)組一棵完全二叉樹存儲(chǔ)在數(shù)組a1a1nn中，編寫非遞歸的中，編寫非遞歸的先序遍歷算法；先序遍歷算法；一棵二叉樹存儲(chǔ)在數(shù)組一棵二叉樹存儲(chǔ)在數(shù)組a1a1nn中，編寫非遞歸的先序中，編寫非遞歸的先序遍歷算法；遍歷算法；d.d.基于二叉樹遍歷的非遞歸算法基于二叉樹遍歷的非遞歸算法：求二叉樹中每一個(gè)

9、葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。求二叉樹中每一個(gè)葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。5 5、習(xí)題習(xí)題(1)(1)給定先序序列為給定先序序列為ABCDEFGHABCDEFGH，中序序列為，中序序列為CBEDAGHFCBEDAGHF構(gòu)造對(duì)應(yīng)的二叉樹。構(gòu)造對(duì)應(yīng)的二叉樹。(2)(2)給定后序序列為給定后序序列為CEDBHGFACEDBHGFA，中序序列為，中序序列為CBEDAGHFCBEDAGHF構(gòu)造對(duì)應(yīng)的二叉樹。構(gòu)造對(duì)應(yīng)的二叉樹。(4)(4)某二叉樹的先序序列和后序序列正好相反，則該某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（二叉樹一定是（ ）的二叉樹。）的二叉樹。 A A空或只有一個(gè)結(jié)點(diǎn)空或只有一個(gè)結(jié)點(diǎn)

10、B B高度等于其結(jié)點(diǎn)數(shù)高度等于其結(jié)點(diǎn)數(shù) C C任一結(jié)點(diǎn)無左孩子任一結(jié)點(diǎn)無左孩子 D D任一結(jié)點(diǎn)無右孩子任一結(jié)點(diǎn)無右孩子(5)(5)遍歷一棵具有遍歷一棵具有N N個(gè)結(jié)點(diǎn)的二叉樹，在前序序列、中個(gè)結(jié)點(diǎn)的二叉樹，在前序序列、中序序列和后序序列中所有葉子結(jié)點(diǎn)的相對(duì)次序（序序列和后序序列中所有葉子結(jié)點(diǎn)的相對(duì)次序（ ） A.A.都不相同都不相同 B.B.完全相同完全相同C.C.前序和中序相同前序和中序相同 D.D.中序和后序相同中序和后序相同 m,nm,n是一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)是一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)n n 在在m m之前的條件是（之前的條件是（ ） 。 A.nA.n在在m

11、m的右方的右方 B. nB. n在在m m的左方的左方 C.nC.n是是m m的祖先的祖先 D. n D. n是是m m的子孫的子孫（7 7）在二叉樹先序、中序和后序遍歷中）在二叉樹先序、中序和后序遍歷中a a都在都在b b前面前面的條件是的條件是( )( )。A Aa a和和b b是兄弟是兄弟 B Ba a是是b b的雙親的雙親 C Ca a是是b b的左孩子的左孩子 D Da a是是b b的右孩子的右孩子已知某二叉樹每個(gè)結(jié)點(diǎn)，要么其左、右子樹都已知某二叉樹每個(gè)結(jié)點(diǎn)，要么其左、右子樹都為空，要么其左、右子樹都不為空。已知其先序序列為：為空，要么其左、右子樹都不為空。已知其先序序列為：jfdb

12、acehxik,jfdbacehxik,后序序列為后序序列為acbedxihfkj,acbedxihfkj,構(gòu)造該二叉樹。構(gòu)造該二叉樹。已知某二叉樹其層次序列為：已知某二叉樹其層次序列為：abcdefghij,abcdefghij,中序中序序列為序列為dbgehacijf,dbgehacijf,構(gòu)造該二叉樹。構(gòu)造該二叉樹。線索二叉樹線索二叉樹1 1、線索二叉樹線索二叉樹：在一個(gè)具有在一個(gè)具有 n個(gè)結(jié)點(diǎn)的二叉鏈表中，個(gè)結(jié)點(diǎn)的二叉鏈表中，利用利用n+1個(gè)空指針域存放指向該結(jié)點(diǎn)在某種遍歷序列中個(gè)空指針域存放指向該結(jié)點(diǎn)在某種遍歷序列中前驅(qū)和后繼結(jié)點(diǎn)指針，這些指向前驅(qū)和后繼結(jié)點(diǎn)的指前驅(qū)和后繼結(jié)點(diǎn)指針，這

13、些指向前驅(qū)和后繼結(jié)點(diǎn)的指針被稱為針被稱為線索，線索，加上線索的二叉樹被加上線索的二叉樹被稱為線索二叉樹稱為線索二叉樹，加上線索的二叉鏈表被稱為加上線索的二叉鏈表被稱為線索鏈表線索鏈表。2、線索二叉樹存儲(chǔ)結(jié)點(diǎn)的定義線索二叉樹存儲(chǔ)結(jié)點(diǎn)的定義：若結(jié)點(diǎn)有左孩子，則若結(jié)點(diǎn)有左孩子，則lchildlchild指向其左孩子，否則，指向其直接前驅(qū)；若結(jié)指向其左孩子，否則，指向其直接前驅(qū)；若結(jié)點(diǎn)有右孩子，則點(diǎn)有右孩子，則rchildrchild指向其右孩子，否則，指向其指向其右孩子，否則，指向其直接后繼；為避免混淆直接后繼；為避免混淆, ,對(duì)結(jié)點(diǎn)結(jié)構(gòu)加以改進(jìn)，增加兩對(duì)結(jié)點(diǎn)結(jié)構(gòu)加以改進(jìn)，增加兩個(gè)標(biāo)志域，個(gè)標(biāo)志域，

14、lchild ltag data rchild rtag線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)0：lchild域指示結(jié)點(diǎn)的左孩子域指示結(jié)點(diǎn)的左孩子1 1：lchild域指示結(jié)點(diǎn)的前驅(qū)域指示結(jié)點(diǎn)的前驅(qū)ltag=0 0：rchild域指示結(jié)點(diǎn)的右孩子域指示結(jié)點(diǎn)的右孩子1 1：rchild域指示結(jié)點(diǎn)的后繼域指示結(jié)點(diǎn)的后繼rtag=線索鏈表結(jié)點(diǎn)的定義線索鏈表結(jié)點(diǎn)的定義typedef struct BiThrNode ElemType data; struct BiTreeNode *lchild , *rchild ; int ltag , rtag ;BiThrNode ;3 3、中序線索鏈表的構(gòu)

15、造中序線索鏈表的構(gòu)造：中序線索鏈表的構(gòu)造過程就中序線索鏈表的構(gòu)造過程就是在遍歷過程中修改空指針使其指向直接前驅(qū)或直接是在遍歷過程中修改空指針使其指向直接前驅(qū)或直接后繼的過程。后繼的過程。算法程序：算法程序：4 4、在中序線索鏈表上查找前驅(qū)和后繼結(jié)點(diǎn)在中序線索鏈表上查找前驅(qū)和后繼結(jié)點(diǎn)：如果結(jié)點(diǎn)的如果結(jié)點(diǎn)的rtagrtag=1,=1,則則rchildrchild指針指向中序遍歷的后指針指向中序遍歷的后繼結(jié)點(diǎn)；若結(jié)點(diǎn)的繼結(jié)點(diǎn)；若結(jié)點(diǎn)的rtagrtag=0=0，則有右子樹的最左下為其，則有右子樹的最左下為其中序遍歷的后繼結(jié)點(diǎn)。中序遍歷的后繼結(jié)點(diǎn)。如果結(jié)點(diǎn)的如果結(jié)點(diǎn)的ltagltag=1,=1,則則lc

16、hildlchild指針指向中序遍歷的前指針指向中序遍歷的前驅(qū)結(jié)點(diǎn)；若結(jié)點(diǎn)的驅(qū)結(jié)點(diǎn)；若結(jié)點(diǎn)的ltagltag=0=0，則有左子樹的最右下為其，則有左子樹的最右下為其中序遍歷的前驅(qū)結(jié)點(diǎn)。中序遍歷的前驅(qū)結(jié)點(diǎn)。5 5、中序線索鏈表的遍歷算法中序線索鏈表的遍歷算法：算法程序：算法程序：6 6、習(xí)題習(xí)題（1 1）線索二叉樹是一種（）線索二叉樹是一種（ ）結(jié)構(gòu)。）結(jié)構(gòu)。 A A邏輯邏輯 B B物理物理 C C邏輯和物理邏輯和物理 D D線性結(jié)構(gòu)線性結(jié)構(gòu)（2 2）線索二叉樹中結(jié)點(diǎn)）線索二叉樹中結(jié)點(diǎn)R R沒有右孩子的充要條件是？沒有右孩子的充要條件是？（3 3）一棵左子樹為空的先序線索二叉樹，空指針域的）一棵

17、左子樹為空的先序線索二叉樹，空指針域的個(gè)數(shù)是（個(gè)數(shù)是（ ）。）。 A A0 B0 B1 C1 C2 D2 D不確定不確定（4 4）一棵左、右子樹均不為空的先序線索二叉樹，空）一棵左、右子樹均不為空的先序線索二叉樹，空指針域的個(gè)數(shù)是（指針域的個(gè)數(shù)是（ ）。）。 A A0 B0 B1 C1 C2 D2 D不確定不確定（5 5）在中序線索二叉樹中，若某結(jié)點(diǎn)有右孩子，則該）在中序線索二叉樹中，若某結(jié)點(diǎn)有右孩子，則該結(jié)點(diǎn)的直接后繼是結(jié)點(diǎn)的直接后繼是( )( )。 A A 左子樹的最右下結(jié)點(diǎn)左子樹的最右下結(jié)點(diǎn) B B 右子樹的最右下結(jié)點(diǎn)右子樹的最右下結(jié)點(diǎn) C C 左子樹的最左下結(jié)點(diǎn)左子樹的最左下結(jié)點(diǎn) D

18、D 右子樹的最左下結(jié)點(diǎn)右子樹的最左下結(jié)點(diǎn)（6 6）在中序線索二叉樹中，能否找到某結(jié)點(diǎn)后序的后）在中序線索二叉樹中，能否找到某結(jié)點(diǎn)后序的后繼結(jié)點(diǎn)？繼結(jié)點(diǎn)？20102010年考了一道選擇題年考了一道選擇題樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)1 1、雙親表示法雙親表示法：用一組連續(xù)的存儲(chǔ)空間來存儲(chǔ)樹的結(jié)：用一組連續(xù)的存儲(chǔ)空間來存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附加一個(gè)指示器點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附加一個(gè)指示器( (整數(shù)域整數(shù)域) ) ，用，用以指示雙親結(jié)點(diǎn)的位置以指示雙親結(jié)點(diǎn)的位置( (下標(biāo)值下標(biāo)值) ) 。數(shù)組元素及數(shù)組的。數(shù)組元素及數(shù)組的類型定義如下：類型定義如下：#define MAX_SIZE 100type

19、def struct PTNode ElemType data ;int parent ;PTNode ;2 2、孩子表示法孩子表示法：對(duì)于樹中的每個(gè)結(jié)點(diǎn)，其孩子結(jié)點(diǎn)用：對(duì)于樹中的每個(gè)結(jié)點(diǎn)，其孩子結(jié)點(diǎn)用帶頭結(jié)點(diǎn)的單鏈表表示，表結(jié)點(diǎn)和頭結(jié)點(diǎn)的結(jié)構(gòu)如圖帶頭結(jié)點(diǎn)的單鏈表表示，表結(jié)點(diǎn)和頭結(jié)點(diǎn)的結(jié)構(gòu)如圖所示。所示。n n個(gè)結(jié)點(diǎn)的樹有個(gè)結(jié)點(diǎn)的樹有n n個(gè)個(gè)( (孩子孩子) )單鏈表單鏈表( (葉子結(jié)點(diǎn)的孩葉子結(jié)點(diǎn)的孩子鏈表為空子鏈表為空) )，而，而n n個(gè)頭結(jié)點(diǎn)又組成一個(gè)線性表且以順個(gè)頭結(jié)點(diǎn)又組成一個(gè)線性表且以順序存儲(chǔ)結(jié)構(gòu)表示。序存儲(chǔ)結(jié)構(gòu)表示。data firstchild(a) 頭結(jié)點(diǎn)頭結(jié)點(diǎn)child

20、no next(b) 表結(jié)點(diǎn)表結(jié)點(diǎn)孩子鏈表結(jié)點(diǎn)結(jié)構(gòu)孩子鏈表結(jié)點(diǎn)結(jié)構(gòu)3 3、孩子兄弟表示法孩子兄弟表示法：以二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)，：以二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)，其結(jié)點(diǎn)形式如圖所示。兩個(gè)指針域：分別指向結(jié)點(diǎn)的其結(jié)點(diǎn)形式如圖所示。兩個(gè)指針域：分別指向結(jié)點(diǎn)的第一個(gè)子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。結(jié)點(diǎn)類型定義如下：第一個(gè)子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。結(jié)點(diǎn)類型定義如下：typedeftypedef structstruct CSnodeCSnode ElemTypeElemType data ; data ; structstruct CSnodeCSnode * *firstchildfirstchild, ,

21、* *nextsibingnextsibing ; ; CSNodeCSNode; ; 孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)兄弟結(jié)點(diǎn)兄弟結(jié)點(diǎn)firstchild data nextsibing結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)樹、森林和二叉樹的轉(zhuǎn)化樹、森林和二叉樹的轉(zhuǎn)化1 1、樹轉(zhuǎn)換成二叉樹樹轉(zhuǎn)換成二叉樹: :a.a.其詳細(xì)步驟是：其詳細(xì)步驟是： 加虛線。在樹的每層按從加虛線。在樹的每層按從“左至右左至右”的順序在的順序在兄弟結(jié)點(diǎn)之間加虛線相連。兄弟結(jié)點(diǎn)之間加虛線相連。 去連線。除最左的第一個(gè)子結(jié)點(diǎn)外，父結(jié)點(diǎn)與去連線。除最左的第一個(gè)子結(jié)點(diǎn)外，父結(jié)點(diǎn)與所有其它子結(jié)點(diǎn)的連線都去掉。所有其它子結(jié)點(diǎn)的連線都去掉。 旋轉(zhuǎn)。將樹順時(shí)針旋轉(zhuǎn)旋轉(zhuǎn)

22、。將樹順時(shí)針旋轉(zhuǎn)450450，原有的實(shí)線左斜。，原有的實(shí)線左斜。 整型。將旋轉(zhuǎn)后樹中的所有虛線改為實(shí)線，并整型。將旋轉(zhuǎn)后樹中的所有虛線改為實(shí)線，并向右斜。向右斜。b.b.這樣轉(zhuǎn)換后的二叉樹的特點(diǎn)是：這樣轉(zhuǎn)換后的二叉樹的特點(diǎn)是： 二叉樹的根結(jié)點(diǎn)沒有右子樹，只有左子樹；二叉樹的根結(jié)點(diǎn)沒有右子樹，只有左子樹； 左子左子樹樹結(jié)點(diǎn)仍然是原來樹中相應(yīng)結(jié)點(diǎn)的左子結(jié)點(diǎn)仍然是原來樹中相應(yīng)結(jié)點(diǎn)的左子樹樹結(jié)點(diǎn)，而所有沿右鏈往下的右子結(jié)點(diǎn)，而所有沿右鏈往下的右子樹樹結(jié)點(diǎn)均是原來結(jié)點(diǎn)均是原來樹中該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)。樹中該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)。2 2、二叉樹轉(zhuǎn)換成樹二叉樹轉(zhuǎn)換成樹: :其步驟是：其步驟是：加虛線。若某結(jié)點(diǎn)加虛線。

23、若某結(jié)點(diǎn)i i是其父結(jié)點(diǎn)的左子樹的根結(jié)是其父結(jié)點(diǎn)的左子樹的根結(jié)點(diǎn)，則將該結(jié)點(diǎn)點(diǎn)，則將該結(jié)點(diǎn)i i的右子樹結(jié)點(diǎn)以及沿右子樹鏈不的右子樹結(jié)點(diǎn)以及沿右子樹鏈不斷地搜索所有的右子樹結(jié)點(diǎn)，將所有這些右子樹斷地搜索所有的右子樹結(jié)點(diǎn)，將所有這些右子樹結(jié)點(diǎn)與結(jié)點(diǎn)與i i結(jié)點(diǎn)的父結(jié)點(diǎn)之間加虛線相連。結(jié)點(diǎn)的父結(jié)點(diǎn)之間加虛線相連。去連線。去掉二叉樹中所有父結(jié)點(diǎn)與其右子樹結(jié)去連線。去掉二叉樹中所有父結(jié)點(diǎn)與其右子樹結(jié)點(diǎn)之間的連線。點(diǎn)之間的連線。規(guī)整化。將圖中各結(jié)點(diǎn)按層次排列且將所有的虛規(guī)整化。將圖中各結(jié)點(diǎn)按層次排列且將所有的虛線變成實(shí)線。線變成實(shí)線。3 3、森林轉(zhuǎn)換成二叉樹森林轉(zhuǎn)換成二叉樹: :其步驟是：其步驟是：將將F=T1, T2,F=T1, T2, ,Tn ,Tn 中的每棵樹轉(zhuǎn)換成二叉樹。中的每棵樹轉(zhuǎn)換成二叉樹。按給出的森林中樹的次序，從最后一棵二叉樹開按給出的森林中樹的次序，從最后一棵二叉樹開始，每棵二叉樹作為前一棵二叉樹的根結(jié)點(diǎn)的右始，每棵二叉樹作為前一棵二叉樹的根結(jié)點(diǎn)的右子樹，依次類推，則第一棵樹的根結(jié)點(diǎn)就是轉(zhuǎn)換子樹，依次類推，則第一棵樹的