数据结构七树和叉树.pptVIP

第七章 树和二叉树 7.1 树的基本概念 7.2 二叉树概念和性质 7.3二叉树遍历 7.4二叉树的基本运算及其实现 7.5 线索二叉树 7.6 哈夫曼树 7.1 树的基本概念 树的定义 树的表示 相关术语 树的存储 树的定义 树是由n(n≥0)个结点组成的有限集合(记为T)。 其中： 如果n=0,它是一棵空树,这是树的特例； 如果n0,这n个结点中存在(有仅存在)一个结点 作为树的根结点,简称为根(root),其余结点可分为m (m0)个互不相交的有限集T1,,T2,…,Tm,其中每一 棵子集本身又是一棵符合本定义的树,称为根root的 子树。 树的表示——树型表示法 相关术语 结点的度与树的度 树中某个结点的子树的个数称为该结点的度。 树中各结点的度的最大值称为树的度,通常将度为m的树称为m叉树。 相关术语 分支结点与叶结点 度不为零的结点称为非终端结点,又叫分支结点 度为零的结点称为终端结点或叶结点 在分支结点中,每个结点的分支数就是该结点的度 如对于度为1的结点,其分支数为1,被称为单分支结点； 对于度为2的结点,其分支数为2,被称为双分支结点 相关术语 孩子结点、双亲结点和兄弟结点 在一棵树中,每个结点的后继,被称作该结点的孩子结点(或子女结点) 该结点被称作孩子结点的双亲结点(或父母结点)。 具有同一双亲的孩子结点互为兄弟结点 把每个结点的所有子树中的结点称为该结点的子孙结点 从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先结点。 相关术语 结点的层次和树的高度 结点的层次从树根开始定义,根结点为第1层,它的孩子结点为第2层,以此类推,一个结点所在的层次为其双亲结点所在的层次加1 树中结点的最大层次称为树的高度(或树的深度)。 相关术语 有序树和无序树 若树中各结点的子树是按照一定的次序从左向右安排的,且相对次序是不能随意变换的,则称为有序树,否则称为无序树 森林 n(n＞0)个互不相交的树的集合称为森林 相关术语 路径与路径长度 对于任意两个结点ki和kj,若树中存在一个结点序列ki,ki1,ki2,…,kin,kj,使得序列中除ki外的任一结点都是其在序列中的前一个结点的后继,则称该结点序列为由ki到kj的一条路径,用路径所通过的结点序列(ki,ki1,ki2,…,kj)表示这条路径。 路径的长度等于路径所通过的结点数目减1(即路径上分支数目)。 7.2 二叉树概念和性质 二叉树的概念 二叉树的性质 二叉树的存储 二叉树的概念 定义 二叉树是有限的结点集合,这个集合或者是空,或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。 二叉树的概念 5种形态 二叉树的概念 满二叉树 在一棵二叉树中,如果所有分支结点都有左孩子结点和右孩子结点,并且叶结点都集中在二叉树的最下一层,这样的二叉树称为满二叉树。 完全二叉树 若二叉树中最多只有最下面两层的结点的度数可以小于2,并且最下面一层的叶结点 都依次排列在该层最左边的位置上,则这样的二叉树称为完全二叉树 二叉树的性质 性质1 非空二叉树上第i层上至多有2i-1个结点,这里应有i≥1。 性质2 高度为h的二叉树至多有2h-1个结点(h≥1)。 性质3 非空二叉树上结点数满足：n0=n2+1 二叉树的性质 性质4 具有n个(n＞0)结点的完全二叉树的高度为?log2n+1?或?log2n?+1。 性质5 对完全二叉树中编号为i的结点(1≤i≤n,n≥1,n为结点数) 若i=1，则i为根结点，无双亲；否则结点i的双亲为?i/2? 若2in,则结点i存在左孩子编号为2i 若2i+1n,则结点i存在右孩子编号为2i+1 二叉树的存储 顺序存储结构 对该树中每个结点进行编号,其编号从小到大的顺序就是结点存放在连续存储单元的先后次序。 若把二叉树存储到一维数组中，则该编号就是下标值加1 二叉树的存储 链式存储结构——二叉链表 二叉链表存储结构定义： typedef struct node { ElemType data; struct node *lchild,*rchild; } BTNode; 7.3二叉树遍历 先序遍历 中序遍历 后序遍历 二叉树与树的转换 先序遍历 递归算法思想 访问根结点； 先序遍历左子树； 先序遍历右子树。 先序遍历——递归算法 void PreOrder(BTNode *b) /*先序遍历的递归算法*/ { if (b!=NULL) { printf(%c ,b-data); /*访问根结点*/ PreOrder(b-lchild); PreOrder(b-rchild);