数据结构C语言CHAP61

第六章树和二叉树第六章树和二叉树基本内容

二叉树的概念、性质和存储结构；二叉树的遍历和线索化算法；树的定义、存储结构、树与二叉树的转换、树的遍历；哈夫曼树的构造；学习要点

1．

掌握二叉树的结构特性，

2．

熟悉二叉树的各种存储结构的特点及适用范围；

3．

遍历二叉树是二叉树各种操作的基础。掌握各种遍历策略的递归算法，能灵活运用遍历算法实现二叉树的其他操作；

4．

理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。

5．

熟悉树的各种存储结构及其特点，掌握树和与二叉树的转换方法，掌握树的遍历方法；

6．

了解哈夫曼树的特性，掌握构造哈夫曼树和哈夫曼编码的方法；第六章树和二叉树第六章树和二叉树6.1树的有关概念6.2二叉树6.3二叉树的遍历6.4遍历的应用6.5线索二叉树6.6树和森林6.7哈夫曼树及应用第六章树和二叉树6.1

树的有关概念1.树的概念2.树的应用3.树的表示树的有关术语5树的基本操作6.1

树的有关概念1．树的概念树结构（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。树是n个结点的有限集合，在任一棵非空树中：

（1）有且仅有一个称为根的结点。

（2）其余结点可分为个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。树是递归结构，在树的定义中又用到了树的概念JIACBDHGFE6.1

树的有关概念例：下面的图是一棵树T={A,B,C,D,E,F,G,H,I,J}A是根，其余结点可以划分为3个互不相交的集合：

T1={B,E,F},T2={C,D},T3={D,H,I,J}这些集合中的每一集合都本身又是一棵树，它们是A的子树。

例如对于T11，B是根，其余结点可以划分为2个互不相交的集合：T11={E}，T12={F}，T11,T12是B的子树。JIACBDHGFE6.1

树的有关概念从逻辑结构看：

1）树中只有根结点没有前趋；

2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；

4）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构JIACBDHGFE6.1

树的有关概念2．树的应用

1）树可表示具有分枝结构关系的对象

例1．家族族谱设某家庭有10个成员A、B、C、D、E、F、G、H、I、J，他们之间的关系可下图所示的树表示：例2．单位行政机构的组织关系JIACBDHGFE6.1

树的有关概念2）树是常用的数据组织形式

有些应用中数据元素之间并不存在间分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。

例3计算机的文件系统

不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。文件夹1文件夹n文件1文件2文件夹11文件夹12文件11文件12C6.1

树的有关概念3）一些应用问题的求解过程可用树结构的来描述

一些应用问题的求解过程可用树结构的来描述，以帮助程序员写出求解问题的程序或算法。

例4求集合的幂集

例如求集合A={1，2，3}的幂集显然集合A中所有即为该树的所有叶子，求集合A所有子集即为求该树的所有叶子。{1}{}{1,2}{1}{2}{}{1,2,3}{1,2}{1,3}{1}{2,3}{2}{3}{}{}集合中每个元素对于子集来说，要么属于该子集，要么不属于该子集例如1不属于{2，3}，左面的树从空集开始，构造集合的子集考虑元素1考虑元素2考虑元素36.1

树的有关概念3树的表示

1）图示表示

2）二元组表示

3）文氏图表示

4）凹人表示法（类似书的目录）

5）广义表表示

6.1

树的有关概念树的基本术语树的结点：包含一个数据元素及若干指向子树的分支；

孩子结点：结点的子树的根称为该结点的孩子；

双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；

兄弟结点：同一双亲的孩子结点；

堂兄结点：同一层上结点；

结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；

树的高度：树中最大的结点层

结点的度：结点子树的个数

树的度：树中最大的结点度。

叶子结点：也叫终端结点，是度为0的结点；

分枝结点：度不为0的结点；

森林；互不相交的树集合；

有序树：子树有序的树，如：家族树；

无序树：不考虑子树的顺序；6.1

树的有关概念5树的基本操作树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：

（以DOS文元件系统为例解释树的基本操作）1）InitTree(&T);2）DestroyTree(&T);3）CreateTree(&T,definition);4）ClearTree(&T);5）TreeEmpty(T);6）TreeDepth(T);7）Root(T);8）Value(T,&cur_e);9）Assign(T,cur_e,value);10）Paret(T,cur_e);11）LeftChild(T,cur_e);12）RightSibling(T,cur_e);13）InsertChild(&T,&p,i,c);14）DeleteChild(&T,&p,i);15）TraverseTree(T,Visit());6．2二叉树

树是一种分枝结构的对象，在树的概念中，对每一个结点孩子的个数没有限制，因此树的形态多种多样，本章我们主要讨论一种最简单的树——二叉树。第六章树和二叉树6.2二叉树一二叉树的概念二二叉树的性质三二叉树的存储结构6.2二叉树一二叉树的概念1二叉树的定义二叉树：或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。说明1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于2;2）左、右子树不能颠例——有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;

A

F

G

E

D

C

B6.2二叉树

A

F

G

E

D

C

B

(a)、(b)是不同的二叉树，(a)的左子树有四个结点，(b)的左子树有两个结点，(a)

A

G

E

D

B

C

F(b)6.2二叉树

2．二叉树的基本形态

φ6.2二叉树3．应用举例例1可以用二叉树表示表达式

a+b*(c-d)-e/f

e

d

c

b

f

a

+

*

/

-

-6.2二叉树例2双人比赛的所有可能的结局

甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙开始开局连赢两局或五局三胜6.2二叉树例3树能用二叉树表示6.2二叉树二二叉树性质性质1在二叉树的第i层上最多有2i-1个结点性质2深度为k的二叉树最多有2k-1个结点性质3设二叉树叶子结点数为n0，度为2的结点n2设，则n0=

n2+1

A

F

G

E

D

C

B6.2二叉树两种特殊的二叉树满二叉树：如果深度为k的二叉树，有2k-1个结点则称为满二叉树；

A

G

F

E

D

C

B

A

C

BK=3的满二叉树K=2的满二叉树6.2二叉树完全二叉树：如果一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树；

A

E

D

C

B

G

A

E

D

C

B(a)(c)(b)、(b)完全二叉树(c)不是完全二叉树

A

G

F

E

D

C

B6.2二叉树下面是两个关于完全二叉树的性质性质4具有n个结点的完全二叉树的深度为：log2n+1对完全二叉树的结点编号：从上到下，每一层从左到右

A

F

E

D

C

B123456性质5：在完全二叉树中编号为i的结点，1）若有左孩子，则左孩编号为2i；2）若有右孩子，则有孩子结点编号为2i+1；3）若有双亲，则双亲结点编号为i/2；6.2二叉树三．二叉树存贮结构

1二叉树的顺序结构完全二叉树的顺序结构用一组连续的内存单元，按编号顺序依次存储完全二叉树的元素

顺序结构图示

1234567m-1

ABCDEF

A

F

E

D

C

B1234566.2二叉树二叉树的顺序结构假想，我们补齐二叉树所缺少的那些结点，对二叉树结点编号。用这种方式对二叉树结点编号，则在二叉树中编号为i的结点，1）若有左孩子，则左孩编号为2i；2）若有右孩子，则有孩子结点编号为2i+1；3）若有双亲，则双亲结点编号为i/2；

A

F

G

E

D

C

B167245389

A

F

G

E

D

C

B6.2二叉树167245389

A

F

G

E

D

C

B123456789m-1

AB

C

DE

F

G二叉树的顺序结构图示将二叉树原有的结点按编号存储到内存单元“相应”的位置上6.2二叉树2二叉链表二叉链表中每个结点至少包含三个域：数据域、左指针域、右指针域∧

D

A

B

∧C

∧∧

E

∧∧

F

∧

A

F

E

D

C

B3三叉链表三叉链表中每个结点至少包含四个域：数据域、双亲指针域、左指针域、右指针域二叉链表图示6.2二叉树4

静态链表上面们二叉链表或三叉链表是用指针实现，是一种动态的链式存储结构，链式存储结构也可用一维数组来实现，用一维数组表示的二叉链表或三叉链表，称为静态链表

A

F

E

D

C

B孩子结点在数组中的位置0表示无左或右孩子静态二叉链表A13C05B00E00F00D4

0123456Lchilddatarchild第六章树和二叉树6.3二叉树的遍历一.二叉树的遍历方法二.遍历的递归算法6.3二叉树的遍历遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现。

对于线性结构由于每个结点只有一个直接后继，遍历是很容易的事

二叉树是非线性结构，每个结点可能有两个后继，如何访问二叉树的每个结点，而且每个结点仅被访问一次？

6.3二叉树的遍历二叉树的遍历方法二叉树由根、左子树、右子树三部分组成二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树令：L：遍历左子树

D：访问根结点

R：遍历右子树

有六种遍历方法：

DLR，LDR，LRD，

DRL，RDL，RLD

约定先左后右,有三种遍历方法：DLR、LDR、LRD

，分别称为

先序遍历、中序遍历、后序遍历

A

F

G

E

D

C

B6.3二叉树的遍历先序遍历（DLR）

若二叉树非空

（1）访问根结点；（2）先序遍历左子树；

（3）先序遍历右子树；

先序遍历序列：A,B,D,E,G,C,F

A

F

G

E

D

C

B例：先序遍历右图所示的二叉树（1）访问根结点A（2）先序遍历左子树：即按DLR的顺序遍历左子树（3）先序遍历右子树：即按DLR的顺序遍历右子树6.3二叉树的遍历中序遍历（LDR）若二叉树非空

（1）中序遍历左子树

（2）访问根结点（3）中序遍历右子树

中序遍历序列：D,B,G,E,A,C,F

A

F

G

E

D

C

B例：中序遍历右图所示的二叉树

（1）中序遍历左子树：即按LDR的顺序遍历左子树

（2）访问根结点A

（3）中序遍历右子树：即按LDR的顺序遍历右子树6.3二叉树的遍历后序遍历（LRD）若二叉树非空

（1）后序遍历左子树

（2）后序遍历右子树（3）访问根结点

后序遍历序列：D,G,E,B,F,C,A例：后序遍历右图所示的二叉树

（1）后序遍历左子树：即按LRD的顺序遍历左子树

（2）后序遍历右子树：即按LRD的顺序遍历右子树（3）访问根结点A

A

F

G

E

D

C

B6.3二叉树的遍历

e

d

c

b

f

a

+

*

/

-

-

后序遍历序列：a,b,c,d,-,*,+,e,f,/,-

中序遍历序列：a,+,b,*,c,-,d,-,e,/,f

先序遍历序列：-,+,a,*,b,-,c,d,/,e,f例：先中序遍历序遍历、中序遍历、后序遍历下图所示的二叉树6.3二叉树的遍历这实际上是先序遍历的递归定义，我们知道递归定义包括两个部分：1）基本项（也叫终止项）；2）递归项若二叉树非空（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；先序遍历递归定义递归项二.遍历的递归算法

上面介绍了三种遍历方法，显然是用递归的方式给出的三种遍历方法，以先序为例：先序遍历（DLR）的定义：该定义隐含着若二叉树为空，结束6.3二叉树的遍历上面先序遍历的定义等价于：若二叉树为空，结束——基本项（也叫终止项）若二叉树非空——递归项（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；下面给出先序、中序、后序遍历递归算法，为了增加算法的可读性，这里对书上算法作了简化，没有考虑访问结点出错的情况（即我们假设调用函数visit()访问结点总是成功的。6.3二叉树的遍历先序遍历递归算法

voidPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉链表存贮二叉树，visit()是访问结点的函数。本算法先序//遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit()

if(T){//若二叉树为空，结束返回

//若二叉树不为空，访问根结点；遍历左子树，遍历右子树

Visit(T->data)；

PreOrderTraverse(T->lchild,Visit);

PreOrderTraverse(T->rchild,Visit);

}//PreOrderTraverse最简单的Visit函数是：

StatusPrintElement(TElemTypee){//输出元素e的值

printf(e);

returnOK;}

∧

D

A

B

∧C

∧∧

E

∧∧

F

∧T6.3二叉树的遍历2中序遍历递归算法

voidInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉链表存贮二叉树，visit()是访问结点的函数。本算法中序//遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit()

if(T){//若二叉树为空，结束返回

//若二叉树不为空，遍历左子树，访问根结点，遍历右子树

InOrderTraverse(T->lchild,Visit);Visit(T->data)；

InOrderTraverse(T->rchild,Visit);

}//InOrderTraverse

你能写出后序遍历递归算法了吧6.3二叉树的遍历3后序遍历递归算法

void

PostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉链表存贮二叉树，visit()是访问结点的函数。本算法中序//遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit()

if(T){//若二叉树为空，结束返回

//若二叉树不为空，遍历左子树，遍历右子树，访问根结点

PostOrderTraverse(T->lchild,Visit);

PostOrderTraverse(T->rchild,Visit);Visit(T->data)；

}//PostOrderTraverse

第六章树和二叉树6.4遍历的应用

1.求二叉树的叶子结点个数2.建立二叉链表

6.4遍历的应用遍历是二叉树的基本操作：二叉树许多操作可在遍历过程中完成，如二叉树线索化，就是在对二叉树进行中序遍历时加上线索的。本节再例子举几个二叉树遍历应用实例。6.4遍历的应用例1编写

求二叉树的叶子结点个数的算法

输入：二叉树的二叉链表

结果：二叉树的叶子结点个数基本思想：遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。所以可在二叉树遍历的过程中，统计叶子结点的个数。∧

D

A

B

∧C

∧∧

E

∧∧

F

∧Tvoidleaf(BiTreeT){//采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点//的个数。本算法在先序遍历二叉树的过程中，统计叶子结点的个数//第一次被调用时，n=0if(T){//若二叉树为空，结束返回

//若二叉树不为空，在先序遍历二叉树的过程中，统计叶子结点的个数if(T->lchild==null&&T->rchild==null)n=n+1;leaf(T->lchild);leaf(T->rchild);}//if}//leafvoidleaf(BiTreeT){//采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点,的个数。//本算法在先序遍历二叉树的过程中，统计叶子结点的个数第一次被调用时，n=0if(T){//若二叉树为空，结束返回

//若二叉树不为空，在先序遍历二叉树的过程中，统计叶子结点的个数if(T->lchild==null&&T->rchild==null)n=n+1;leaf(T->lchild);leaf(T->rchild);}//if}//leaf6.4遍历的应用

viodPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉链表存贮二叉树，visit()是访问结点的函数。本算法先序//遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit()

if(T){//若二叉树为空，返回

//若二叉树不为空，访问根结点；遍历左子树，遍历右子树

Visit(T->data)；

PreOrderTraverse(T->lchild,Visit);

PreOrderTraverse(T->rchild,Visit);

}//PreOrderTraverse比较先序遍历算法和计算叶子结点算法，有什么相同和不同？结构类似函数名不同访问结点时调用visit()访问结点时统计叶子结点的个数6.4遍历的应用例2为二叉树建立二叉链表

输入：二叉树的先序序列

结果：二叉树的二叉链表

遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可在利用遍历，建立二叉链表的所有结点并完成相应结点的链接？基本思想：输入（在空子树处添加*的二叉树的）先序序列（设每个元素是一个字符//）按先序编历的顺序，建立二叉链表的所有结点并完成相应结点的链接6.4遍历的应用∧

D

A

B

∧C

∧∧

E

∧∧

F

∧T先序序列：ABDFCE（在空子树处添加*的二叉树的）先序序列：ABD*F**CE***

A

F

E

D

C

B*******

A

F

E

D

C

B6.4遍历的应用StatusCreateBiTree(BiTree&T){//输入（在空子树处添加*的二叉树的）先序序列（设每个元素是一个字//符）按先序编历的顺序，建立二叉链表，并将该二叉链表根结点指针//赋给T

scanf(&ch);if(ch==‘*’)T=NULL;//若ch==‘*’则T=NULL返回else{//若ch!=‘*’if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->date=ch;//建立（根）结点

CreateBiTree(T->lchild);//构造左子树链表，并将左子树根结点指针//赋给（根）结点的左孩子域CreateBiTree(T->rchild);//构造右子树链表，并将右子树根结点指针//赋给（根）结点的右孩子域}

returnOK;}//CreateBiTree小结

小结1二叉树：或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树；2二叉树即可以用顺序结构存储，也可用链式结构存储；3遍历：按某种搜索路径访问二叉树的每个结点，每个结点仅被访问一次。二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树，本课程介绍了三种遍历算法：先序遍历、中序遍历、后序遍历；习题十1P386.12对P396.15给出的二叉树求出以下的遍历序列：（1）先序序列（2）中序序列（3）后序序列3编写

求二叉树的分枝结点个数的算法（用二叉链表存贮二叉树习题取自数据结构题集C语言版严尉敏等编清华大学出版社第六章习题第六章树和二叉树6.4线索二叉树1.线索二叉树的概念2线索链表3.线索二叉树的遍历6.5线索二叉树1线索二叉树

遍历是二叉树最基本最常用的操作。

1）对二叉树所有结点做某种处理可在遍历过程中实现；

2）检索（查找）二叉树某个结点，可通过遍历实现；

与线性表相比，对二叉树的遍历存在如下问题：1）遍历算法要复杂的多，费时的多；2）为检索或查找二叉树中某结点在某种遍历下的后继，必须从根开始遍历，直到找到该结点及后继；

如果能将二叉树线性化，就可以减化遍历算法，提高遍历速度。如何将二叉树线性化？

以中序遍历为例，我们看到通过遍历可以得到二叉树结点的中序序列。若能将中序序列中每个结点前趋、后继信息保存起来，以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二叉树进行遍历。

加上结点前趋后继信息（结索）的二叉树称为线索二叉树6.5线索二叉树中序遍历序列：D,B,H,E,A,F,C,G在中序序列中，D的后继是B，H的前趋是B，后继是E…

A

G

H

E

D

C

B

F加上结点前趋后继信息（结索）的二叉树称为线索二叉树线索二叉树孩子指针前趋指针后继指针6.5线索二叉树2．线索链表

线索二叉树的存贮方法：

1）

为每个结点增加二个指针域。

缺点：要点用较多的内存空间。每个n个结点的二叉链表，有n+1个空指针域，故可利用这些的空指针域存放结点的前趋和后继指针，以这种结点的构成二叉链表称为线索链表T∧

D

A

B

C

∧

F

∧∧

H∧

E

∧∧

G

∧6.5线索二叉树

线索链表的类型说明typedefenum{link,thread}PointerTag;//link=0,thread=1typedefstructBiThrNode{

TElemTypedata;

StructBiThrNode*lchild,*rchild;//左右指针域

PointerTagLtag,Rtag;//左右标志域，标志域为0时，表示左右指针//域存储的是左右孩子的指针，标志域为1时，表示左右指针域存储的是//前趋后继结点的指针}BiThrNode，*BiThrTreeLchildlTagdataRTagrchildF11E01G10D01A00B00H11C006.5线索二叉树线索链表图示线索二叉树

A

G

H

E

D

C

B

F孩子指针前趋指针后继指针

6.5线索二叉树为简化线索链表的遍历算法，仿照线性链表，为线索链表加上一头结点

约定：

头结点的lchild域：存放线索链表的根结点指针；

头结点的rchild域:中序序列最后一个结点的指针；

中序序列第一结点lchild域指向头结点;

中序序列最后一个结点的rchild域指向头结点;F11E01G11D11A00B00H11C0001头结点6.5线索二叉树如图标出的中序二叉树结点的顺序，可看出1）中序序列的第一结点，是二叉树的最左下结点；2）若p所指结点的右孩子域为线索，则p的右孩子结点即为后继结点；3）若p所指结点的右孩子域为孩子指针，则p的后继结点为其右子树的最左下结点；F11E01G11D11A00B00H11C0001头结点①②③

中序遍历序列：D,B,H,E,A,F,C,G6.5线索二叉树3．线索二叉树的遍历

在二叉树上加上结点前趋、后继线索后，可利用线索对二叉树进行遍历。

下面是线索链表的遍历算法。

基本步骤：1）p=T->lchild;p指向线索链表的根结点；2）若线索链表非空，循环：（a）循环，顺着p左孩子指针找到最左下结点；访问之；（b）若p所指结点的右孩子域为线索，p的右孩子结点即为后继结点循环：p=p->rchild；并访问p所指结点；（在此循环中，顺着后继线索访问二叉树中的结点）（c）一旦线索“中断”，p所指结点的右孩子域为右孩子指针，p=p->rchild，使p指向右孩子结点；3）返回OK；结束6.5线索二叉树线索链表的遍历算法VoidInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TE1emTypee)){//T指向头结点，头结点的左链lchild指向根结点，//中序遍历二叉线索树T算法，对每个数据元素调用函数Visit。P=T->lchild;//p指向根结点While(p!=T){//空树或遍历结束时，p==TWhile(p->Ltag==Link)p=p->lchild;//找到最左下结点；访问之Visit(p->data))while(p->Rtag==Thread&&p->rchild!=T){//若p所指结点的右孩子域为线索//且不是最后一个结点p=p->rchild;Visit(p->data);//访问后继结点}p=p->rchild;}returnOK;}//InOrderTraverse_Thr为了增加算法的可读性，这里对书上算法作了简化，没有考虑访问结点出错的情况（即我们假设调用函数visit()访问结点总是成功的。第六章树和二叉树6.6树和森林一.树的存储结构二.树和二叉树的转换三.

树的遍历四.森林

6.6树和森林

一．树的存贮结构在树中，每个结点即可能有孩子也可能有双亲，所以既可以通过保存每个结点的孩子结点位置来表示结点之间的结构关系，也双亲表示法通过通过保存每个结点的双亲结点位置来表示结点之间的结构关系。

1双亲表示法双亲表示法：通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。用一组连续的内存单元存储数的结点，每个结点包含两个域：一个数据域，一个“指针域”，用于指示其双亲结点在数组中的位置6.6树和森林双亲表示类型定义

#defineMAX_TREEE_SIZE100typedefstructPTNode{

TelemTypedata;

intparent;//双亲位置域}PTNode;typedefstruct{

PTNodenodes[MAX_TREE_SIZE];

Intn;//结点数}Ptree;IACBDHGFE双亲表示图示A-1B0C0D0E1F1G2H3I3012345678.dataparent9T.nodesT.n结点数双亲结点在数组中的位置-1表示无双亲

6.6树和森林2、孩子表示法孩子表示法：通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。

与双亲表示法相反，孩子表示法适合实现涉及孩子的操作。还可以将双亲表示与孩子表示法结合：带双亲的孩子链表。

方法1：多重链表（类似二叉链表）

两种方式：定长结点不定长结点定长结点

优点结点结构一致，便于实现树的操作。缺点是浪费一些内存。

不定长结点

优点：节省内存

缺点：不定长会使一些操作实现复杂一些6.6树和森林方式II：孩子链表（可以不看）孩子链表：对树的每个结点用线性链表存贮它的孩子结点树的孩子链表类型定义typedefstructCTNode{//孩子结点

intchild;

str