第6章二叉树和树1

《第6章二叉树和树1》由会员分享，可在线阅读，更多相关《第6章二叉树和树1（26页珍藏版）》请在装配图网上搜索。

1、12v 树结构的特点及基本术语树结构的特点及基本术语v 6.1 二叉树二叉树34线性结构树型结构第一个数据元素 (无前驱)根结点 (无前驱)最后一个数据元素 (无后继)多个叶子结点 (无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点5结点结点:数据元素+若干指向子树的分支结点的度结点的度:分支的个数树的度树的度:树中所有结点的度的最大值叶子结点叶子结点:度为零的结点分支结点分支结点:度大于零的结点DHIJM基本术语基本术语6(从根到结点的)路径路径：孩子孩子结点、双亲双亲结点兄弟兄弟结点、堂兄弟祖先祖先

2、结点、子孙子孙结点 由从根根到该结点所经分支和结点构成ABCDEFGHIJMKL结点的层次结点的层次:假设根结点的层次为1 1,第l 层的结点的子树根结点的层次为l+1 1树的深度：树的深度：树中叶子结点所在的最大层次7一、二叉树的定义和基本术语一、二叉树的定义和基本术语二、二叉树的几个基本性质二、二叉树的几个基本性质三、二叉树的存储结构三、二叉树的存储结构8一、二叉树的定义和基本术语一、二叉树的定义和基本术语9 二叉树二叉树的定义的定义 二叉树是n（n0）个元素的有限集，它或为空树空树，或是由一个根结点根结点加上两棵两棵分别称为左左子树子树和右子树的、互不交的互不交的二叉树二叉树组成。根结点

3、左子树右子树ABCDEFGHKLB10二叉树二叉树可以表现出可以表现出五种基本形态五种基本形态：空树空树N只含根结点只含根结点右子树右子树为空树为空树NL左子树左子树为空树为空树NR左右子树均不为空树左右子树均不为空树NLR11 二叉树二叉树的基本操作：的基本操作：v 查查 找找 类类 的的 操操 作作v 插插 入入 类类 的的 操操 作作v 删删 除除 类类 的的 操操 作作12 Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpt

4、y(T);BiTreeDepth(T);PreOrderTraverse(T);InOrderTraverse(T);PostOrderTraverse(T);LevelOrderTraverse(T);查找类的操作：查找类的操作：13 InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);插入类的操作：插入类的操作：14ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);删除类的操作：删除类的操作：15二、二叉树的几个基本性

5、质二、二叉树的几个基本性质16v 性质性质 1：在二叉树的第在二叉树的第 i 层上至多有层上至多有2i-1 个结点个结点(i1)。用归纳法证明用归纳法证明：归纳基归纳基：归纳假设：归纳假设：归纳证明：归纳证明：i=1 层时，只有一个根结点：2i-1=20=1；假设对所有的 j，1 j i，命题成立；二叉树上每个结点至多有两棵子树，则第 i 层的结点数=2i-2 2=2i-1。17v 性质性质 2：深度为深度为 k 的二叉树上至多含的二叉树上至多含 2k-1 个结点（个结点（k1）。）。证明：证明：基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+2k-1=2k-1。18v 性质

6、性质 3：对任何一棵二叉树，若它含有对任何一棵二叉树，若它含有n0 个叶子结点、个叶子结点、n2 个度为个度为 2 的结点，的结点，则必存在关系式：则必存在关系式：n0=n2+1。证明：证明：设设 二叉树上结点总数 n=n0+n1+n2又又 二叉树上分支总数 b=n1+2n2 而 b=n-1=n0+n1+n2-1由此，由此，n0=n2+1。19两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号为编号为 1 至至 n 的结点的结点一一对应。abcdefghij123456789101112

7、13141520v 性质性质 4：具有具有 n 个结点的完全二叉树的个结点的完全二叉树的深度为为 log2n +1。证明：证明：设设完全二叉树的深度为 k 则根据第二条性质得 n 2k-1，得n 2k前k-1层是满二叉树，因而2k-1-1n，得2k-1 n，从而得到2k-1 n2k 即 k-1 log2 n n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子右孩子结点。123456789101112 13 14 1523三、二叉树的存储结构三、二叉树的存储结构u 二叉树顺序存储表示二叉树顺序存储表示u 二叉树链式存储表示二叉树链式存储表示24const MAXSIZE=100;/暂定二叉树的最大结点数typedef struct TElemType*data;/存储空间基址 int nodenum;/树中结点数SqBiTree;u 二叉树顺序存储表示二叉树顺序存储表示25例如例如:A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 13ABCDEF140132626第第7次书面作业次书面作业6.16.26.36.4练习和理解练习和理解p179 1.p180 5.6.7.