十三，數據結構-樹

定義

樹也是基于節點的數據結構，和鏈表不同的是，樹的節點可以指向多個節點。首先對樹的一些常用術語進行說明：

最上面的節點叫做根節點，根位于樹頂，如圖中的節點A；
和族譜一樣，節點有后代和祖先；節點的后代即起源于該節點的全部節點，祖先即可以派生出該節點的節點；
樹有層級，每一層都是樹的一行，如上圖，樹有三層；
樹的一個屬性是它是否平衡，即如果子樹中的節點數量相同，則這棵樹是平衡的，上圖中的樹就是不平衡的；

二叉查找樹

二叉查找樹也是樹的一種，其特征如下：

每個節點最多有一個左子節點和右子節點
一個節點的左子樹中的值都小于節點本身，同時右子樹中的值都大于節點本身；

實現

二叉樹實現如下：

#include <iostream>
#include <memory>// 二叉樹節點類
template <typename T>
class TreeNode {
public:T data;std::shared_ptr<TreeNode<T>> left;std::shared_ptr<TreeNode<T>> right;TreeNode(T value) : data(value), left(nullptr), right(nullptr) {}
};

二叉樹查找

二叉樹查找步驟如下：

以根節點為當前節點；
讀取當前節點數值；
如果當前數值為要查找的數值，則停止查找并返回；
如果當前值大于要查找的數值，則在其左子樹中繼續查找；
如果當前值小于要查找的數值，則在右子樹中繼續查找；
重復1-5步，直到找到對應數值，或者到達了樹的底端，即數值不在該樹中；

注意觀察可以發現，每次查找都會排除大約一半的節點，因此可以推測二叉查找樹的查找效率為O( $log_{2}N$ )，之所以說大約為這個效率，是因為只有二叉查找樹的每一行節點都填滿（即是一棵平衡二叉樹），則上述特性才成立即：如果一棵平衡的二叉樹中有N個節點，則就會有大約logN層。代碼實現如下：

bool searchRecursive(std::shared_ptr<TreeNode<T>> node, T value) const {if (!node) {return false;}if (value == node->data) {return true;} else if (value < node->data) {return searchRecursive(node->left, value);} else {return searchRecursive(node->right, value);}}

二叉樹插入

二叉樹的插入是基于二叉樹的查找，即找到要插入的位置后插入（方法同上述中的二叉樹查找），其效率為O(logN)+1,代碼實現如下：

    // 遞歸插入節點std::shared_ptr<TreeNode<T>> insertRecursive(std::shared_ptr<TreeNode<T>> node, T value) {if (!node) {return std::make_shared<TreeNode<T>>(value);}if (value < node->data) {node->left = insertRecursive(node->left, value);} else if (value > node->data) {node->right = insertRecursive(node->right, value);}return node;}

二叉樹刪除

二叉樹查找樹的刪除是最復雜的部分，其步驟如下：

如果要刪除的節點沒有子節點，那么就可以直接刪除該節點；
如果要刪除的節點有一個子節點，那么就在刪除該節點的同時把子節點插到該節點的位置；
如果要刪除的節點有兩個子節點，則需要把要刪除的節點替換為其后繼節點，后繼節點即大于被刪除節點的所有子節點中最小的那個；
如果需要尋找后繼節點，則需要先移動到被刪除節點的右子節點，然后沿左節點的鏈接移動到左子結點，直到找不到任何左子結點為止，最下的這個值即后繼節點；
如果后繼節點有一個右子節點，則在將后繼節點放置到被刪除節點的位置之后，把這個右子節點變成后繼節點曾經的父節點的左子結點。

刪除的效率和插入以及查找類似，均為O(logN)，代碼如下：

    // 查找最小節點std::shared_ptr<TreeNode<T>> findMin(std::shared_ptr<TreeNode<T>> node) const {while (node && node->left) {node = node->left;}return node;}// 遞歸刪除節點std::shared_ptr<TreeNode<T>> deleteRecursive(std::shared_ptr<TreeNode<T>> node, T value) {if (!node) {return nullptr;}if (value < node->data) {node->left = deleteRecursive(node->left, value);} else if (value > node->data) {node->right = deleteRecursive(node->right, value);} else {// 找到要刪除的節點if (!node->left) {return node->right;} else if (!node->right) {return node->left;}// 有兩個子節點的情況：找到右子樹的最小節點替換當前節點std::shared_ptr<TreeNode<T>> temp = findMin(node->right);node->data = temp->data;node->right = deleteRecursive(node->right, temp->data);}return node;}

遍歷-前、中、后

二叉查詢樹的遍歷，即訪問所有節點，分類為三種：前序、中序、后序。其實這里的前、中、后針對的是調用遍歷函數時的當前節點，前的意思就是先訪問當前節點，再訪問左、右子節點；中的意思就是先訪問左子節點，再訪問當前節點，最后訪問右子節點；后的意思是先訪問左、右子節點，最后訪問本節點，其實現如下：

    // 中序遍歷（遞歸）void inorderRecursive(std::shared_ptr<TreeNode<T>> node) const {if (!node) return;inorderRecursive(node->left);std::cout << node->data << " ";inorderRecursive(node->right);}// 前序遍歷（遞歸）void preorderRecursive(std::shared_ptr<TreeNode<T>> node) const {if (!node) return;std::cout << node->data << " ";preorderRecursive(node->left);preorderRecursive(node->right);}// 后序遍歷（遞歸）void postorderRecursive(std::shared_ptr<TreeNode<T>> node) const {if (!node) return;postorderRecursive(node->left);postorderRecursive(node->right);std::cout << node->data << " ";}

以上就是本節關于二叉查找樹的全部內容，樹還有很多形式，這里挑選比較常用、簡單的樹形結構來進行講解，不過今后有了AI，這些數據結構和算法的實現將會比較簡單，程序員更多地是理解原理以及優化。全部代碼整理如下：

#include <iostream>
#include <memory>// 二叉樹節點類
template <typename T>
class TreeNode {
public:T data;std::shared_ptr<TreeNode<T>> left;std::shared_ptr<TreeNode<T>> right;TreeNode(T value) : data(value), left(nullptr), right(nullptr) {}
};// 二叉查找樹類
template <typename T>
class BinarySearchTree {
private:std::shared_ptr<TreeNode<T>> root;// 遞歸插入節點std::shared_ptr<TreeNode<T>> insertRecursive(std::shared_ptr<TreeNode<T>> node, T value) {if (!node) {return std::make_shared<TreeNode<T>>(value);}if (value < node->data) {node->left = insertRecursive(node->left, value);} else if (value > node->data) {node->right = insertRecursive(node->right, value);}return node;}// 遞歸查找節點bool searchRecursive(std::shared_ptr<TreeNode<T>> node, T value) const {if (!node) {return false;}if (value == node->data) {return true;} else if (value < node->data) {return searchRecursive(node->left, value);} else {return searchRecursive(node->right, value);}}// 查找最小節點std::shared_ptr<TreeNode<T>> findMin(std::shared_ptr<TreeNode<T>> node) const {while (node && node->left) {node = node->left;}return node;}// 遞歸刪除節點std::shared_ptr<TreeNode<T>> deleteRecursive(std::shared_ptr<TreeNode<T>> node, T value) {if (!node) {return nullptr;}if (value < node->data) {node->left = deleteRecursive(node->left, value);} else if (value > node->data) {node->right = deleteRecursive(node->right, value);} else {// 找到要刪除的節點if (!node->left) {return node->right;} else if (!node->right) {return node->left;}// 有兩個子節點的情況：找到右子樹的最小節點替換當前節點std::shared_ptr<TreeNode<T>> temp = findMin(node->right);node->data = temp->data;node->right = deleteRecursive(node->right, temp->data);}return node;}// 中序遍歷（遞歸）void inorderRecursive(std::shared_ptr<TreeNode<T>> node) const {if (!node) return;inorderRecursive(node->left);std::cout << node->data << " ";inorderRecursive(node->right);}// 前序遍歷（遞歸）void preorderRecursive(std::shared_ptr<TreeNode<T>> node) const {if (!node) return;std::cout << node->data << " ";preorderRecursive(node->left);preorderRecursive(node->right);}// 后序遍歷（遞歸）void postorderRecursive(std::shared_ptr<TreeNode<T>> node) const {if (!node) return;postorderRecursive(node->left);postorderRecursive(node->right);std::cout << node->data << " ";}public:BinarySearchTree() : root(nullptr) {}// 插入值void insert(T value) {root = insertRecursive(root, value);}// 查找值bool search(T value) const {return searchRecursive(root, value);}// 刪除值void remove(T value) {root = deleteRecursive(root, value);}// 中序遍歷void inorder() const {std::cout << "中序遍歷: ";inorderRecursive(root);std::cout << std::endl;}// 前序遍歷void preorder() const {std::cout << "前序遍歷: ";preorderRecursive(root);std::cout << std::endl;}// 后序遍歷void postorder() const {std::cout << "后序遍歷: ";postorderRecursive(root);std::cout << std::endl;}// 判斷樹是否為空bool isEmpty() const {return root == nullptr;}
};// 示例用法
int main() {BinarySearchTree<int> bst;// 插入一些值bst.insert(50);bst.insert(30);bst.insert(20);bst.insert(40);bst.insert(70);bst.insert(60);bst.insert(80);// 遍歷二叉樹bst.inorder();bst.preorder();bst.postorder();// 搜索值std::cout << "搜索 40: " << (bst.search(40) ? "找到" : "未找到") << std::endl;std::cout << "搜索 90: " << (bst.search(90) ? "找到" : "未找到") << std::endl;// 刪除值std::cout << "\n刪除 20\n";bst.remove(20);bst.inorder();std::cout << "刪除 30\n";bst.remove(30);bst.inorder();std::cout << "刪除 50\n";bst.remove(50);bst.inorder();return 0;
}