biscuitの博客

binary tree的定义#

二叉树是每个节点最多有两个子节点的树结构，分别称为左子节点和右子节点。二叉树的节点度数最大为2，并且是有序树，用左右区分序。

斜树：只有左子树的二叉树称为左斜树，只有右子树的二叉树称为右斜树。

满二叉树：高度为 $K$ 且有 $2^K-1$ 个节点的二叉树称为满二叉树。每个分支节点都有两棵子树，且所有叶子节点都在最后一层。

完全二叉树：高度为 $K$ 的二叉树，除第 $K$ 层外，其余各层节点数均达到最大值，第 $K$ 层所有节点都连续集中在最左边。

TIP

深度为k的完全二叉树的前k-1层是满二叉树，第k层的节点从左到右依次编号为 $1,2,...,m(m<=2^{(k-1)})$。

二叉树的性质#

1. 深度节点数：深度为 $K$ 的二叉树最多有 $2^K-1$ 个节点，最少有 $K$ 个节点；

   TIP

   每一层节点数是前一层的两倍，所以第i层最多有 $2^{i-1}$ 个节点，等比数列求和公式

   $$\sum_{i=0}^{n-1}2^i=2^n-1$$

   就得到了满二叉树节点数的公式

2. 每一层节点数：第 $i$ 层最多有 $2^{i-1}$ 个节点，最少有1个节点。

3. 叶子节点数：对于非空二叉树，叶子节点数 $n_0$ 与度为2的节点数 $n_2$ 满足关系 $n_0=n_2+1$。

   对于 $N$ 节点的满二叉树，叶子节点数为 $(N+1)/2$。

   证明

   设二叉树中度为0的节点数为 $n_0$，度为1的节点数为 $n_1$，度为2的节点数为 $n_2$，总节点数为 $N$，则有：

   $$N=n_0+n_1+n_2 \tag{1}$$

   每个节点有一条边指向它（根节点除外），所以边数 $E$ 满足：

   $$E=N-1 \tag{2}$$

   另一方面，边数也可以通过节点的度数来计算：

   $$E=n_1+2n_2 \tag{3}$$

   将 (2) 和 (3) 结合，得到：

   $$N-1=n_1+2n_2 \tag{4}$$

   将 (1) 代入 (4)：

   $$(n_0+n_1+n_2)-1=n_1+2n_2$$

   化简得到:

   $$n_0=n_2+1$$

4. 节点数和高度：具有n个节点的完全二叉树的高度为 $\lceil log_2(n+1)\rceil$ 或 $\lfloor log_2n \rfloor +1$。

   证明

   设完全二叉树的高度为 $h$，则前 $h-1$ 层是满二叉树，有 $2^{h-1}-1$ 个节点，第 $h$ 层有 $m$ 个节点，$1\leq m\leq 2^{h-1}$，所以总节点数 $n$ 满足

   $$2^{h-1}\leq n\leq 2^h-1$$

   取对数得到

   $$h-1\leq log_2n<h$$

   即

   $$h=\lceil log_2(n+1)\rceil=\lfloor log_2n \rfloor +1$$

一般二叉树的空间浪费#

• 规律：随节点数量指数增长

• 最坏：右单枝树，所有节点全是right child

$n$ 节点的二叉树需要 $2^n-1$ 个存储单元（$n$ 节点的右单支树有n层）

$31$ 个节点的二叉树就要 $21$亿 个存储单元

二叉链表的建立#

1. 先序遍历建立二叉树
   按照先序遍历的顺序输入节点值，遇到空节点输入特殊标记（如#），递归建立二叉树。

   1
   #include <iostream>
   2
   #include <sstream>
   3
   using namespace std;
   4
   
   5
   TreeNode* createTree() {
   6
       string val;
   7
       if (!(cin >> val)) return nullptr;
   8
       if (val == "#") return nullptr;
   9
       TreeNode* node = new TreeNode(stoi(val));
   10
       node->left = createTree();
   11
       node->right = createTree();
   12
       return node;
   13
   }
   

2. 索引式构建二叉链表

   先创建所有节点对象，然后根据输入的左右孩子编号建立指针连接。

   1
       #include <iostream>
   2
   #include <vector>
   3
   #include <string>
   4
   using namespace std;
   5
   struct TreeNode {
   6
       char data;
   7
       TreeNode* left;
   8
       TreeNode* right;
   9
       TreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
   10
   };
   11
   // 每个节点的输入信息
   12
   struct NodeInfo {
   13
       char data;
   14
       int leftIndex;
   15
       int rightIndex;
   16
   };
   17
   TreeNode* buildTree(const vector<NodeInfo>& input) {
   18
       int n = input.size();
   19
       vector<TreeNode*> nodes(n);
   20
       // 第一步：创建所有节点对象
   21
       for (int i = 0; i < n; ++i) {
   22
           nodes[i] = new TreeNode(input[i].data);
   23
       }
   24
       // 第二步：建立左右孩子指针连接
   25
       for (int i = 0; i < n; ++i) {
   26
           int l = input[i].leftIndex;
   27
           int r = input[i].rightIndex;
   28
           if (l != 0) nodes[i]->left = nodes[l];
   29
           if (r != 0) nodes[i]->right = nodes[r];
   30
       }
   31
   
   32
       return nodes[0]; // 返回根节点
   33
   }
   34
   // 前序遍历用于验证构建结果
   35
   void preorder(TreeNode* root) {
   36
       if (!root) return;
   37
       cout << root->data << " ";
   38
       preorder(root->left);
   39
       preorder(root->right);
   40
   }
   41
   int main() {
   42
       // 示例输入：构建如下结构
   43
       //        A
   44
       //       / \
   45
       //      B   C
   46
       //     / \ / \
   47
       //    D  E F  G
   48
       vector<NodeInfo> input = {
   49
           {'A', 1, 2},
   50
           {'B', 3, 4},
   51
           {'C', 5, 6},
   52
           {'D', 0, 0},
   53
           {'E', 0, 0},
   54
           {'F', 0, 0},
   55
           {'G', 0, 0}
   56
       };
   57
       TreeNode* root = buildTree(input);
   58
       cout << "前序遍历结果: ";
   59
       preorder(root);
   60
       cout << endl;
   61
       return 0;
   62
   }