4-3樹的存儲(chǔ)結(jié)構(gòu)v第四章樹和二叉樹思考問題的出發(fā)點(diǎn)：如何表示結(jié)點(diǎn)的雙親和孩子如何表示樹中結(jié)點(diǎn)之間的邏輯關(guān)系數(shù)據(jù)元素及其邏輯關(guān)系在存儲(chǔ)器中的表示實(shí)現(xiàn)樹的存儲(chǔ)結(jié)構(gòu)，關(guān)鍵是什么?什么是存儲(chǔ)結(jié)構(gòu)?樹中結(jié)點(diǎn)之間的邏輯關(guān)系是什么?CBGFEDHIA學(xué)什么？4-3-1樹的雙親表示法v第四章樹和二叉樹雙親表示法CBGFEDHIA樹的雙親表示法：用一維數(shù)組存儲(chǔ)樹中各個(gè)結(jié)點(diǎn)（一般按層序存儲(chǔ)）的數(shù)據(jù)信息以及該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo)012345678dataparent

ABCDEFGHI

-100111224如何定義樹的雙親表示法?template<typename

DataType>struct

PNode

{

DataTypedata;

intparent;};012345678

A-1B0C0D1E1F1G2H2I

4dataparent如何查找雙親結(jié)點(diǎn)？時(shí)間性能？O(1)如何查找孩子結(jié)點(diǎn)？時(shí)間性能？O(n)數(shù)據(jù)表示firstChild

136

-18-1-1-1-1雙親表示法CBGFEDHIA4-3-2樹的孩子表示法v第四章樹和二叉樹孩子表示法CBGFEDHIA如何表示結(jié)點(diǎn)的孩子呢？方案一：指針域的個(gè)數(shù)等于樹的度

datachild1child2……childd其中：data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息

child1~childd：指針域，指向該結(jié)點(diǎn)的孩子∧AB∧C∧D∧E∧F∧G∧H∧I∧∧∧∧∧∧∧∧∧∧∧缺點(diǎn)：浪費(fèi)空間CBGFEDHIA方案二：指針域的個(gè)數(shù)等于該結(jié)點(diǎn)的度

datadegreechild1child2……childd其中：data：存放該結(jié)點(diǎn)的數(shù)據(jù)；degree：存放該結(jié)點(diǎn)的度；

child1~childd：指針域，指向該結(jié)點(diǎn)的孩子孩子表示法如何表示結(jié)點(diǎn)的孩子呢？A2B3C2E1I0G0H0F0D0缺點(diǎn)：結(jié)點(diǎn)結(jié)構(gòu)不一致CBGFEDHIA方案三：將結(jié)點(diǎn)的所有孩子構(gòu)成一個(gè)單鏈表12∧345∧7∧68∧∧∧∧∧∧firstChild

012345678

ABCDEFGHIdata孩子表示法如何表示結(jié)點(diǎn)的孩子呢？如何定義樹的孩子表示法呢？12∧345∧7∧68∧∧∧∧∧∧firstChild

012345678

ABCDEFGHIdatachildnext孩子結(jié)點(diǎn)datafirstChild表頭結(jié)點(diǎn)孩子表示法structChildNode//孩子結(jié)點(diǎn){

intchild;ChildNode*next;};template<typenameDataType>structTreeNode//表頭結(jié)點(diǎn){DataTypedata;ChildNode*firstChild;//指向孩子鏈表的頭指針};如何定義樹的孩子表示法呢？孩子表示法childnext孩子結(jié)點(diǎn)datafirstChild表頭結(jié)點(diǎn)ACBGFEDHI如何查找孩子結(jié)點(diǎn)？時(shí)間性能？O(1)12∧345∧7∧68∧∧∧∧∧∧firstchild

012345678

ABCDEFGHIdata孩子表示法ACBGFEDHI如何查找雙親結(jié)點(diǎn)？時(shí)間性能？O(n)12∧345∧7∧68∧∧∧∧∧∧firstchild

ABCDEFGHIdata012345678

ABCDEFGHIdata

parent-100111224孩子表示法4-3-3樹的孩子兄弟表示法v第四章樹和二叉樹孩子兄弟表示法CBGFEDHIA樹的孩子兄弟表示法（二叉鏈表）：鏈表中的每個(gè)結(jié)點(diǎn)包括數(shù)據(jù)域和分別指向該結(jié)點(diǎn)的第一個(gè)孩子和右兄弟的指針某結(jié)點(diǎn)的第一個(gè)孩子是惟一的某結(jié)點(diǎn)的右兄弟是惟一的設(shè)置兩個(gè)分別指向該結(jié)點(diǎn)的第一個(gè)孩子和右兄弟的指針CBGFEDHIA

B∧

D

C

F

I

G∧

H∧

E∧∧∧∧∧∧∧

A孩子兄弟表示法樹的孩子兄弟表示法（二叉鏈表）：鏈表中的每個(gè)結(jié)點(diǎn)包括數(shù)據(jù)域和分別指向該結(jié)點(diǎn)的第一個(gè)孩子和右兄弟的指針如何定義樹的孩子兄弟存儲(chǔ)結(jié)構(gòu)?firstChilddata

rightSibtemplate<typenameDataType>structTNode{

DataTypedata;

TNode<DataType>*firstChild,*rightSib;};

孩子兄弟表示法

A

B

C

D

E

F

G

H

I∧∧∧∧∧∧∧∧∧∧ACBGF