数据结构-树与二叉树

1、树与二叉树梁 音地球信息科学与技术系地球物理与空间信息学院基本概念回顾从此处开始我们将要接触到非线性结构了。回忆一下线性数据结构的特点？有限、有序只有唯一的头和尾除了头和尾以外，每一个数据元素都只有唯一的直接前驱和唯一的直接后继基本概念回顾那么非线性的数据结构将打破这三大特点中的一种或多种。比如我们即将讲到的树，它有唯一的头，我们称为根节点(Root)，但是它有很多尾，我们称为叶子节点(Leaf)；除了根节点和叶子节点外，中间的节点有很多直接后继，但是都只有唯一的直接前驱。树的基本概念树的基本概念A节点就是根节点，它没有直接前驱；J、K、F、C、L、H和I节点都是叶子节点，它们都没有直接后继；

2、E、B、G和D节点都是中间节点；E的直接前驱是B，直接后继是J和K；B的直接前驱是A，直接后继是E和F；D的直接前驱也是A，直接后继是G、H和I。树的基本概念树的定义：(1)有且仅有一个根节点；(2)除了根节点之外，其余的节点可以分成若干个互不相交有限集合，其中的每一个集合本身又是一棵树。可见，树的定义本身就是递归的。所以有关树结构的算法一般多以递归形式给出。树的基本概念A为根节点；B、E、F、J和K组成一棵子树，B为该子树的根节点；C独立组成一棵子树，它既是根节点，又是叶子节点；D、G、H、I和L节点组成另一棵子树，D为该子树的根节点。树的基本概念B、C和D节点有相同的直接前驱A，A称为他们

3、的父节点(Parent)，B、C和D称为A的孩子(Child)；有同一个父节点的孩子节点互称兄弟(Sibling)，B、C和D节点就互为兄弟。以某一节点为根的子树中的任一节点都称为该节点的子孙(Offspring)。E、F、J和K节点都是B的子孙。树的基本概念树中节点得最大层次称为树的深度(Depth)或高度。节点的度：节点所拥有的子树的数目。树的度：树内各节点度的最大值。森林(Forest)是若干棵互不相交的树的集合树中节点的各子树从左自右是右次序的，则该树为有序树，否则为无序树。树的基本概念树的深度为4A节点的度为3B节点的度为2去掉A节点后，集合B, E, F, J, H, C, D,

4、G, H, I, L组成森林。树的基本概念就逻辑结构而言，任何一棵树都是一个二元组Tree = (root, F)，其中，root是树的根节点，F是m棵树所构成的森林。F = (T1, T2, Tm)，其中Ti = (ri, Fi)称作根root的第i棵子树。并且有Ti与Tj的交集为空集，其中1ij=m二叉树二叉树(Binary Tree)：本身是树型结构。每个节点最多只有两棵子树。即，节点的度不能大于2。二叉树的子树有左右之分，其次序不能颠倒。所以二叉树是一个有序树。二叉树的性质性质1：在二叉树的第i层上最多有2i1个节点。证明：用数学归纳法。i = 1时，节点数为1，就是根节点，假设i =

5、 k时，命题成立，即第k层上最多有2k1个节点，那么对于k+1层而言，由于是二叉数，其节点至多就是2第k层上的节点数。二叉树的性质性质2：深度为k的二叉数，最多有2k-1个节点根据性质1，对于第k而言，其最大的节点数是2i-1。那么总的节点数不能超过：二叉树的性质性质3：对任何一棵二叉数T，如果其终端节点数为n0，度为2的节点数为n2，则n0 = n2+1。假设度为1的节点数为n1，则总的节点数为n0+ n1+ n2。除了根节点以外，每一个节点都只有唯一的直接前驱。二叉树的性质那么总的节点数还可以等于：n1+2n2+1实际的分支数就和中间节点与叶子节点总和相等。与式子n0+ n1+ n2作比较

6、，可以得到性质3： n0 = n2+1两类特殊的二叉数满二叉树：必须首先是二叉树所有的节点的度都是2如果深度为k，则节点树就是2k-1两类特殊的二叉数这里为了方便的引入另外一种特殊的二叉树，我们给满二叉树的每一个节点编号。编号的规则：从上向下，从左向右。如果我们对二叉树按上述规则进行编号，与其同深度的满二叉树对应节点编号全一样的树称为完全二叉树。两类特殊的二叉数 树T1 树T2两类特殊的二叉数 树T3 树T4两类特殊的二叉数树T1和T3都是完全二叉树，树T2和T4都不是完全二叉树。完全二叉树的特点：叶子节点只可能在最大的两层上出现；对任一节点，若其右分支下的子孙的最大层次为L，则其左分支下的子

7、孙的最大层次必为L或L1。二叉树的性质性质4：具有n个节点的完全二叉树的深度为log2n+1。若深度为k，根据完全二叉树的定义以及性质2，2k-1-1n=2k-1或者2k-1=n 2k，这样，就有k-1= log2nk成立。于是，k = log2n+1。二叉树的存储结构顺序存储结构用一组地址连续的存储单元依次自上而下，从左至右存储二叉树上的节点元素。链式存储结构依靠指针来连接根节点和其左、右子树。二叉树的存储结构顺序存储：123456789101112131415二叉树的存储结构顺序存储：12345000067二叉树的存储结构顺序存储：优点：简单、方便缺点：深度为k且只有k个节点的单枝树，仍然需要使用2 k-1的一维数组存放。102000300000004二叉树的存储结构链式存储结构表示二叉树的链表的结点中包含三个域：数据域左指针域右指针域LChildDataRChild二叉树的存储结构链式存储结构(C语言描述)typedef struct BiTNode ElemType data; struct BiTNode *LChild, *RChild; /左右孩子指针BiTree二叉树