一、樹的概念

樹是由n(n≥0)個節點組成的有限集合，它滿足以下條件：
?
1.?當n=0時，稱為空樹
2.?當n>0時，有且僅有一個特定的節點稱為根節點(root)
3.?其余節點可分為m(m≥0)個互不相交的有限集合，每個集合本身又是一棵樹，稱為根的子樹(subtree)
?
二、基本術語
?
- 節點(Node): 樹的基本單位，包含數據項和指向其他節點的指針
- 邊(Edge): 連接兩個節點的線
- 根節點(Root): 樹的最頂層節點，沒有父節點
- 父節點(Parent): 一個節點的直接上層節點
- 子節點(Child): 一個節點的直接下層節點
- 葉子節點(Leaf): 沒有子節點的節點
- 內部節點(Internal Node): 至少有一個子節點的節點
- 度(Degree): 一個節點擁有的子節點數目
- 樹的度: 樹中所有節點度的最大值
- 層次(Level): 根節點為第1層，其子節點為第2層，以此類推
- 高度/深度(Height/Depth): 樹中節點的最大層次數
- 兄弟節點(Sibling): 具有相同父節點的節點
- 祖先節點(Ancestor): 從根到該節點路徑上的所有節點
- 后代節點(Descendant): 某節點子樹中的所有節點
?
三、樹的分類
?
1.?二叉樹(Binary Tree): 每個節點最多有兩個子節點
- 滿二叉樹
- 完全二叉樹
- 二叉搜索樹(BST)
- 平衡二叉樹(AVL樹)
- 紅黑樹
2.?多叉樹: 每個節點可以有多個子節點
- B樹
- B+樹
- Trie樹(字典樹)
3.?其他特殊樹結構
- 堆(Heap)
- 哈夫曼樹
- 線段樹
- 樹狀數組
?
四、樹的存儲表示
?
1.?鏈式存儲
- 每個節點包含數據域和指針域
- 指針指向子節點
2.?順序存儲
- 使用數組存儲
- 對于完全二叉樹特別有效
?3.樹的簡單實現

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;// 定義樹節點類模板
template <typename T>
class TreeNode
{
public:T data;  // 節點存儲的數據TreeNode* firstChild;  // 指向該節點的第一個孩子節點TreeNode* nextSibling; // 指向該節點的下一個兄弟節點// 構造函數，初始化節點數據，將孩子和兄弟指針置為空TreeNode(T val) : data(val), firstChild(nullptr), nextSibling(nullptr) {}
};// 定義樹類模板
template <typename T>
class Tree
{
private:TreeNode<T>* root;  // 樹的根節點// 遞歸清空樹的輔助函數void clear(TreeNode<T>* node){if (node == nullptr) return;  // 如果節點為空，直接返回clear(node->firstChild);  // 遞歸清空當前節點的第一個孩子節點及其子樹clear(node->nextSibling); // 遞歸清空當前節點的下一個兄弟節點及其子樹delete node;  // 釋放當前節點的內存}public:// 構造函數，初始化根節點為空Tree() : root(nullptr) {}// 析構函數，調用 clear 函數清空整棵樹~Tree() { clear(root); }// 創建一個新的樹節點，返回新節點的指針TreeNode<T>* createNode(T data){return new TreeNode<T>(data);}// 設置樹的根節點void setRoot(TreeNode<T>* node){root = node;}// 獲取樹的根節點TreeNode<T>* getRoot() const{return root;}// 向指定父節點插入一個孩子節點void insertChild(TreeNode<T>* parent, TreeNode<T>* child){if (parent == nullptr) return;  // 如果父節點為空，直接返回if (parent->firstChild == nullptr){// 如果父節點沒有第一個孩子節點，將該孩子節點設為第一個孩子parent->firstChild = child;}else{// 否則，找到父節點孩子鏈表的末尾，將該孩子節點插入到末尾TreeNode<T>* sibling = parent->firstChild;while (sibling->nextSibling != nullptr){sibling = sibling->nextSibling;}sibling->nextSibling = child;}}// 前序遍歷樹void preOrderTraversal(TreeNode<T>* node){if (node == nullptr) return;  // 如果節點為空，直接返回cout << node->data << " ";  // 訪問當前節點的數據preOrderTraversal(node->firstChild);  // 遞歸前序遍歷當前節點的第一個孩子節點及其子樹preOrderTraversal(node->nextSibling); // 遞歸前序遍歷當前節點的下一個兄弟節點及其子樹}// 后序遍歷樹void postOrderTraversal(TreeNode<T>* node){if (node == nullptr) return;  // 如果節點為空，直接返回postOrderTraversal(node->firstChild);  // 遞歸后序遍歷當前節點的第一個孩子節點及其子樹cout << node->data << " ";  // 訪問當前節點的數據postOrderTraversal(node->nextSibling); // 遞歸后序遍歷當前節點的下一個兄弟節點及其子樹}// 層序遍歷樹void levelOrderTraversal(){if (root == nullptr) return;  // 如果根節點為空，直接返回queue<TreeNode<T>*> q;  // 定義一個隊列用于層序遍歷q.push(root);  // 將根節點入隊while (!q.empty()){TreeNode<T>* current = q.front();  // 獲取隊首節點q.pop();  // 隊首節點出隊cout << current->data << " ";  // 訪問當前節點的數據// 將當前節點的所有孩子節點依次入隊TreeNode<T>* child = current->firstChild;while (child != nullptr){q.push(child);child = child->nextSibling;}}}// 獲取樹的高度int getHeight(TreeNode<T>* node){if (node == nullptr) return 0;  // 如果節點為空，高度為 0int maxHeight = 0;  // 初始化最大子樹高度為 0TreeNode<T>* child = node->firstChild;while (child != nullptr){// 遞歸計算每個子樹的高度，并更新最大子樹高度maxHeight = max(maxHeight, getHeight(child));child = child->nextSibling;}return maxHeight + 1;  // 當前節點的高度為最大子樹高度加 1}// 計算樹中節點的總數int countNodes(TreeNode<T>* node){if (node == nullptr) return 0;  // 如果節點為空，節點數為 0// 當前節點及其子樹的節點總數為當前節點加上其第一個孩子節點及其子樹的節點數，再加上其兄弟節點及其子樹的節點數return 1 + countNodes(node->firstChild) + countNodes(node->nextSibling);}// 在樹中查找值為 value 的節點TreeNode<T>* findNode(TreeNode<T>* node, T value){if (node == nullptr) return nullptr;  // 如果節點為空，返回空指針if (node->data == value) return node;  // 如果當前節點的值等于要查找的值，返回當前節點的指針// 先在當前節點的第一個孩子節點及其子樹中查找TreeNode<T>* found = findNode(node->firstChild, value);if (found != nullptr) return found;// 若未找到，再在當前節點的下一個兄弟節點及其子樹中查找return findNode(node->nextSibling, value);}// 打印樹的結構，level 表示當前節點的層級void printTree(TreeNode<T>* node, int level = 0){if (node == nullptr) return;  // 如果節點為空，直接返回// 根據當前節點的層級打印相應數量的空格for (int i = 0; i < level; ++i){cout << "  ";}cout << node->data << endl;  // 打印當前節點的數據// 遞歸打印當前節點的第一個孩子節點及其子樹，層級加 1printTree(node->firstChild, level + 1);// 遞歸打印當前節點的下一個兄弟節點及其子樹，層級不變printTree(node->nextSibling, level);}
};int main()
{Tree<char> tree;  // 創建一個存儲字符類型數據的樹對象// 創建樹的各個節點TreeNode<char>* A = tree.createNode('A');TreeNode<char>* B = tree.createNode('B');TreeNode<char>* C = tree.createNode('C');TreeNode<char>* D = tree.createNode('D');TreeNode<char>* E = tree.createNode('E');TreeNode<char>* F = tree.createNode('F');TreeNode<char>* G = tree.createNode('G');// 構建樹的結構tree.setRoot(A);  // 設置 A 為根節點tree.insertChild(A, B);  // 將 B 插入為 A 的孩子節點tree.insertChild(A, C);  // 將 C 插入為 A 的孩子節點tree.insertChild(A, D);  // 將 D 插入為 A 的孩子節點tree.insertChild(B, E);  // 將 E 插入為 B 的孩子節點tree.insertChild(B, F);  // 將 F 插入為 B 的孩子節點tree.insertChild(D, G);  // 將 G 插入為 D 的孩子節點// 打印樹的結構cout << "Tree structure:" << endl;tree.printTree(tree.getRoot());cout << endl;// 進行各種遍歷測試cout << "Pre-order traversal: ";tree.preOrderTraversal(tree.getRoot());cout << endl;cout << "Post-order traversal: ";tree.postOrderTraversal(tree.getRoot());cout << endl;cout << "Level-order traversal: ";tree.levelOrderTraversal();cout << endl;// 測試其他功能cout << "Tree height: " << tree.getHeight(tree.getRoot()) << endl;cout << "Total nodes: " << tree.countNodes(tree.getRoot()) << endl;// 測試查找節點功能char searchValue = 'F';TreeNode<char>* found = tree.findNode(tree.getRoot(), searchValue);if (found){cout << "Found node: " << found->data << endl;}else{cout << "Node " << searchValue << " not found" << endl;}return 0;
}

五、樹的應用
?
- 文件系統目錄結構
- 數據庫索引
- 網絡路由算法
- 決策樹(機器學習)
- XML/HTML文檔對象模型(DOM)
- 組織結構圖
- 游戲中的場景圖
?
樹結構因其高效的查找、插入和刪除操作(O(log n)時間復雜度)而被廣泛應用于各種算法和系統中。