軟件技術基礎09--樹結(jié)構

1、軟件技術基礎軟件技術基礎制作主講段景山樹的基本概念樹的基本概念有且僅有一個根結(jié)點除根結(jié)點以外的結(jié)點有且僅有一個父結(jié)點樹的定義樹的定義樹的定義樹的定義樹的術語樹的術語l(3)結(jié)點的關系結(jié)點的關系樹的術語樹的術語樹的術語樹的術語樹的術語樹的術語樹的術語樹的術語樹的存儲樹的存儲連續(xù)線性的下標不能很好的反映樹的分支關系（非線性）樹的存儲樹的存儲二叉樹二叉樹仍然是遞歸定義。二叉樹是樹嗎？二叉樹二叉樹二叉樹的性質(zhì)二叉樹的性質(zhì)1二叉樹的數(shù)學特性二叉樹與二進制之間存在必然聯(lián)系，進而可以與整個數(shù)學發(fā)生關聯(lián)了二叉樹的性質(zhì)二叉樹的性質(zhì)設n0為葉結(jié)點個數(shù)， n1為具有一個孩子的分支結(jié)點個數(shù)， n2為具有兩個孩子的分支

2、結(jié)點個數(shù)， n為結(jié)點總個數(shù)條件1、 n = n0 + n1 + n2條件2、 n = 分支的個數(shù) + 1設為分支的個數(shù)為B條件3、 B = 2 n2 + n1所以： 2n2 + n1 + 1 = n0 + n1 + n2二叉樹的性質(zhì)二叉樹的性質(zhì)二叉樹的性質(zhì)二叉樹的性質(zhì)完全二叉樹完全二叉樹二叉樹二叉樹順序存儲二叉樹順序存儲二叉樹順序存儲二叉樹順序存儲二叉樹101112131415用鏈表實現(xiàn)二叉樹用鏈表實現(xiàn)二叉樹dataLchileRchild根結(jié)點指針用鏈表實現(xiàn)二叉樹用鏈表實現(xiàn)二叉樹dLRdLRdLRdLRdLRdLRdLRdLR二叉樹的遍歷二叉樹的遍歷以根被訪問順序來劃分不同的遍歷方法在子樹的

3、訪問順序中始終以左子樹優(yōu)先特點：二叉樹的遍歷二叉樹的遍歷ABCDEFGHIJKLMNOPQF G C E H B D J I A L N P O Q M K左左 根根 右右二叉樹的遍歷二叉樹的遍歷ABCDEFGHIJKLMNOPQA B C F G E H D I J K L M N O P Q根根 左左 右右二叉樹的遍歷二叉樹的遍歷ABCDEFGHIJKLMNOPQG F H E C J I D B P Q O N M L K A左左 右右 根根課堂練習課堂練習ABCDEFGHIJKLMNOPQA B C F G E H D I J K L M N O P QG F H E C J I D

4、B P Q O N M L K AF G C E H B D J I A L N P O Q M K二叉樹的遍歷二叉樹的遍歷ABC方法一、利用棧來實現(xiàn)回朔方法一、利用棧來實現(xiàn)回朔回到回到回溯回溯XABCDEFGHIJKLMNOPQABCFGE HDwhile( ! end_of(tree).while( ! end_of(tree) if( p != NULL )push(stack , p)p = p-Lchild; elsep = pop(stack);process(p);p = p-Rchild; ABCF GEwhile( ! end_of(tree) if( p != NULL )

5、push(stack , p)p = p-Lchild; elsep = pop(stack);process(p);p = p-Rchild;isEmpty(stack)ABCDEFGHIJKLMNOPQAP指針指針K_NULLNULLwhile( ! empty(tree) if( p != NULL )push(stack , p)p = p-Lchild; elsep = pop(stack);process(p);p = p-Rchild;ABCDEFGHIJKLMNOPQAP指針指針KNULLvoid inorder( tree)tnode_type * p;create_stac

6、k( stack );p = tree-root;訪問結(jié)點訪問結(jié)點while( p != NULL | ! empty(stack) )if ( p != NULL)push(stack, p);p = p - Lchild;elsep = pop(stack);process(p);p = p-Rchild;中根遍歷算法（法一）中根遍歷算法（法一）void preorder( tree)tnode_type * p;create_stack( stack );p = tree-root;while( p != NULL | ! empty(stack) )if ( p != NULL)pro

7、cess(p);push(stack, p);p = p - Lchild;elsep = pop(stack);process(p);p = p-Rchild;先根遍歷算法先根遍歷算法后根遍歷算法在基本框架上如何更動以完成void postorder( tree)tnode_type * p;create_stack( stack );p = tree-root;while( p != NULL | ! empty(stack) )if ( p != NULL)push(stack, p);p = p - Lchild;elsep = pop(stack);p = p-Rchild; pro

8、cess( p )放到哪里？放到哪里？后根遍歷后根遍歷利用遞歸的遍歷算法（重要）利用遞歸的遍歷算法（重要）左左 根根 右右左左 根根 右右左左 右右 根根利用遞歸的遍歷算法利用遞歸的遍歷算法利用遞歸的遍歷算法利用遞歸的遍歷算法根根 左左 右右ABC中根遍歷中根遍歷中序遍歷中序遍歷先根遍歷先根遍歷先序遍歷先序遍歷后根遍歷后根遍歷后序遍歷后序遍歷利用遞歸的遍歷算法利用遞歸的遍歷算法二叉樹的遍歷二叉樹的遍歷二叉樹的建立（上機練習）二叉樹的建立（上機練習）ABC_DEF_G_H_I_JK_L_利用先根遍歷算法框架，建立二叉樹根據(jù)輸入的情況，將新節(jié)點放在指定的位置，然后從新節(jié)點開始下一個過程二叉樹的建立

9、（上機練習）二叉樹的建立（上機練習）二叉樹的建立（上機練習）二叉樹的建立（上機練習）二叉樹的建立（上機練習）二叉樹的建立（上機練習）node * create_node（ch） node * p; p = (node *)malloc(sizeof(node); p-data = ch; p-Lchild = NULL; p-Rchile = NULL; return p;二叉樹的建立（上機練習）二叉樹的建立（上機練習）根據(jù)輸入，生成新鏈點，主要包括申請鏈點空間輸入根元素生成整個樹的根以先根遍歷算法為基礎遞歸生成二叉樹二叉樹的操作二叉樹的操作BCDFGEHnew哪一種插入方式更合理？法2維持遍

10、歷順序一致二叉樹的插入二叉樹的插入課堂練習課堂練習右右左左根根二叉樹的刪除二叉樹的刪除del左左右右爺爺二叉樹的刪除二叉樹的刪除左左右右左左右右爺爺爺爺deldeldel左左右右爺爺二叉樹刪除二叉樹刪除 課堂練習課堂練習ABCDEFGHIJKLMNOP左左右右爺爺FGHIJKLMNOPdel左左右右爺爺二叉樹刪除二叉樹刪除 課堂練習課堂練習二叉樹的重構二叉樹的重構F G C E H B D J I A L N P O Q M KA B C F G E H D I J K L M N O P QFGCEHBDJILNPOQMK二叉樹的重構二叉樹的重構樹與二叉樹的轉(zhuǎn)換樹與二叉樹的轉(zhuǎn)換1243567123456788森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換樹的應用樹的應用樹的應用樹的應用樹的應用樹的應用樹的應用樹的應用樹的應用樹的應用220615樹的應用樹的應用樹的應用樹的應用57245724572452722242 3652734321 4623435271 35樹的應用樹的應用5724657241