数据结构第六章 树和二叉树

《数据结构第六章 树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6哈夫曼树及其应用作业实验6.1树的定义和基本术语结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM(从根到结点的)路径：孩子结点、双亲结点兄弟结点、堂兄弟祖先结点、子孙结点由从根到该结点所经分支和结点构成ABCDEFGHIJMKL结点的层次:树的深度：假设根结点的层次为1，第l层的结点的子树根结点的层次为l

2、+1树中叶子结点所在的最大层次ABCDEFGHIJMKL森林：是m（m≥0）棵互不相交的树的集合BEFKLACGDHIJMABCDEFGHIJMKLA(B(E,F(K,L)),C(G),D(H,I,J(M)))T1T3T2树根例如:(１)有确定的根；(２)树根和子树根之间为有向关系。有向树：有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。BEFKL对比树型结构和线性结构的结构特点线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结

3、点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~而现实中的许多事物的关系并非这样简单，如人类社会的族谱、各种社会组织机构以及城市交通、通讯等，这些事物中的联系都是非线性的，采用非线性结构进行描绘会更明确和便利。在前面几章里讨论的数据结构都属于线性结构线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述所谓非线性结构是指，在该结构中至少存在

4、一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型结构和图型就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系，如前面提到的族谱、城市交通等。本章对树型结构中最简单、应用十分广泛的二叉树结构进行讨论。二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树6.2二叉树6.2.1二叉树的定义二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树

5、二叉树的主要基本操作：查找插入删除性质1：在二叉树的第i层上至多有2i-1个结点。(i≥1)用归纳法证明：归纳基：归纳假设：归纳证明：i=1层时，只有一个根结点：2i-1=20=1；假设对所有的j，1≤ji，命题成立；二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-22=2i-1。6.2.2二叉树的性质性质2：深度为k的二叉树上至多含2k-1个结点（k≥1）。证明：基于上一条性质，深度为k的二叉树上的结点数至多为20+21++2k-1=2k-1。性质3：对任何一棵二叉树，

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

7、k则根据第二条性质得2k-1≤n<2k即k-1≤log2nn，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；(3)若2i+1>n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。2.二叉树的链式存储表示1.

8、二叉树的顺序存储表示6.2.3二叉树的存储结构#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTreebt;1.二叉树的顺序存储表示例如:ABCDEFABDCEF01234567891011121314013262、二叉树的链式存储表示（1）二叉链表（2）三叉链表ADEBCFrootlchilddatarchild结点结构:（1）二叉链表typedefs