第6章树和二叉树树的定义和基本术语•树是n(n≥0)个结点（数据元素）的有限集。若n=0，集合为空树；若n>0，则集合对应一棵非空树，它具有如下特点：(1)树中有且仅有一个特定的称为根的结点；(2)当n>1时，根以外的其余结点可分为m个(m>0)互不相交的有限集。这些有限集本身又是一棵树，是根的子树。（递归定义）•抽象数据类型树的定义：ADTTree•树结构的其它表示形式：嵌套集合形式、广义表形式、凹入形式•树的结点包含一个数据元素和若干指向其子树的分支•结点的度：结点拥有的子树的数目•树的度：树中结点的度的最大值•叶子（终端结点）：度为0的结点•非终端结点（分支结点）：度不为0的结点•结点间的关系：双亲、孩子、兄弟、祖先、子孙、堂兄弟等•树的深度（高度）：树中结点的最大层次数（注：根为第一层，其孩子为第二层……）•有序树和无序树：子树是否有次序•森林：m(m>0)棵互不相交的树的集合树的示例ABCDGFEHIJ二叉树•二叉树是另一种树形结构。它的特点是每个结点至多只有二棵子树（树中不存在度大于2的结点），并且子树有左右之分（有序树）。•抽象数据类型二叉树的定义：ADTBinaryTree•二叉树的五种基本形态：二叉树的性质•性质1：二叉树的第i层上至多有2i-1个结点•性质2：深度为k的二叉树至多有2k-1个结点•性质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。而深度为k、结点数目为n(n≤N)的二叉树，当且仅当其每一结点的编号都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树•深度为k的完全二叉树中，1~k-1层的结点数应达到最多，其余结点在第k层依次从左往右排二叉树的存储结构•根据二叉树性质5，对完全二叉树可按结点编号将其存于一组地址连续的存储单元中，结点之间的关系也可通过存储位置反映，即采用顺序存储结构。其类型定义为：#defineMAX-TREE-SIZE100typedefTelemtypeSqBiTree[MAX-TREE-SIZE];//0号单元存储根结点，编号为i的结点存于i-1号单元•对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对应，虚设结点后顺序存储。但有时虚设结点数反而多于二叉树的结点数。所以，一般二叉树不宜采用顺序存储结构二叉树的链式存储结构•二叉树的二叉链表存储表示结点结构：类型定义：typedefstructbitnode{TElemTypedata;structbitnode*lchild,*rchild;}BiTNode,*BiTree;•二叉树的三叉链表存储表示结点结构：lchilddatarchildlchilddataparentrchild二叉树的遍历•遍历二叉树：按某种顺序对二叉树中每个结点访问，使每个结点均被访问到且只被访问一次•遍历方法（限定遍历时先左后右）：1.按根结点被访问的先后，分为先序、中序和后序三种遍历2.按层次遍历二叉树•先序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。•中序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。•后序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。例：二叉树的遍历先序遍历序列：ABDGCEFIJ中序序列：DGBAECIFJ后序序列：GDBEIJFCAABCDGFEIJ递归的遍历算法假设二叉树采用二叉链表表示，对树中结点进行打印输出的访问，则根据遍历操作的定义，可得如下先序遍历的递归算法：voidPreOrderTranverse(BiTreet){if(t){printf(t->data);PreOrderTranverse(t->lchild);PreOrderTranverse(t->rchild);}}中序遍历的递归算法如下：voidInOrderTranverse(BiTreet){i...
