数据结构与算法 －二叉树

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

二叉树的基本概念

1. 定义

二叉树是递归的一种表现形式，它是n(n>=0)个结点的有限集合。通常是由一个根及两棵互不相交的左子树和右子树组成，其中左子树和右子树也均为二叉树。此外，二叉树可以是空集合， 根也可以有空的左子树或空的右子树。

2. 特点

(1). 二叉树可以是空的，称空二叉树。

(2). 每个结点最多只能有两个孩子。

(3). 子树有左、右之分且次序不能颠倒。

3. 二叉树与树的比较

二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树，这是二叉树与树的最 主要的差别。下图列出二叉树的5种基本形态，图(c) 和(d)是不同的两棵二叉树。

4. 二叉树的基本运算包括

(1). 初始化Initiate(BT)：建立一棵空二叉树，BT=∅。

(2). 求双亲Parent(BT,X)：求出二叉树BT上结点X的双亲结点， 若X是BT的根或X根本不是BT上的结点，运算结果为 NULL。

(3). 求左孩子Lchild(BT,X)和求右孩子Rchild(BT,X)：分别求出二叉树BT上结点X的左、右孩子；若X为BT的叶子或X 不在BT上，运算结果为NULL。

(4). 建二叉树Create(BT)：建立一棵二叉树BT。

(5). 先序遍历PreOrder(BT)：按先序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。

(6). 中序遍历InOrder(BT)：按中序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次， 若BT为空，则运算为空操作。

(7). 后序遍历PostOrder(BT)：按后序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次， 若BT为空，则运算为空操作。

(8). 层次遍历LevelOrder(BT)：按层从上往下，同一层中结点按从左往右的顺序，对二叉树进行遍历，每个结点被访问一次且仅被访问一次，若 BT 为空，则运算为空操作。

二叉树的性质

1. 在二叉树的第i(i>=1)层上至多有2^(i - 1)个 结点。

2. 深度为k(k>=1)的二叉树至多有2^k - 1 个结点。

3. 对任何一棵二叉树，如果度为0结点数为n0，度为2的结点数为n2，则n0＝n2＋1。即叶结点数n0 = 度为2的结点数n2+1。

(1). 完全二叉树：深度为k的二叉树中，k-1层结点数是满的2^(k-2)，k层结点是左连续的。

(2). 满二叉树：深度为k(k>=1)，且有2^k-1个结点的二叉树。

满二叉树中结点顺序编号：即从第一层结点开始自上而下，从左到右进行连续编号，满二叉树是完全二叉树的特例。

4. 具有n个结点的完全二叉树的深度为 ⌊log2n⌋ + 1，此处2为底数。

符号⌊x⌋表示对x进行下取整。

假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2^(k-1) -1< n <= 2^k-1，或 2^(k-1) < n <= 2^k。

取对数得到：k-1< log2n < k，因为k是整数，所以有：k＝⌊log2n⌋+1，此处2为底数。

5. 对有n个结点的完全二叉树的结点按层(从左往右)编号，则对任一结点i (1≤i≤n)有以下特点：

(1). 如果i＝1，则结点i无双亲，是二叉树的根； 如果i>1，则i的双亲Parent(A)是结点⌊i/2⌋。

(2). 如果2*i <= n，则其左孩子是结点2*i，否则结点i无左孩子且为叶子结点。

(3). 如果2*i＋1 <= n，则其右孩子是结点2*i＋1， 否则结点i无右孩子。