《数据结构——用C语言描述（第二版）》-宁正元-电子教案 第6章 树

6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树 6.4 线索二叉树 6.5 树和森林 6.6 哈夫曼树,第6章 树,树形结构是一种应用十分广泛和重要的非线性数据结构，是一种以分支关系定义的层次结构。在这种结构中，每个数据元素至多只有一个前趋，但可以有多个后继；数据元素之间的关系是一对多的层次关系。树形结构主要用于描述客观世界中具有层次结构的数据关系。 本章重点讨论树与二叉树的概念、性质、存贮结构及其各种运算，并研究一般树、森林和二叉树的转换关系；此外，作为树形结构的应用，介绍了哈夫曼树及其哈夫曼编码。,第6章 树,6.1.1 树的定义及表示 1、树形结构示例,6.1 树的基本概念,2、树的定义 树（Tree）是n（n0）个结点的有限集合T，当n=0时称为空树，否则，称为非空树。在任一棵非空树中： （1）有且仅有一个称为树根的结点。 （2）除根结点之外的其余结点可分为m（m0）个互不相交的集合T1，T2，Tm，其中每一个集合本身又都是一棵树，一般称为根的子树。 树的定义是一个递归的定义，它反映了树的固有特性，即一棵树由若干棵子树构成，且各子树间互不相交，而每棵子树又由若干棵更小的子树构成。例如，在图6.2中，（a）是只有一个根结点的树；（b）是有8个结点的一般树，其中A是根，其余结点分成三个互不相交的子集：T1=B、E、F，T2 =C，T3=D、G、H，而且它们都是A的子树，且其本身也是一棵树。,3、树的表示 树的表示方法有树形表示、集合表示、凹入表示和广义表等4种。图6.3给出了树的其它表示形式，如（a）为集合表示法或范氏图法，（b）为凹入表示法或缩格法，（c）为广义表表示法或嵌套括弧法等。,6.1.2 树的常用术语 树的结点：是指一个数据元素及若干指向其子树的分支，通常用一个结构体或记录来描述，在树形表示中用一个圆圈及短线表示。 结点的度：是指结点的子树数目。 叶子或终端结点：是指度为零的结点。 分支结点或非终端结点：是指度不为零的结点。 树的度：是指树中各结点度的最大值。 有时，在实际应用中也引用家族树中的一些习惯用语来描述树，如孩子、双亲、祖先、子孙和兄弟等。如将某结点的子树的根称为该结点的孩子，相应地，将该结点称为孩子的双亲；同一个双亲的孩子之间互称为兄弟等等。祖先则是从根结点到该结点所经过分支上的所有结点，而以某结点作为根的子树中任一个结点都称为该结点的子孙。,结点的层次：从根开始定义，根为第一层，根的孩子为第二层，以此类推，即设根结点的层数为1，其余结点的层数等于其双亲结点的层数加1。若某结点在第i层，则其孩子结点就在第i+1层。 树的深度或高度：是指树中结点的最大层次数。 路径：若树中存在一个结点序列k1，k2，kj，使得ki是k i1的双亲（1ij），则称该结点序列是从k1到kj的一条路径，且路径的长度为j-1，即等于路径上分支的数目。在树形表示中，路径表示从k1出发自上而下地通过k2，k3，kj各结点。 有序树和无序树：若将树中每个结点的各子树看成是从左至右有序且不能交换，则称该树为有序树，否则称为无序树。图6.4给出了两棵不同的有序树。,图6.4 两棵不同的有序树,森林：是指m（m0）棵互不相交的树的集合。 显然，树形结构不同于线性结构。在树中，一个结点至多只有一个直接前趋（双亲），却可以有多个直接后继（孩子），即结点之间的关系不象线性结构中的结点关系是一一对应关系，而是呈现出一对多的层次关系。,6.1.3 树的基本运算 （1）setnull(T) ：置T为空树，即初始化一棵树T。 （2）root(T)或root(x)：求根函数。 （3）parent(T，x)：求双亲函数。 （4）child(T，x，i)：求孩子结点函数。 （5）rsibling(T，x)：求右兄弟函数。 （6）create(x，F)：建树函数。 （7）delchild(x，i)：子树删除操作。 （8）addchild(y，i，x)：插入子树操作。 （9）traverse(T)：树的遍历操作。,二叉树（Binary Tree）是另一种重要的树形结构，在实际应用中具有重要的意义。本节将详细地讨论二叉树的定义、重要性质、存储方式、运算及其应用。,6.2 二叉树,6.2.1 二叉树的概念及运算 1、二叉树定义 二叉树是n（0）个结点的有限集合，这个集合可以是空集合，或者由一个根结点和两棵互不相交的分别称为根的左子树和右子树的二叉树组成。显然，由定义可知，二叉树具有递归性质，它的特点是每个结点至多只有二棵子树即二叉树中任何结点的度数不大于2，而且，二叉树的子树有左右之分，其次序不能任意颠倒。应该指出的是，二叉树与树是两个不同的概念，它不是树的特殊情形，例如，在图6.5中，（a）和（b）所示的两棵二叉树虽然与（c）所示的一般树相似，但却不等同于这棵一般树。,A,图6.5 二叉树与度为2的一般树的区别举例,B,C,D,(a) 二叉树1,A,B,C,D,(b) 二叉树2,A,B,C,D,(c)一般树,2、二叉树基本形态,两种特殊形态的二叉树：满二叉树和完全二叉树。,（1）满二叉树是指一棵深度为h且有2h -1个结点的二叉树，如图6.7（a）所示是一棵深度为3的满二叉树。 （2）完全二叉树：对满二叉树中的结点按照从根结点起，自上而下，自左至右的约定进行连续编号，一棵深度为h，有n个结点的二叉树，当且仅当其每一个结点都与深度为h的满二叉树中的编号从1至n的结点一一对应时，称之为完全二叉树，如图6.7（b）所示为一棵深度为3的完全二叉树，而图6.7（c）所示就不是完全二叉树。 （3）满二叉树的每一层上具有最大的结点数，它不存在度为1的结点，所有叶子结点均在第h层上。 （4）完全二叉树的特点是所有叶子结点都只可能在最大的两层出现，第i（ih-1）层含有2i-1个结点，第h层上的结点都集中在该层最左边的位置上，换句话说，完全二叉树上的结点编号与同深度的满二叉树对应位置的结点编号相同。满二叉树是完全二叉树的特殊情形，它一定是完全二叉树，而完全二叉树不一定是满二叉树。,3、二叉树的基本运算 （1）setnull（bt）：置bt为空二叉树 （2）求根函数root（bt）或root（x） （3）求双亲函数parent（bt，x） （4）求孩子结点函数lchild（bt，x）和rchild（bt，x） （5）插入运算addlchild(b，x，y)和addrchild(bt，x，y) （6）二叉树建立运算create（x，lbt，rbt） （7）删除子树运算dellchild（bt， x）和delrchild（bt， x） （8）遍历运算traverse（bt）,6.2.2 二叉树的性质 性质1 在二叉树的第i层上至多有2i-1结点（i1）。 性质2 深度为h的二叉树至多有2h-1个结点（hl）。 性质3 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0= n21。 性质4 具有n个结点的完全二叉树的深度为log2n+1。 性质5 如果对一棵有n个结点的完全二叉树（其深度为log2n1），按照从根结点起，自上而下，从左到右的约定对所有结点从1到n进行编号，则对于任意的编号为i的结点（1in）有以下性质： （1）如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲的编号是i/2。 （2）如果2in，则结点i无左孩子（结点i为叶子结点），否则其左孩子的编号是2i。 （3）如果2i1n，则结点i无右孩子， 否则其右孩子的编号是2il。 （4）若i为奇数且不为1，则该结点左兄弟的编号是i-1，否则无左兄弟。 （5）若i为偶数且小于n，则该结点右兄弟的编号是i+1，否则无右兄弟。,6.2.3 二叉树的存储结构 1.顺序存储结构 二叉树的顺序存储是用一组地址连续的存储单元存储二叉树中的数据元素。 （1）完全二叉树 对一棵具有n个结点的完全二叉树，从树根结点起，自上层到下层，每层自左至右地给所有结点编号，然后将完全二叉树中的所有结点按编号顺序依次存储在一维数组R1n中，如图6.8（a）所示。 （2）一般二叉树 一般二叉树也必须按完全二叉树的形式来存储一般二叉树中的结点，只有通过添加一些并不存在的“虚结点”，使之成为完全二叉树的形式才行，如图6.8（b）所示。 在最坏的情况下，一个深度为h且只有h个结点的右单支树需要2h-1个的结点空间。所以，不宜采用顺序存储结构存储一般的二叉树。,2.链式存储结构 （1）二叉链表 采用链式存储结构来存储二叉树，而且设计不同的结点结构可以构成不同形式的二叉树的链式存储结构。二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，所以，二叉树的链式存储结构中的结点至少应包含三个域：数据域和左、右指针域，即每个结点应包含两个指针lchild和rchild，分别指向该结点的左孩子和右孩子。其结点结构形式如图6.9所示。,结点类型定义： typedef struct node datatype data； /*数据域*/ struct node *lchild，*rchild；/*左、右孩子域* btnode，*bitree； 在一棵二叉树中，所有类型为btnode的结点，加上一个指向根结点的头指针，就可构成二叉树的链式存储结构，有时将这种存储结构称为二叉链表，如图6.10所示。一个二叉链表可以由头指针唯一地确定 。 采用二叉链表作为二叉树的链式存储结构便于从根结点开始往下搜索孩子或子孙结点。,（3）三叉链表 有时，为了便于检索结点的双亲或祖先结点，可在结点结构中增加一个指向其双亲结点的指针域（如图6.11（a）中的parent），这种结构称为三叉链表，如图6.11所示即为图6.10（a）中二叉树所对应的三叉链表。,6.2.4 二叉树的简单运算实现 这里所讨论的运算实现算法，以二叉链表作为其存储结构。 （1）置空二叉树setnull(bt) void setnull(bitree bt) bt-lchild=NULL； /*左链域置空*/ bt-rchild=NULL； /*右链域置空*/ （2）求二叉树的根root(bt) datatype root(bitree bt) if(bt-lchild=NULL) return NULL；/*空树时返回NULL*/ else return（bt-lchild-data）；/*否则返回根结点数据域的值*/ ,（3）建立二叉树操作create(x，lbt，rbt) bitree create(datatype x，bitree lbt，bitree rbt) bitree p； p=(bitree)malloc(sizeof(btnode)； /*申请一个结点空间，地址传给p指针*/ p-data=x； p-lchild=lbt； /*把二叉树lbt填入p的左孩子链域*/ p-rchild=rbt； /*把二叉树rbt填入p的右孩子链域*/ return p； /*返回建成的二叉树*/ （4）插入左孩子addlchild(bt，x) void addlchild(bitree bt，datatype x) bitree p； p=(bitree)malloc(sizeof(btnode)； /*申请一个结点空间*/ p-data=x； p-lchild=NULL； p-rchild=NULL； /*左、右孩子域置空*/ bt-lchild=p； /*插入bt的左孩子域*/ ,（5）删除左孩子dellchild(bt) void dellchild(bitree bt) bitree p； p=bt-lchild； /*保存左子树指针*/ bt-lchild=NULL；/*bt的左孩子域置空*/ free (p)； /*释放左子树空间*/ ,在实际应用中，常常要求在二叉树中检索或查找具