数据结构6-树和二叉树.ppt

《数据结构6-树和二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章树和二叉树树的定义和基本术语树是n(n≥0)个结点（数据元素）的有限集。若n=0，集合为空树；若n>0，则集合对应一棵非空树，它具有如下特点：(1)树中有且仅有一个特定的称为根的结点；(2)当n>1时，根以外的其余结点可分为m个(m>0)互不相交的有限集。这些有限集本身又是一棵树，是根的子树。（递归定义）抽象数据类型树的定义：ADTTree树结构的其它表示形式：嵌套集合形式、广义表形式、凹入形式树的结点包含一个数据元素和若干指向其子树的分支结点的度：结点拥有的子树的数目树的度：树中结点的度的最大值叶子（终端结点）：度为0的结点非终端结点

2、（分支结点）：度不为0的结点结点间的关系：双亲、孩子、兄弟、祖先、子孙、堂兄弟等树的深度（高度）：树中结点的最大层次数（注：根为第一层，其孩子为第二层……）有序树和无序树：子树是否有次序森林：m(m>0)棵互不相交的树的集合树的示例ABCDGFEHIJ二叉树二叉树是另一种树形结构。它的特点是每个结点至多只有二棵子树（树中不存在度大于2的结点），并且子树有左右之分（有序树）。抽象数据类型二叉树的定义：ADTBinaryTree二叉树的五种基本形态：二叉树的性质性质1：二叉树的第i层上至多有2i-1个结点性质2：深度为k的二叉树至多有2k-1个结

3、点性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1性质4：具有n个结点的完全二叉树的深度为［log2n］+1性质5：如果对一棵有n个结点的完全二叉树按层次从左到右依次编号（根结点编号为1），则对任一编号为i的结点（1≤i≤n），其双亲编号为［i/2］，其左孩子编号为2i，右孩子编号为2i+1（如果存在的话）完全二叉树的定义由性质2，深度为k的二叉树至多有2k-1个结点，而结点数目达到最多的二叉树为满二叉树对深度为k、结点数目为N（N=2k-1）的满二叉树按层次从左到右编号，则编号为1，2，…，N。而深

4、度为k、结点数目为n(n≤N)的二叉树，当且仅当其每一结点的编号都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树深度为k的完全二叉树中，1~k-1层的结点数应达到最多，其余结点在第k层依次从左往右排二叉树的存储结构根据二叉树性质5，对完全二叉树可按结点编号将其存于一组地址连续的存储单元中，结点之间的关系也可通过存储位置反映，即采用顺序存储结构。其类型定义为：#defineMAX-TREE-SIZE100typedefTelemtypeSqBiTree[MAX-TREE-SIZE];//0号单元存储根结点，编号为i的结点存

5、于i-1号单元对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对应，虚设结点后顺序存储。但有时虚设结点数反而多于二叉树的结点数。所以，一般二叉树不宜采用顺序存储结构二叉树的链式存储结构二叉树的二叉链表存储表示结点结构：类型定义：typedefstructbitnode{TElemTypedata;structbitnode*lchild,*rchild;}BiTNode,*BiTree;二叉树的三叉链表存储表示结点结构：二叉树的遍历遍历二叉树：按某种顺序对二叉树中每个结点访问，使每个结点均被访问到且只被访问一次遍历方法（限定遍历时先左后

6、右）：按根结点被访问的先后，分为先序、中序和后序三种遍历按层次遍历二叉树先序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。中序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。后序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。例：二叉树的遍历先序遍历序列：ABDGCEFIJ中序序列：DGBAECIFJ后序序列：GDBEIJFCAABCDGFEIJ递归的

7、遍历算法假设二叉树采用二叉链表表示，对树中结点进行打印输出的访问，则根据遍历操作的定义，可得如下先序遍历的递归算法：voidPreOrderTranverse(BiTreet){if(t){printf(t->data);PreOrderTranverse(t->lchild);PreOrderTranverse(t->rchild);}}中序遍历的递归算法如下：voidInOrderTranverse(BiTreet){if(t){InOrderTranverse(t->lchild);printf(t->data);InOrderTran

8、verse(t->rchild);}}后序遍历的递归算法如下：voidPostOrderTranverse(BiTreet){if(t){PostOrderTran