PKU 数据结构与算法笔记——二叉树_在完全二叉树中,当i为奇数且不等于1时,结点i的左兄弟是结点(),否则没有左兄弟。

二叉树

二叉树的概念

二叉树由结点有限的集合组成，或者为空集，或者由一个根结点及两棵不相交的左子树和右子树构成

例如

N个结点的树有多少种不同的形态（设点、边没有标签）

易知
$$
\begin{aligned}
f(1)&=1\
f(2)&=f(1)\cdot f(0)+f(0)\cdot f(1)\
f(3)&=f(2)\cdot f(0)+f(1)\cdot f(1)+f(0)\cdot f(2)\
\cdots\
f(n)&=\sum_{i=0}^{n-1}f(n-i-1)f(i)\quad
\end{aligned}

$$

所以$f(n)=\frac{1}{n+1}{C}_{2n}^n$（卡特兰数）

相关概念

• 父母
• 子女（孩子）
• 边
• 兄弟
• 路径
• 祖先
• 子孙
• 树叶
• 内部结点或分支结点
• 度数：结点子树的数目
• 层数（注：一般根结点的层数标记为0层）

N个结点的树有多少边

除了根结点每个结点都有一条边进入，所以是N-1条边

二叉树的类型

满二叉树

满二叉树的结点要么度数为0，要么度数为2，没有度数为1的结点

完全二叉树

完全二叉树只有最下面两层结点度数可以小于2，最下面一层的结点都在该层最左边、最连续的位置上

特点：

• 叶结点只可能在最下面两层出现
• 路径长度和最短(满二叉树不具有此性质)：任意一棵二叉树中根结点到各结点的最长路径一定不短于结点数目相同的完全二叉树中的路径长度

扩充二叉树

当二叉树的结点出现空指针时，就增加一个特殊结点——空树叶，扩充的二叉树时满二叉树

• 度数为1的结点，在它下面增加1个空树叶
• 度数为2的结点，在它下面增加2个空树叶

示例：

性质：

• 外部路径长度E：从扩充二叉树的根到每个外部节点的路径长度之和
• 内部路径长度I：从扩充二叉树的根到每个内部结点的路径长度之和

$E=I+2n$，其中n时内部结点的个数

如上图中E = 3+4+4+3+4+4+3+4+4+3+3=39

​ I = 0+1+2+3+2+3+1+2+3+2=19

二叉树的主要性质

1. 二叉树的第i层最多有2ⁱ个结点
2. 深度为k的二叉树至多有2^k+1-1个结点，其中深度是指二叉树中层数最大的叶结点的层数
3. 任何一棵二叉树，度为0的结点比度为2的结点多1个，即==$n_0=n_2+1$==
4. 满二叉树定理：非空满二叉树树叶等于其分支结点数加1
5. 一个非空二叉树空子树的数目等于其结点数加1
6. 有n个结点的完全二叉树的高度为$\lceil lo{g}_2(n+1)\rceil$(深度为$\lceil lo{g}_2(n+1)\rceil -1$)
7. 对于具有n个结点的完全二叉树，按结点层次由左到右编号，则对任意结点i，有
   • 如果i=0，则结点是二叉树的根结点；若i>0，则其父结点的编号是==$\lfloor (i+1)/2\rfloor$==
   • 当$2i+1\le n-1$时，结点i的左子结点时2i+1，否则没有左子结点，当$2i+2\le n-1$时，结点i的右子结点时2i+2，否则没有右子结点
   • 当i为偶数且0<i<n时，结点i的左兄弟是结点i-1，否则无左兄弟；当i为奇数且i+1<n时，结点i的右兄弟是结点i+1，否则结点i无右兄弟

二叉树的周游

二叉树ADT

BinaryTreeNode

template <class T>
class BinaryTreeNode
{
friend class BinaryTree<T>;//声明二叉树为友元类
private:
    T info;//二叉树结点数据
public:
    BinaryTreeNode();//缺省的构造
    BinaryTreeNode(const T& ele);//给定数据的构造
    BinaryTreeNode(const T& ele, BinaryTreeNode<T> *l, BinaryTreeNode<T> *r);//子树构造
    T value() const;//返回当前结点数据
    BinaryTreeNode<T>* leftchild() const;//返回左子树
    BinaryTreeNode<T>* rightchild() const;//返回右子树
    void setLeftchild(BinaryTreeNode<T>*);//设置左子树
    void setRightchild(BinaryTreeNode<T>*);//设置右子树
    void setValue(const T& val);//设置数据域
    bool isLeaf() const;//判断是否为叶结点
    BinaryTreeNode<T>& operator = (const BinaryTreeNode<T>& Node);//重载赋值操作符
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

BinaryTree

template <class T>
class BinaryTree
{
private:
    BinaryTreeNode<T>* root;//二叉树根结点
public:
    BinaryTree()
    {
		root = NULL;
    }
    ~BinaryTree()
    {
        DeleteBinaryTree(root);
    }
    bool isEmpty() const;//判定是否为空树
    BinaryTreeNode<T>* Root()//返回根结点
    {
        return root;
    }
    BinaryTreeNode<T>* Parent(BinaryTreeNode<T> *current);//返回父
    BinaryTreeNode<T>* LeftSibling(BinaryTreeNode<T> *current);//左兄
    BinaryTreeNode<T>* RightSibling(BinaryTreeNode<T> *current);//右兄
    void CreateTree(const T& info, BinaryTree<T>& leftTree, BinaryTree<T>& rightTree);//构造树
    void PreOrder(BinaryTreeNode<T> *root);//前序遍历
    void InOrder(BinaryTreeNode<T> *root);//中序遍历
    void PostOrder(BinaryTreeNode<T> *root);//后序遍历
    void LevelOrder(BinaryTreeNode<T> *root);//按层次遍历
    void DeleteBinaryTree(BinaryTreeNode<T> *root);//删除二叉树
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

遍历二叉树

按一定层次访问二叉树的过程，每个结点正好被访问一次，实质是把二叉树的结点放入一个线性序列的过程

分为深度优先和广度优先两种

深度优先周游二叉树

• 前序周游
  • 访问根结点–前序周游左子树–前序周游右子树
• 中序周游
  • 中序周游左子树–访问根结点–中序周游右子树
• 后序周游
  • 后序周游左子树–后序周游右子树–访问根结点

template <class T>
void DepthOrder(BinaryTree<T>* root)
{
    if(root != NULL)
    {
        visit(root);	//前序
        DepthOrder(root->leftchild());
        visit(root);	//中序
        DepthOrder(root->rightchild());
        visit(root);	//后序	
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

周游的时间复杂度O(n),空间复杂度为O(n)

二叉树遍历的性质

1. 已知二叉树的先序序列和中序序列，可以唯一确定一棵二叉树
2. 已知二叉树的后序序列和中序序列，可以唯一确定一棵二叉树
3. 已知二叉树的先序序列和后序序列，不能唯一确定一棵二叉树

非递归深度优先遍历

前序

• 看到一个结点，访问它并把非空右子结点压栈，然后深度遍历其左子树（走之前右孩子先入栈）
• 左子树遍历完毕，弹出结点并访问，继续遍历（左子树完毕就出栈）
• 开始时要将一个空指针入栈作为遍历结束的标志（遇到监视哨就结束）

中序

• 遇到一个结点栈并遍历其左子树
• 遍历完左子树出栈并访问这个结点，然后遍历其右子树

后序

• 遇到一个结点，将其入栈并遍历其左子树
• 左子树遍历后不能马上访问栈顶结点，而是要按照右链去遍历其右子树
• 右子树遍历完成后才能访问栈顶的结点
• 需要给栈中的每个元素加一个特征位，标记其是从左边回来还是从右边回来

广度优先遍历二叉树

从根结点开始从上至下逐层遍历，同层结点按照从左到右的顺序遍历

二叉树的存储结构

• 动态存储结构
  • 链式存储
• 静态存储结构
  • 顺序存储（完全二叉树）

动态链式存储结构

各结点随机存储在内存空间，结点之间关系用指针表示，除了本身数据之外每个结点再设置两个指针字段left和right，分别指向左孩子和右孩子，这种结构成为二叉链表表示法

也可以增加一个指向父节点的指针parent，形成三叉链表，这种链表提供了向上访问的能力

静态数组存储

按照一定次序，用一组地址连续的存储单元存储二叉树上的各个结点元素，排成的序列需要能够通过结点在序列中的相对位置确定结点间的逻辑关系

结点i的左子女是结点2i+1，右子女是结点2i+2，父结点是$\lfloor (i-1)/2\rfloor$，左兄是结点i-1，右兄是结点i+1

二叉搜索树

二叉搜索树具有以下性质

• 对于任意一个结点，设其值为k，该结点的左子树的任意一个结点都小于k，该结点的右子树的任意一个结点都大于k，它的左右子树也是二叉搜索树
• 树的结点的值唯一
• 按照中序周游将各结点打印出来，将得到由小到大的排列

搜索

从根结点开始检索，如果结点值为k，检索结束，如果k小于结点的值，只需要检索左子树，如果K大于结点的值，只需要检索右子树，一直持续到k被找到或者遇上了一个树叶

插入

基本步骤与搜索类似，先要进行一次失败的查找，再执行插入

建立

对于一个给定的关键码集合从一个空的二叉树一个个插进去

删除

对于待删除结点pointer，删除过程如下

• 若结点pointer没有左子树：则用pointer右子树的根代替被删除的结点pointer
• 若结点pointer有左子树：则在左子树里找到中序周游的最后一个结点temppointer（左子树里的最大值，也就是小于删除结点的值的最大值），把temppointer的右指针设置成pointer右子树的根，然后用结点pointer左子树的根代替被删除的结点pointer

这样会导致二叉树高度失衡，使得效率降低

改进的思想如下

• 若结点pointer没有左子树：则用pointer右子树的根代替被删除的结点pointer
• 若结点pointer有左子树：则在左子树里找到按照中序周游的最后一个结点replpointer（即左子树里的最大结点）并将其从二叉搜索树里删除
• 由于replpointer没有右子树，删除该结点只需用replpointer的左子树代替replpointer，然后用replpointer结点代替待删除的结点pointer

堆与优先队列

堆

• 分为最小值堆和最大值堆，最小值堆的序列有以下特性$k_i\le K_{2i+1},k_i\le K_{2i+2}$

• 最大值堆的定义类似

• 堆中的数据局部有序，结点与其子女之间存在大小比较关系，兄弟之间没有限定大小关系

• 堆是一个可以用数组表示的完全二叉树

建堆过程

• 将关键码放到数组形成完全二叉树
• 从完全二叉树的倒数第二层的$i=(n/2-1)$位置开始从左至右，从下至上依次调整
• 直到树根，整棵树就形成一个堆

插入新元素

先把新结点插入堆的最后位置，然后向上调整，使之成为堆

移出最小值

移出最小值后，将堆中的最后一个位置上的元素移到根结点，再利用向下调整的办法

效率

建堆的时间复杂度是O(n)，插入、删除的时间复杂度都是O(logn)

优先队列

优先队列的主要特点是从一个集合中快速地查找并移出具有最大值或最小值地元素

堆是优先队列地一种自然的实现方法

Huffman树

一个具有n个外部结点的扩充二叉树，每个外部结点k_i有一个w_i与之对应，成为该外部结点的权，二叉树叶结点带权外部路径长度总和称为带权外部路径长度，具有最小带权外部路径长度的二叉树称为Huffman树

Huffman编码

• 用d₀，d₁,……,d_n-1作为外部结点构造具有最小带权外部路径长度的扩充二叉树
• 把从每个结点引向其左子结点的边标上号码0，引向其右子节点的边标上号码1
• 把从根结点到每个叶结点路径上的编号连接起来，得到的二进制前缀码就称作Huffman编码

性质

• 不等长编码
• 编码的长度取决于对应字符的相对使用频率或权重
• 任何一个字符的编码都不是另一个字符编码的前缀