C实现二叉树7种核心操作从存储结构到AVL树调整的完整代码库1. 二叉树基础与存储结构实现二叉树作为计算机科学中最基础的非线性数据结构之一其高效的组织方式使其在搜索、排序等领域有着广泛应用。理解二叉树的存储结构是掌握其操作的关键第一步。顺序存储实现通常适用于完全二叉树其核心思想是利用数组下标反映结点间的逻辑关系。对于非完全二叉树这种存储方式会造成空间浪费#define MAX_SIZE 100 struct SeqTreeNode { int data; bool isEmpty true; }; class SeqBinaryTree { public: SeqTreeNode tree[MAX_SIZE]; void init() { for(int i0; iMAX_SIZE; i) { tree[i].isEmpty true; } } // 获取父节点索引i1时有效 int parent(int i) { return i/2; } // 获取左孩子索引 int leftChild(int i) { return 2*i; } // 获取右孩子索引 int rightChild(int i) { return 2*i1; } };链式存储则更为灵活适合任意形态的二叉树。我们定义结点结构体和二叉树类struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; class LinkedBinaryTree { private: TreeNode* root; public: LinkedBinaryTree() : root(nullptr) {} // 递归销毁树 ~LinkedBinaryTree() { destroyTree(root); } void destroyTree(TreeNode* node) { if(node) { destroyTree(node-left); destroyTree(node-right); delete node; } } };两种存储方式的对比特性顺序存储链式存储空间利用率完全二叉树时高总是高效访问速度O(1)随机访问需要遍历插入删除需要移动元素只需修改指针适用场景完全二叉树任意二叉树实际工程中选择存储结构时需要考虑二叉树的具体形态和操作频率。对于频繁修改的二叉树链式存储通常是更好的选择。2. 二叉树遍历算法实现遍历是二叉树最基本的操作分为递归和非递归两种实现方式。理解不同遍历方式的特性对解决树相关问题至关重要。递归遍历代码简洁但存在栈溢出风险适合小规模数据// 先序遍历 void preOrder(TreeNode* root) { if(!root) return; cout root-val ; preOrder(root-left); preOrder(root-right); } // 中序遍历 void inOrder(TreeNode* root) { if(!root) return; inOrder(root-left); cout root-val ; inOrder(root-right); } // 后序遍历 void postOrder(TreeNode* root) { if(!root) return; postOrder(root-left); postOrder(root-right); cout root-val ; }非递归遍历利用栈模拟递归过程更适合大规模数据。以下是中序遍历的非递归实现void inOrderIterative(TreeNode* root) { stackTreeNode* s; TreeNode* curr root; while(curr || !s.empty()) { while(curr) { s.push(curr); curr curr-left; } curr s.top(); s.pop(); cout curr-val ; curr curr-right; } }层次遍历使用队列实现广度优先搜索常用于求树的宽度或层序输出void levelOrder(TreeNode* root) { if(!root) return; queueTreeNode* q; q.push(root); while(!q.empty()) { TreeNode* node q.front(); q.pop(); cout node-val ; if(node-left) q.push(node-left); if(node-right) q.push(node-right); } }遍历方式的选择建议需要先处理根节点时用先序需要有序输出二叉搜索树时用中序需要先处理子节点时用后序需要按层处理时用层次遍历3. 二叉排序树(BST)的实现二叉排序树BST是一种特殊的二叉树其中每个节点的值大于其左子树所有节点的值小于其右子树所有节点的值。这种性质使得BST在查找、插入和删除操作上非常高效。BST查找操作实现如下TreeNode* searchBST(TreeNode* root, int key) { if(!root || root-val key) return root; if(key root-val) return searchBST(root-left, key); else return searchBST(root-right, key); }BST插入操作需要保持排序性质TreeNode* insertBST(TreeNode* root, int val) { if(!root) return new TreeNode(val); if(val root-val) root-left insertBST(root-left, val); else if(val root-val) root-right insertBST(root-right, val); return root; }BST删除操作最为复杂需要考虑三种情况TreeNode* deleteNode(TreeNode* root, int key) { if(!root) return nullptr; if(key root-val) { root-left deleteNode(root-left, key); } else if(key root-val) { root-right deleteNode(root-right, key); } else { // 节点只有一个子节点或没有子节点 if(!root-left) { TreeNode* temp root-right; delete root; return temp; } else if(!root-right) { TreeNode* temp root-left; delete root; return temp; } // 节点有两个子节点找到右子树的最小节点 TreeNode* temp minValueNode(root-right); root-val temp-val; root-right deleteNode(root-right, temp-val); } return root; } TreeNode* minValueNode(TreeNode* node) { TreeNode* current node; while(current current-left) current current-left; return current; }BST操作的性能分析操作平均时间复杂度最坏时间复杂度查找O(log n)O(n)插入O(log n)O(n)删除O(log n)O(n)当BST退化为链表时如插入有序序列性能会下降到O(n)。这就是为什么需要平衡二叉树AVL树来保证树的高度平衡。4. AVL树实现与平衡调整AVL树是一种自平衡二叉搜索树通过旋转操作保持树的平衡确保所有节点的左右子树高度差不超过1。AVL树节点结构需要增加高度信息struct AVLNode { int val; AVLNode *left; AVLNode *right; int height; AVLNode(int x) : val(x), left(nullptr), right(nullptr), height(1) {} };四种不平衡情况及旋转调整LL型右旋AVLNode* rightRotate(AVLNode* y) { AVLNode* x y-left; AVLNode* T2 x-right; x-right y; y-left T2; y-height max(getHeight(y-left), getHeight(y-right)) 1; x-height max(getHeight(x-left), getHeight(x-right)) 1; return x; }RR型左旋AVLNode* leftRotate(AVLNode* x) { AVLNode* y x-right; AVLNode* T2 y-left; y-left x; x-right T2; x-height max(getHeight(x-left), getHeight(x-right)) 1; y-height max(getHeight(y-left), getHeight(y-right)) 1; return y; }LR型先左旋后右旋AVLNode* node ... // 不平衡节点 node-left leftRotate(node-left); return rightRotate(node);RL型先右旋后左旋AVLNode* node ... // 不平衡节点 node-right rightRotate(node-right); return leftRotate(node);AVL插入操作的完整实现AVLNode* insertAVL(AVLNode* node, int val) { // 1. 执行标准BST插入 if(!node) return new AVLNode(val); if(val node-val) node-left insertAVL(node-left, val); else if(val node-val) node-right insertAVL(node-right, val); else return node; // 不允许重复值 // 2. 更新节点高度 node-height 1 max(getHeight(node-left), getHeight(node-right)); // 3. 获取平衡因子 int balance getBalance(node); // 4. 处理不平衡情况 // LL if(balance 1 val node-left-val) return rightRotate(node); // RR if(balance -1 val node-right-val) return leftRotate(node); // LR if(balance 1 val node-left-val) { node-left leftRotate(node-left); return rightRotate(node); } // RL if(balance -1 val node-right-val) { node-right rightRotate(node-right); return leftRotate(node); } return node; }AVL树的性能优势保证最坏情况下O(log n)的查找、插入和删除时间复杂度适合查找密集型应用作为许多高级数据结构的基础5. 线索二叉树实现线索二叉树通过在空指针域中存储前驱或后继信息可以无需栈或递归实现高效遍历特别适合内存受限环境。线索二叉树节点结构enum PointerTag { CHILD, THREAD }; struct ThreadNode { int val; ThreadNode *left, *right; PointerTag ltag, rtag; ThreadNode(int x) : val(x), left(nullptr), right(nullptr), ltag(CHILD), rtag(CHILD) {} };中序线索化实现void inThreading(ThreadNode* p, ThreadNode* pre) { if(!p) return; inThreading(p-left, pre); if(!p-left) { p-ltag THREAD; p-left pre; } if(pre !pre-right) { pre-rtag THREAD; pre-right p; } pre p; inThreading(p-right, pre); }线索二叉树的中序遍历void inOrderTraverse(ThreadNode* root) { ThreadNode* p root; while(p) { // 找到最左节点 while(p-ltag CHILD) { p p-left; } cout p-val ; // 如果右指针是线索直接访问后继 while(p-rtag THREAD p-right) { p p-right; cout p-val ; } // 否则转向右子树 p p-right; } }线索二叉树的优势和应用场景不需要递归或栈节省内存空间可以快速找到前驱和后继节点适合嵌入式系统等资源受限环境数据库索引等需要频繁遍历的场景6. 二叉树的高级应用二叉树在实际工程中有许多高级应用以下是两个典型示例。哈夫曼编码树用于数据压缩struct HuffmanNode { char data; unsigned freq; HuffmanNode *left, *right; HuffmanNode(char data, unsigned freq) : data(data), freq(freq), left(nullptr), right(nullptr) {} }; struct compare { bool operator()(HuffmanNode* l, HuffmanNode* r) { return l-freq r-freq; } }; HuffmanNode* buildHuffmanTree(const unordered_mapchar, unsigned freqMap) { priority_queueHuffmanNode*, vectorHuffmanNode*, compare minHeap; for(auto pair : freqMap) minHeap.push(new HuffmanNode(pair.first, pair.second)); while(minHeap.size() ! 1) { HuffmanNode* left minHeap.top(); minHeap.pop(); HuffmanNode* right minHeap.top(); minHeap.pop(); HuffmanNode* top new HuffmanNode($, left-freq right-freq); top-left left; top-right right; minHeap.push(top); } return minHeap.top(); }表达式树用于数学表达式求值bool isOperator(char c) { return c || c - || c * || c /; } TreeNode* constructExpressionTree(const string postfix) { stackTreeNode* st; for(char c : postfix) { if(isOperator(c)) { TreeNode* right st.top(); st.pop(); TreeNode* left st.top(); st.pop(); TreeNode* node new TreeNode(c); node-left left; node-right right; st.push(node); } else { st.push(new TreeNode(c - 0)); // 假设是数字字符 } } return st.top(); } int evalExpressionTree(TreeNode* root) { if(!root) return 0; if(!root-left !root-right) return root-val; int l_val evalExpressionTree(root-left); int r_val evalExpressionTree(root-right); switch(root-val) { case : return l_val r_val; case -: return l_val - r_val; case *: return l_val * r_val; case /: return l_val / r_val; } return 0; }7. 性能优化与工程实践在实际工程中实现二叉树时需要考虑内存管理、并发安全和性能优化等问题。内存池优化减少频繁内存分配class TreeNodePool { private: vectorTreeNode* pool; size_t index 0; public: TreeNode* allocate(int val) { if(index pool.size()) { pool.push_back(new TreeNode(val)); return pool.back(); } pool[index]-val val; pool[index]-left pool[index]-right nullptr; return pool[index]; } void reset() { index 0; } ~TreeNodePool() { for(auto node : pool) delete node; } };线程安全实现考虑#include mutex class ConcurrentBinaryTree { private: TreeNode* root; mutable std::mutex mtx; public: void insert(int val) { std::lock_guardstd::mutex lock(mtx); // 插入逻辑... } bool search(int val) const { std::lock_guardstd::mutex lock(mtx); // 搜索逻辑... return false; } };性能测试对比BST vs AVL vs 红黑树操作BSTAVL红黑树查找O(n)O(log n)O(log n)插入O(n)O(log n)O(log n)删除O(n)O(log n)O(log n)旋转无多少适用场景随机数据查找密集插入/删除密集实际项目中STL中的map和set通常使用红黑树实现因为它在插入删除和查找之间提供了更好的平衡。而AVL树在查找密集型应用中表现更优。
C++实现二叉树 7种核心操作：从存储结构到AVL树调整的完整代码库
C实现二叉树7种核心操作从存储结构到AVL树调整的完整代码库1. 二叉树基础与存储结构实现二叉树作为计算机科学中最基础的非线性数据结构之一其高效的组织方式使其在搜索、排序等领域有着广泛应用。理解二叉树的存储结构是掌握其操作的关键第一步。顺序存储实现通常适用于完全二叉树其核心思想是利用数组下标反映结点间的逻辑关系。对于非完全二叉树这种存储方式会造成空间浪费#define MAX_SIZE 100 struct SeqTreeNode { int data; bool isEmpty true; }; class SeqBinaryTree { public: SeqTreeNode tree[MAX_SIZE]; void init() { for(int i0; iMAX_SIZE; i) { tree[i].isEmpty true; } } // 获取父节点索引i1时有效 int parent(int i) { return i/2; } // 获取左孩子索引 int leftChild(int i) { return 2*i; } // 获取右孩子索引 int rightChild(int i) { return 2*i1; } };链式存储则更为灵活适合任意形态的二叉树。我们定义结点结构体和二叉树类struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; class LinkedBinaryTree { private: TreeNode* root; public: LinkedBinaryTree() : root(nullptr) {} // 递归销毁树 ~LinkedBinaryTree() { destroyTree(root); } void destroyTree(TreeNode* node) { if(node) { destroyTree(node-left); destroyTree(node-right); delete node; } } };两种存储方式的对比特性顺序存储链式存储空间利用率完全二叉树时高总是高效访问速度O(1)随机访问需要遍历插入删除需要移动元素只需修改指针适用场景完全二叉树任意二叉树实际工程中选择存储结构时需要考虑二叉树的具体形态和操作频率。对于频繁修改的二叉树链式存储通常是更好的选择。2. 二叉树遍历算法实现遍历是二叉树最基本的操作分为递归和非递归两种实现方式。理解不同遍历方式的特性对解决树相关问题至关重要。递归遍历代码简洁但存在栈溢出风险适合小规模数据// 先序遍历 void preOrder(TreeNode* root) { if(!root) return; cout root-val ; preOrder(root-left); preOrder(root-right); } // 中序遍历 void inOrder(TreeNode* root) { if(!root) return; inOrder(root-left); cout root-val ; inOrder(root-right); } // 后序遍历 void postOrder(TreeNode* root) { if(!root) return; postOrder(root-left); postOrder(root-right); cout root-val ; }非递归遍历利用栈模拟递归过程更适合大规模数据。以下是中序遍历的非递归实现void inOrderIterative(TreeNode* root) { stackTreeNode* s; TreeNode* curr root; while(curr || !s.empty()) { while(curr) { s.push(curr); curr curr-left; } curr s.top(); s.pop(); cout curr-val ; curr curr-right; } }层次遍历使用队列实现广度优先搜索常用于求树的宽度或层序输出void levelOrder(TreeNode* root) { if(!root) return; queueTreeNode* q; q.push(root); while(!q.empty()) { TreeNode* node q.front(); q.pop(); cout node-val ; if(node-left) q.push(node-left); if(node-right) q.push(node-right); } }遍历方式的选择建议需要先处理根节点时用先序需要有序输出二叉搜索树时用中序需要先处理子节点时用后序需要按层处理时用层次遍历3. 二叉排序树(BST)的实现二叉排序树BST是一种特殊的二叉树其中每个节点的值大于其左子树所有节点的值小于其右子树所有节点的值。这种性质使得BST在查找、插入和删除操作上非常高效。BST查找操作实现如下TreeNode* searchBST(TreeNode* root, int key) { if(!root || root-val key) return root; if(key root-val) return searchBST(root-left, key); else return searchBST(root-right, key); }BST插入操作需要保持排序性质TreeNode* insertBST(TreeNode* root, int val) { if(!root) return new TreeNode(val); if(val root-val) root-left insertBST(root-left, val); else if(val root-val) root-right insertBST(root-right, val); return root; }BST删除操作最为复杂需要考虑三种情况TreeNode* deleteNode(TreeNode* root, int key) { if(!root) return nullptr; if(key root-val) { root-left deleteNode(root-left, key); } else if(key root-val) { root-right deleteNode(root-right, key); } else { // 节点只有一个子节点或没有子节点 if(!root-left) { TreeNode* temp root-right; delete root; return temp; } else if(!root-right) { TreeNode* temp root-left; delete root; return temp; } // 节点有两个子节点找到右子树的最小节点 TreeNode* temp minValueNode(root-right); root-val temp-val; root-right deleteNode(root-right, temp-val); } return root; } TreeNode* minValueNode(TreeNode* node) { TreeNode* current node; while(current current-left) current current-left; return current; }BST操作的性能分析操作平均时间复杂度最坏时间复杂度查找O(log n)O(n)插入O(log n)O(n)删除O(log n)O(n)当BST退化为链表时如插入有序序列性能会下降到O(n)。这就是为什么需要平衡二叉树AVL树来保证树的高度平衡。4. AVL树实现与平衡调整AVL树是一种自平衡二叉搜索树通过旋转操作保持树的平衡确保所有节点的左右子树高度差不超过1。AVL树节点结构需要增加高度信息struct AVLNode { int val; AVLNode *left; AVLNode *right; int height; AVLNode(int x) : val(x), left(nullptr), right(nullptr), height(1) {} };四种不平衡情况及旋转调整LL型右旋AVLNode* rightRotate(AVLNode* y) { AVLNode* x y-left; AVLNode* T2 x-right; x-right y; y-left T2; y-height max(getHeight(y-left), getHeight(y-right)) 1; x-height max(getHeight(x-left), getHeight(x-right)) 1; return x; }RR型左旋AVLNode* leftRotate(AVLNode* x) { AVLNode* y x-right; AVLNode* T2 y-left; y-left x; x-right T2; x-height max(getHeight(x-left), getHeight(x-right)) 1; y-height max(getHeight(y-left), getHeight(y-right)) 1; return y; }LR型先左旋后右旋AVLNode* node ... // 不平衡节点 node-left leftRotate(node-left); return rightRotate(node);RL型先右旋后左旋AVLNode* node ... // 不平衡节点 node-right rightRotate(node-right); return leftRotate(node);AVL插入操作的完整实现AVLNode* insertAVL(AVLNode* node, int val) { // 1. 执行标准BST插入 if(!node) return new AVLNode(val); if(val node-val) node-left insertAVL(node-left, val); else if(val node-val) node-right insertAVL(node-right, val); else return node; // 不允许重复值 // 2. 更新节点高度 node-height 1 max(getHeight(node-left), getHeight(node-right)); // 3. 获取平衡因子 int balance getBalance(node); // 4. 处理不平衡情况 // LL if(balance 1 val node-left-val) return rightRotate(node); // RR if(balance -1 val node-right-val) return leftRotate(node); // LR if(balance 1 val node-left-val) { node-left leftRotate(node-left); return rightRotate(node); } // RL if(balance -1 val node-right-val) { node-right rightRotate(node-right); return leftRotate(node); } return node; }AVL树的性能优势保证最坏情况下O(log n)的查找、插入和删除时间复杂度适合查找密集型应用作为许多高级数据结构的基础5. 线索二叉树实现线索二叉树通过在空指针域中存储前驱或后继信息可以无需栈或递归实现高效遍历特别适合内存受限环境。线索二叉树节点结构enum PointerTag { CHILD, THREAD }; struct ThreadNode { int val; ThreadNode *left, *right; PointerTag ltag, rtag; ThreadNode(int x) : val(x), left(nullptr), right(nullptr), ltag(CHILD), rtag(CHILD) {} };中序线索化实现void inThreading(ThreadNode* p, ThreadNode* pre) { if(!p) return; inThreading(p-left, pre); if(!p-left) { p-ltag THREAD; p-left pre; } if(pre !pre-right) { pre-rtag THREAD; pre-right p; } pre p; inThreading(p-right, pre); }线索二叉树的中序遍历void inOrderTraverse(ThreadNode* root) { ThreadNode* p root; while(p) { // 找到最左节点 while(p-ltag CHILD) { p p-left; } cout p-val ; // 如果右指针是线索直接访问后继 while(p-rtag THREAD p-right) { p p-right; cout p-val ; } // 否则转向右子树 p p-right; } }线索二叉树的优势和应用场景不需要递归或栈节省内存空间可以快速找到前驱和后继节点适合嵌入式系统等资源受限环境数据库索引等需要频繁遍历的场景6. 二叉树的高级应用二叉树在实际工程中有许多高级应用以下是两个典型示例。哈夫曼编码树用于数据压缩struct HuffmanNode { char data; unsigned freq; HuffmanNode *left, *right; HuffmanNode(char data, unsigned freq) : data(data), freq(freq), left(nullptr), right(nullptr) {} }; struct compare { bool operator()(HuffmanNode* l, HuffmanNode* r) { return l-freq r-freq; } }; HuffmanNode* buildHuffmanTree(const unordered_mapchar, unsigned freqMap) { priority_queueHuffmanNode*, vectorHuffmanNode*, compare minHeap; for(auto pair : freqMap) minHeap.push(new HuffmanNode(pair.first, pair.second)); while(minHeap.size() ! 1) { HuffmanNode* left minHeap.top(); minHeap.pop(); HuffmanNode* right minHeap.top(); minHeap.pop(); HuffmanNode* top new HuffmanNode($, left-freq right-freq); top-left left; top-right right; minHeap.push(top); } return minHeap.top(); }表达式树用于数学表达式求值bool isOperator(char c) { return c || c - || c * || c /; } TreeNode* constructExpressionTree(const string postfix) { stackTreeNode* st; for(char c : postfix) { if(isOperator(c)) { TreeNode* right st.top(); st.pop(); TreeNode* left st.top(); st.pop(); TreeNode* node new TreeNode(c); node-left left; node-right right; st.push(node); } else { st.push(new TreeNode(c - 0)); // 假设是数字字符 } } return st.top(); } int evalExpressionTree(TreeNode* root) { if(!root) return 0; if(!root-left !root-right) return root-val; int l_val evalExpressionTree(root-left); int r_val evalExpressionTree(root-right); switch(root-val) { case : return l_val r_val; case -: return l_val - r_val; case *: return l_val * r_val; case /: return l_val / r_val; } return 0; }7. 性能优化与工程实践在实际工程中实现二叉树时需要考虑内存管理、并发安全和性能优化等问题。内存池优化减少频繁内存分配class TreeNodePool { private: vectorTreeNode* pool; size_t index 0; public: TreeNode* allocate(int val) { if(index pool.size()) { pool.push_back(new TreeNode(val)); return pool.back(); } pool[index]-val val; pool[index]-left pool[index]-right nullptr; return pool[index]; } void reset() { index 0; } ~TreeNodePool() { for(auto node : pool) delete node; } };线程安全实现考虑#include mutex class ConcurrentBinaryTree { private: TreeNode* root; mutable std::mutex mtx; public: void insert(int val) { std::lock_guardstd::mutex lock(mtx); // 插入逻辑... } bool search(int val) const { std::lock_guardstd::mutex lock(mtx); // 搜索逻辑... return false; } };性能测试对比BST vs AVL vs 红黑树操作BSTAVL红黑树查找O(n)O(log n)O(log n)插入O(n)O(log n)O(log n)删除O(n)O(log n)O(log n)旋转无多少适用场景随机数据查找密集插入/删除密集实际项目中STL中的map和set通常使用红黑树实现因为它在插入删除和查找之间提供了更好的平衡。而AVL树在查找密集型应用中表现更优。
