资源描述：
《数据结构ppt教学课件第6章树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、6.1树的基本概念和术语6.2二叉树6.3遍历二叉树6.4线索二叉树6.5二叉树、树和森林6.6树的应用6.7二叉树的建立和遍历C语言源程序示例第6章树返回主目录第6章树6.1树的基本概念和术语6.1.1树的定义树（tree）是由一个或多个结点组成的有限集合T。其中:(1)有一个特定的结点称为该树的根（root）结点;(2)除根结点之外的其余结点可分为m（m≥0）个互不相交的有限集合T1,T2,…,Tm,且其中每一个集合本身又是一棵树,称之为根的子树（subtree）。这是一个递归的定义,即在定义中又用到了树这个术语。它
2、反应了树的固有特性。可以认为仅有一个根结点的树是最小树,树中结点较多时,每个结点都是某一棵子树的根。图6.1是一棵由11个结点组成的树T。其中A是根结点,其余结点分为三个互不相交的子集:T1={B,E,F},T2={C,G},T3={D,H,I,J,K}。T1、T2、T3都是树根Ａ的子树,这三棵子树的根结点分别是B、C、D。每棵子树本身也是一棵树,可继续划分。例如子树T3以D为根结点,它的其余结点又可分为三个互不相交的子集:T31={H},T32={I,K},T33={J},而其中T31、T33都可认为是仅有一个根结点的子树。6.
3、1.2树的常用术语树结构常常用到一些术语,如度、双亲、孩子、树深等。结点的度是结点的子树的个数。树的度是树中结点度的最大值。度为零的结点称为叶子或终结点。度不为零的结点称为非终端结点。图6.1中树T的度为３。结点E,F,G,H,K,J度为零,它们是叶子结点。某结点的各子树的根结点称为该结点的孩子,而该结点又称为孩子们的双亲结点。具有相同双亲的结点互称为兄弟。图6.1中根结点A有三棵子树,这三棵子树的根结点分别是B,C,D,因此说结点A是结点B,C,D的双亲,而结点B,C,D又都是结点A的孩子,B,C,D之间互为兄弟。一棵树上除根结点以外的
4、其它结点称为根结点的子孙。对于树中某结点,从根结点开始到该结点的双亲是该结点的祖先。结点的层次值从根算起,根的层次值为１,其余结点的层次值为双亲结点层次值加１。一棵树的深度是该树中结点最大层次值,例如图6.1中的树T的深度为４。结点A、B、E、K的层次值分别为1、2、3、4。6.1.3树的表示方法树的表示形式有多种,常见的三种方法是:(1)倒悬树法,如图6.1所示。(2)集合包含关系文氏图法,如图6.2(a)所示。(3)凹入法,如图6.2(b)所示。6.2二叉树6.2.1二叉树的定义二叉树（binarytree）是n（n>=0）
5、个结点的有限集合。它或为空树（n=0）,或为非空树;对于非空树有:(1)有一个特定的称之为根的结点。(2)除根结点以外的其余结点分为两个互不相交的称之为左子树和右子树的二叉树构成。这个定义是递归的。由于左、右子树也是二叉树,因此子树也可为空树。图6.3中展现了五种基本形态不同的二叉树。6.2.2二叉树的重要性质性质1二叉树第i(i≥1)层上至多有2i-1个结点。根据图6.4(a)可知,根结点在第一层上,这层结点数最多为1个,即20个;显然第二层上最多有2个结点,即21个;…假设第i-1层的结点最多有2i-2个,且每个结点最多有
6、两个孩子,那么第i层上结点最多有2*2i-2=2i-1个。性质2深度为k(k≥1)的二叉树至多有2i-k个结点。由性质1可知各层结点最多数目之和为20+21+22+…+2k-1;由二进制换算关系可知:20+21+22+…+2k-1=20,因此二叉树树中结点的最大数目为20。性质3在任意二叉树中,若叶子结点（即度为零的结点）个数为n0,度为1的结点个数为n1,度为2的结点个数为n2,那么n0=n2+1。设n代表二叉树结点总数,那么n=n0+n1+n2(6.1) 由于有n个结点的二叉树总边数为n-1条,于是得n-1=0*n0+
7、1*n1+2*n2(6.2)将式(6.1)代入式(6.2)得n0=n2+1有两种特殊形态的二叉树,它们是满二叉树和完全二叉树。深度为k并且含有2k-1个结点的二叉树称为满二叉树,这种树的特点是每层上的结点数都是最大结点数,如图6.4(a)所示。对满二叉树的结点可以从根结点开始自上向下,自左至右顺序编号,图6.4(a)中每个结点斜上角的数字即是该结点的编号。深度为k,含有n个结点的二叉树,当且仅当每个结点的编号与相应满二叉树结点顺序编号从1到n相对应时,则称此二叉树为完全二叉树,如图6.4(b)所示。而图6.4(c)则不是完全二叉树。
8、质4具有n个结点的完全二叉树树深为［log2n］+1（其中［x］表示不大于x的最大整数）。性质5若对有n个结点的完全二叉树进行顺序编号(1≤i≤n),那么,对于编号为i(i≥1)的结点
