树

树的基本概念

二叉树

参看：Java数据结构:树（Tree） (opens new window)

为何要重点研究每结点最多只有两个“叉”的树?

• 二叉树的结构最简单，规律性最强;
• 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。

普通树(多叉树)若不转化为二叉树，则运算很难实现

二叉树在树结构的应用中起着非常重要的作用，因为对二叉的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。

定义

二叉树是n (n≥O)个结点的有限集，它或者是空集(n = 0)，或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。

特点 1、每个结点最多有俩孩子(二叉树中不存在度大于2的结点)。

2、子树有左右之分，其次序不能颠倒。

3、二叉树可以是空集合，根可以有空的左子树或空的右子树。

二叉树的性质

性质1

性质1:在二叉树的第i层上至多有**2^i-1^**个结点(i≥1)。

证明:用数学归纳法。

归纳基础:当i=1时，整个二叉树只有一个根结点，此时2^i-1^=2^0^=1，结论成立。

归纳假设:假设i=k时结论成立，即第k层上结点总数最多为2^k-1^个。

欲证明当i=k+1时，结论成立。

因为二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的2倍，即2×2=2^(k+1)-1^，故结论成立。

延伸：第i层上至少有1个节点。

性质2

性质2:深度为k的二叉树至多有2^k^-1个结点(k≥1)。

证明:因为深度为k的二叉树，其结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为k的二叉树的结点总数至多为

故结论成立。

性质3

性质4

性质5

性质5:对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有：

二叉树的存储结构

顺序存储

对于完全二叉树来说，可以将其数据元素逐层存放到一组连续的存储单元中，如下图所示。用一维数组作存储结构，将二叉树中编号为i的结点存放在数组的第i个分量中。根据二叉树的性质5，可得结点i的左孩子的位置为LChild(i)=2×i;右孩子的位置为RChild(i)=2×i＋1。

对于完全二叉树来说，这样既不浪费空间，又可以根据公式直接计算每个节点的左右孩子的位置。

但是对于一般二叉树而言，会造成浪费。

极端情况下，对于一个深度为k的二叉树，在最坏情况下需要占用2^k^ -1个存储单元，而实际上二叉树只有k个节点，空间浪费太大。

分析：

优点:通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。

缺点:如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低[示意图]

链式存储

对于任意的二叉树来说，每个结点只有两个孩子，一个双亲结点。可以设计每个结点至少包括三个域:数据域、左孩子域和右孩子域，如下图所示。

其中，LChild域指向该结点的左孩子，Data域记录该结点的信息，RChild域指向该结点的右孩子。此结点结构形成的二叉树称为二叉链表，如下图所示

但有时，为了找到父节点，可以增加一个Parent域：

二叉链表性质：

分析：

优点:在一定程度上对数组存储方式有优化(比如:插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好)。

缺点:在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)【示意图】