#CS225

Tree

Concept & Teminology

二叉树及基本性质



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18



template <class T>
class BinaryTree {
private:
    struct TreeNode {
        T data;
        TreeNode *left;
        TreeNode *right;
    };

    TreeNode *root;

public:
    BinaryTree() : root(nullptr) {} // 构造函数
    ~BinaryTree() { clear(); }      // 析构函数，释放内存

    // ... (其他方法，例如 insert, remove, traverse 等) ...
};

1. Height

定义：

递归定义：
f7058bf799e924202be9d9d457e2b86.png

2. Full Tree
每个节点要么没有子节点，要么有两个子节点

3. Perfect Tree
所有内部节点都有两个子节点，并且所有叶子节点都在同一层
高度为 h 的完美二叉树的节点数量: $P_{h} = 2^{h+1}-1$

递归定义：

4. Complete Tree
除了最后一层，其他每一层都是满的，并且最后一层的节点都尽可能地靠左排列。

[!warning] 注意

5. NULL 的数量

NULL 的数量为当前节点数量 +1（可以利用数学归纳法证明）

Abstract Data Type(ABT)

Insert



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



template <class T>
void BinaryTree<T>::insert(T value) {
    TreeNode *newNode = new TreeNode{value, nullptr, nullptr};

    if (!root) {
        root = newNode;
        return;
    }

    TreeNode *current = root;
    while (current) {
        if (value < current->data) {
            if (!current->left) {
                current->left = newNode;
                return;
            }
            current = current->left;
        } else {
            if (!current->right) {
                current->right = newNode;
                return;
            }
            current = current->right;
        }
    }
}

Remove



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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54



template <typename T>
void Tree<T>::remove(TreeNode<T>* node) {
    if (node == nullptr) return;
    
    // 获取父节点引用
    TreeNode<T>* parent = node->parent;
    
    // 处理节点是根节点的情况
    if (parent == nullptr) {
        // 根节点删除操作
        delete_subtree(root);
        root = nullptr;
        return;
    }
    
    // 处理一般情况
    // 1. 更新父节点的子节点链表
    if (parent->firstChild == node) {
        // 如果是第一个子节点
        parent->firstChild = node->nextSibling;
    } else {
        // 如果不是第一个子节点，需要遍历找到前一个兄弟节点
        TreeNode<T>* sibling = parent->firstChild;
        while (sibling != nullptr && sibling->nextSibling != node) {
            sibling = sibling->nextSibling;
        }
        
        if (sibling != nullptr) {
            sibling->nextSibling = node->nextSibling;
        }
    }
    
    // 2. 递归删除子树
    delete_subtree(node);
}
// 删除子树的辅助函数
template <typename T>
void Tree<T>::delete_subtree(TreeNode<T>* node) {
    if (node == nullptr) return;
    
    // 递归删除所有子节点
    TreeNode<T>* child = node->firstChild;
    while (child != nullptr) {
        TreeNode<T>* next = child->nextSibling;
        delete_subtree(child);
        child = next;
    }
    
    // 删除当前节点
    delete node;
}

Copy



1
2
3
4
5
6
7
8
9



template<class T>
TreeNode * BinaryTree<T>::copy_(TreeNode* root){
	if (root != nullptr){
		TreeNode* t = new TreeNode(root->data);
		t->left = copy_(root->left);
		t->right = copy_(root->right);
	}
	return t;
}

Clear



1
2
3
4
5
6
7
8



template<class T>
void BinaryTree<T>::clear_(TreeNode* root){
	if(root != nullptr){
		clear_(root->left);
		clear_(root->right);
		delete root;
		}
}

Traversal

Depth-First 深度优先遍历

1. 前序遍历（Pre-order Traversal）
先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。

2. 中序遍历（In-order Traversal）
先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。

3. 后续遍历（Post-order Traversal）
先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。



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



template <class T>
void BinaryTree<T>::preOrder(TreeNode *root) {
    if (root != NULL) {
        std::cout << root->data << " "; // 访问根节点
        preOrder(root->left);           // 递归遍历左子树
        preOrder(root->right);          // 递归遍历右子树
    }
}

template <class T>
void BinaryTree<T>::inOrder(TreeNode *root) {
    if (root != NULL) {
        inOrder(root->left);            // 递归遍历左子树
        std::cout << root->data << " "; // 访问根节点
        inOrder(root->right);           // 递归遍历右子树
    }
}

template <class T>
void BinaryTree<T>::postOrder(TreeNode *root) {
    if (root != NULL) {
        postOrder(root->left);           // 递归遍历左子树
        postOrder(root->right);          // 递归遍历右子树
        std::cout << root->data << " "; // 访问根节点
    }
}
Level-order Traversal 层序遍历


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16



template <class T>
void BinaryTree<T>::levelOrder(TreeNode *root) {
    std::queue<TreeNode *> q;
    q.enqueue(root);
    while (!q.isEmpty()) {
        TreeNode *node = q.dequeue();
        if (node != NULL) {
            std::cout << node->data << " ";
            if (node->left)
                q.enqueue(node->left);
            if (node->right)
                q.enqueue(node->right);
        }
    }
}

Breadth First V.S. Depth First

[!tip] Traversal 与 Search
Traversal: 遍历每一个节点一次
Search: 访问每个节点直到我们找到一个或多个满足要求的节点

49f0bf09f4436bd327c21c035b2a368.png

特性 BFS DFS
数据结构 队列 (Queue) 栈 (Stack)
访问顺序 按层级 按深度
空间复杂度 可能更高 (需存储整层顶点) 通常较低
适用场景 寻找最短路径、关系网络分析 拓扑排序、连通性检测
实现难度 稍微复杂 相对简单

Binary Search Tree

Definition

性能分析

具体实现

BST 操作与 C++ 实现思路

BST 复杂度分析

Operation BST Average Case BST Worst Case Sorted Array Sorted List
find $O(\log n)$ $O(n)$ $O(\log n)$ $O(n)$
insert $O(\log n)$ $O(n)$ $O(n)$ $O(n)$
delete $O(\log n)$ $O(n)$ $O(n)$ $O(n)$
traverse $O(n)$ $O(n)$ $O(n)$ $O(n)$

Rotation

Height-balanced Tree

高度平衡的定义

Rotation

1. 旋转的目的

2. 旋转的种类

3. 旋转的步骤 (以右旋为例)

  1. 找到不平衡的节点：从底向上找到第一个平衡因子绝对值大于 1 的节点。
  2. 确定旋转类型：根据不平衡节点的子树结构，确定需要进行哪种旋转。

核心旋转操作

我们先定义两个基本的旋转操作：左旋和右旋。

1. 右旋 (Right Rotation)

当节点 z 的左子树 (y) 比右子树过高，并且不平衡是由插入到 y 的左子树 (x) 中引起的时 (即 Left-Left Case)，通常执行右旋。

目标：将 y 提升为子树的新根，z 成为 y 的右子节点。

图示：



1
2
3
4
5
6
7



      z              y
     / \            / \
    y   T4  ===>   x   z      (围绕 z 进行右旋)
   / \           / \   / \
  x   T3        T1 T2  T3 T4
 / \
T1  T2

操作步骤：

  1. y 的右子树 (T3) 成为 z 的新的左子树。
  2. z 成为 y 的新的右子节点。
  3. y 成为原 z 位置的新根节点。

伪代码/C++ 代码 (假设节点结构包含 left, right, height 成员)：



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
30
31
32
33
34
35
36
37
38
39
40
41



struct Node {
    int key;
    Node *left;
    Node *right;
    int height;
    // Constructor...
};

// Helper function to get height (handles NULL nodes)
int height(Node* N) {
    if (N == nullptr)
        return -1; // 或者 0, 取决于高度定义 (空树高度为-1 或 叶子节点高度为0)
                   // 这里假设空树高度为 -1, 叶子节点高度为 0
    return N->height;
}

// Helper function to update height of a node
void updateHeight(Node* N) {
    if (N != nullptr) {
        N->height = 1 + std::max(height(N->left), height(N->right));
    }
}

// 执行右旋操作
// 输入: z - 需要围绕其进行右旋的节点 (不平衡节点)
// 返回: 旋转后子树的新根节点 (y)
Node* rightRotate(Node* z) {
    Node* y = z->left;       // y 是 z 的左孩子
    Node* T3 = y->right;     // T3 是 y 的右子树

    // 执行旋转
    y->right = z;            // z 成为 y 的右孩子
    z->left = T3;            // T3 成为 z 的左孩子

    // 更新高度 (必须先更新 z, 再更新 y, 因为 y 的高度依赖于更新后的 z)
    updateHeight(z);
    updateHeight(y);

    // 返回新的根节点
    return y;
}

现实比喻：想象 z 是一个枢轴，你抓住 y 向上推，z 就顺时针旋转下来成为 y 的右边部分，而原来夹在 y 和 z 之间的 T3 就挂在了 z 的左边空位上。

2. 左旋 (Left Rotation)

当节点 z 的右子树 (y) 比左子树过高，并且不平衡是由插入到 y 的右子树 (x) 中引起的时 (即 Right-Right Case)，通常执行左旋。

目标：将 y 提升为子树的新根，z 成为 y 的左子节点。

图示：



1
2
3
4
5
6
7



      z             y
     / \           / \
    T1  y   ===>  z   x       (围绕 z 进行左旋)
       / \       / \ / \
      T2  x     T1 T2 T3 T4
         / \
        T3 T4

操作步骤：

  1. y 的左子树 (T2) 成为 z 的新的右子树。
  2. z 成为 y 的新的左子节点。
  3. y 成为原 z 位置的新根节点。

伪代码/C++ 代码：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18



// 执行左旋操作
// 输入: z - 需要围绕其进行左旋的节点 (不平衡节点)
// 返回: 旋转后子树的新根节点 (y)
Node* leftRotate(Node* z) {
    Node* y = z->right;      // y 是 z 的右孩子
    Node* T2 = y->left;      // T2 是 y 的左子树

    // 执行旋转
    y->left = z;             // z 成为 y 的左孩子
    z->right = T2;           // T2 成为 z 的右孩子

    // 更新高度 (先更新 z, 再更新 y)
    updateHeight(z);
    updateHeight(y);

    // 返回新的根节点
    return y;
}

现实比喻：与右旋相反，抓住 y 向上推，z 逆时针旋转下来成为 y 的左边部分，原来夹在 z 和 y 之间的 T2 挂在了 z 的右边空位上。

当插入路径形成 “zig-zag” 形状时，需要进行两次旋转。

3. 左右旋 (Left-Right Rotation, LR)

当节点 z 的左子树 (y) 比右子树过高，但！不平衡是由插入到 y 的右子树 (x) 中引起的时 (即 Left-Right Case)。形状像一个 “<”。

目标：将 x 提升为子树的新根。

图示：



1
2
3
4
5
6
7



      z               z             x
     / \             / \           / \
    y   T4  -(L@y)-> x   T4 -(R@z)-> y   z      (先对 y 左旋, 再对 z 右旋)
   / \             / \         / \ / \
  T1  x           y   T3       T1 T2 T3 T4
     / \         / \
    T2 T3       T1 T2

操作步骤：

  1. 先对 z 的左子节点 y 进行一次左旋 (Left Rotation)。这会将 LR 情况转化为 LL 情况。
  2. 再对不平衡节点 z 进行一次右旋 (Right Rotation)。

伪代码/C++ 代码：



1
2
3
4
5
6
7
8
9
10



// 执行左右旋操作
// 输入: z - 不平衡节点
// 返回: 旋转后子树的新根节点 (x)
Node* leftRightRotate(Node* z) {
    // 1. 对 z 的左孩子 y 进行左旋
    z->left = leftRotate(z->left); // y 被 x 替换, 返回的新根 x 成为 z 的新左孩子

    // 2. 对 z 进行右旋
    return rightRotate(z);         // 返回最终的新根 x
}

现实比喻：想象 < 形状的链条，先把它掰直 (对 y 左旋，变成 / 形状，即 LL)，然后再整体旋转 (对 z 右旋) 使其平衡。

4. 右左旋 (Right-Left Rotation, RL)

当节点 z 的右子树 (y) 比左子树过高，但！不平衡是由插入到 y 的左子树 (x) 中引起的时 (即 Right-Left Case)。形状像一个 “>”。

目标：将 x 提升为子树的新根。

图示：



1
2
3
4
5
6
7



       z              z              x
      / \            / \            / \
     T1  y -(R@y)-> T1  x  -(L@z)-> z   y      (先对 y 右旋, 再对 z 左旋)
        / \            / \        / \ / \
       x   T4         T2  y      T1 T2 T3 T4
      / \                / \
     T2 T3              T3 T4

操作步骤：

  1. 先对 z 的右子节点 y 进行一次右旋 (Right Rotation)。这会将 RL 情况转化为 RR 情况。
  2. 再对不平衡节点 z 进行一次左旋 (Left Rotation)。

伪代码/C++ 代码：



1
2
3
4
5
6
7
8
9
10



// 执行右左旋操作
// 输入: z - 不平衡节点
// 返回: 旋转后子树的新根节点 (x)
Node* rightLeftRotate(Node* z) {
    // 1. 对 z 的右孩子 y 进行右旋
    z->right = rightRotate(z->right); // y 被 x 替换, 返回的新根 x 成为 z 的新右孩子

    // 2. 对 z 进行左旋
    return leftRotate(z);          // 返回最终的新根 x
}

现实比喻：想象 > 形状的链条，先把它掰直 (对 y 右旋，变成 \ 形状，即 RR)，然后再整体旋转 (对 z 左旋) 使其平衡。

总结

Dictionary ADT

Dictionary（字典）是一种关联式容器，存储键值对。

主要操作：