数据结构c语言版树和叉树.pptVIP

学习目标与重点： ◆掌握二叉树的存储结构； ◆掌握二叉树的性质和存储结构； ◆熟练掌握二叉树的遍历； ◆掌握哈夫曼树及哈夫曼编码。 6.1 树的定义和基本术语 1、树(Tree)的定义 树是n（n≥0 ）个结点的有限集。在任意一棵非空树中： （1）有且仅有一个特殊的称为根(Root)的结点 ； （2）当n＞1时，其余结点可分成m（m ＞0）个互不相交的有限集T1,T2, …,T m， 其中每一个集合本身又是一棵树，并 且称为根的子树（Sub Tree）。 如图6.1：A为根结点; （B，E，F）、 （C，G，H，J，K，L，M）、 （D，I）分别为根结点A的三棵子树。 B，C，D分别为三棵子树的根结点。 显然这是一个递归定义。 图6.1 树的示意图 2、树中结点的度(Degree)与树的度 树中每个结点的分枝数称为该结点的度。 例如图6.1中根结点A的度为3。B的度为2。G的度为4。 而E，F，H，I，J，K，L，M的度全为零。 树的度是树中结点的最大度数。所以图6.1的度为4。 在实际应用中我们称度为零的结 点为叶子(Leaf)结点，称度不为 零的结点为分枝结点。 如图6.1中E，F ，H，I，J，K， L，M都是叶子结点，B，C，D， G都是分枝结点。 从树中我们知道度为4的树中结 点的度有0，1，2，3，4五种。 因而可推知度为m的树中结点的度有m+1种。 3、孩子(Child)结点与双亲(Parent)结点 树中结点的子树的根结点称为该结点的孩子结点。相反， 称该结点为孩子结点的双亲。例如图6.1中，B，C，D是根结点A 的三个孩子结点。A为B，C，D的双亲。B，C，D三个结点又互称 为兄弟(Sibling)结点（它们具有同一个双亲） 。 而E，F，G，H，I称为堂兄弟（它们 的双亲称为兄弟结点）。 祖先结点是从根结点到达某结点所经 过分枝上的所有结点通称为该结点的 祖先。例如 A，C，G为结点J，K，L， M的祖先。子孙结点以某结点为根的 子树中的任一结点都称为该结点的子 孙。例如G，H， J，K，L，M都是C的 子孙。 4、树中结点的层数(Level) 从根结点开始，根为一层结点， 其孩子结点为二层结点依次类推， 叶子结点为最下层结点。例如: 右图示。这种分层的好处是树中 结点的最大层数称为该树的高度 （深度）。所以右图（用黑数字） 所示树的高度（深度）为4。 实际应用中树也可以以根为0层结点开始，此时，结点的层数为 从根到达该结点的路径长度。如果，知道树中每层结点的个数， 便可计算出对树中所有结点查找一遍所花费的总代价。使用哪种 方式用户可根据系统需要进行选择。 5、森林（Forest) 是 m (m=0)棵互不相交的树的集合（可以看成是把一棵树的根结点去掉，所得到的子树构成森林） 。例如图6.2为图6.1去掉根结点A，以其三个孩子结点B，C，D为根的三棵子树构成的森林。 6、有序树与无序树 如果树中每个结点的孩子结点规定从左到右是有次序的（不许随意改动）那么，称该树为有序树。否则称为无序树。图6.3为相同的无序树，不同的有序树。 树的第二个定义： 就逻辑结构而言，任何一棵树都是一个二元组 Tree=(Root,F), 其中：Root是数据元素，称为树的根结点;F是 m(m=0)棵树的森林,F=(T1,T2,…Tm),其中Ti=(ri,Fi) 称为根root的第i棵子树;当M!=0时，在树根和其子树 森林之间存在下列关系： RF ={Root,ri| i= 1,2,…m,m0} 这个定义将有助于得到森林和树与二叉树之间转换 的递归定义。 6.2 二叉树（BinaryTree) 6.2.1二叉树的定义 二叉树是每个结点至多有两个孩子结点的一种树。其中两 个孩子结点分别被称为左孩子结点和右孩子结点。而以左 孩子结点为根的子树称为左子树，以右孩子结点为根的子 树称为右子树。另外，二叉树是有序树，其左右孩子的次 序不能任意颠倒。