一、树的概念
非线性逻辑结构：树，所存储的数据结构之间的关系：一对多（每一个数据只有一个前驱，可以有多个后继），把数据放到节点中保存，由节点构成树，一般一个节点保存一个数据
树的各种概念
二、树的存储结构
树：n 个具有 1 对多关系的数据的集合
表示什么： n 个数据 父子兄弟关系
（1）双亲表示法：说清楚每个节点的父亲是谁
存数据： 数组
存父亲关系： 每个数据后跟着父亲的下标使用结构体数组存储即可
优点： 方便找父亲
缺点： 不方便找孩子和兄弟
#include"mycode.h"
//双亲表示法
struct treeNode
{
int val;
int parentIndex; // 父节点索引（根节点为-1）
treeNode(int n,int d) :val(n), parentIndex(d) {}
};
class parentTree
{
private:
//创建容器存储节点，及根节点的索引
vector<treeNode> nodes;
int rootindex;
int findIndex(int data)//查找父亲节点
{
for (int i = 0; i < nodes.size(); i++)
{
if (nodes[i].val == data)return i;
return -1;
}
}
public:
parentTree(int Rootdata) :rootindex(0)//添加根节点
{
nodes.emplace_back(Rootdata, -1);
}
void addNode(int data, int parentData)//添加节点
{
int i=findIndex(parentData);
if (i == -1)
{
cerr << "Error: Parent node " << parentData << " not found!\n";
return;
}
nodes.emplace_back(data, i);
}
void printTree()//通过父节点不断查找子节点进行打印
{
queue<int> q;//存储父节点的索引
q.push(rootindex);
cout << "Tree Structure:\n";
while (!q.empty())
{
int leveSize = q.size();//当前同一水平节点数
while (leveSize--)//打印各个节点
{
int curIndex = q.front();
treeNode cur = nodes[curIndex];
q.pop();
//收集当前节点的所有子节点
vector <int>children;
for (int i = 0; i < nodes.size(); i++)
{
if (nodes[i].parentIndex == curIndex)
{
children.push_back(i);
}
}
//打印当前节点的信息
std::cout << cur.val<< " (children: ";
for (int child : children)
{
cout << nodes[child].val << " ";
q.push(child);
}
cout << ") | ";
}
cout << "\n--------------------------------\n";
}
}
void displayNodes() {
cout << "\nNode List:\n";
cout << "Index\tData\tParent\n";
for (int i = 0; i < nodes.size(); ++i) {
int parentData = (nodes[i].parentIndex == -1) ? -1 : nodes[nodes[i].parentIndex].val;
cout << i << "\t" << nodes[i].val
<< "\t" << parentData << "\n";
}
}
};
（2）孩子表示法：说清楚每个节点的孩子都有谁
存数据： 数组
存孩子： 把孩子组成链表，挂在父亲数据的后面，本质上是一个结构体数组
优点： 方便找孩子
缺点： 不方便找父亲和兄弟
在 c++ 中：结构体为 节点数据 + 孩子节点指针数组
代码：
//树结构-孩子表示法：说清楚每个节点的孩子都有谁
#include <iostream>
#include <vector>
using namespace std;
struct treeNode
{
int val;//节点数据
vector<treeNode*> children;//孩子节点指针数组
treeNode(int value) :val(value) {}//初始化
};
// 递归打印树结构
void printTree(treeNode* root)
{
if (root == nullptr)//递归终止条件
{
return;
}
// 打印当前节点及其子节点
cout <<root->val << " -> ";
for (treeNode* child : root->children)
{
cout << child->val<<" ";
}
cout << endl;
// 递归打印每个子树
for (treeNode* child : root->children)
{
printTree(child);
}
}
// 递归释放树内存
void delete_Tree(treeNode* root)
{
if (!root)return;
for (treeNode* child : root->children)
{
delete_Tree(child);
}
delete(root);
}
int main()
{
treeNode* root = new treeNode(10);
root->children = { new treeNode(20) ,new treeNode(30),new treeNode(40) };
root->children[0]->children = { new treeNode(50),new treeNode(60) };
root->children[1]->children = { new treeNode(70) };
printTree(root);
return 0;
}
（3）孩子兄弟表示法：说清楚每个节点的长子和（亲兄弟）都有谁
基于递归采用二叉链表存树，二叉链表中的一个（二叉）节点对应树中的一个节点
二叉链表：
| child 指向长子节点 |
data | bro 指向右边第一个亲兄弟节点 |
|---|
优点： 方便找父亲和兄弟
缺点： 不方便找孩子
代码：
// c++_dataStructure_008.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
//树结构-（3）孩子兄弟表示法：说清楚每个节点的长子和（亲兄弟）都有谁
#include <iostream>
using namespace std;
struct treeNode//树节点
{
int data;//节点数据
treeNode* firstChild;//指向第一个字节点
treeNode* nextSibling;// 指向右侧兄弟节点
treeNode(int val) :data(val), firstChild(nullptr), nextSibling(nullptr) {}
};
// 递归打印树结构（前序遍历风格）
void printTree(treeNode* root, int depth=0)
{
if (root == nullptr)return;
// 打印当前节点缩进
for (int i = 0; i < depth; i++)
{
cout << " ";
}
cout << "└─" << root->data << endl;
// 先递归处理第一个子节点（深度+1）
printTree(root->firstChild, depth + 1);
// 再处理兄弟节点（保持相同深度）
printTree(root->nextSibling, depth);
}
// 创建示例树结构
treeNode* buildSampleTree()
{
/* 构建如下树结构：
10
/ | \
20 30 40
/ \ |
50 60 70
*/
treeNode* root = new treeNode(10);
// 创建并连接子节点
treeNode* node20=new treeNode(20);
treeNode* node30=new treeNode(30);
treeNode* node40=new treeNode(40);
// 连接根节点的第一个子节点链
root->firstChild = node20;
node20->nextSibling = node30;
node30->nextSibling = node40;
// 为20节点添加子节点
treeNode* node50 = new treeNode(50);
treeNode* node60 = new treeNode(60);
node20->firstChild = node50;
node50->nextSibling = node60;
treeNode* node70 = new treeNode(70);
node30->firstChild = node70;
return root;
}
void deleteTree(treeNode* root) {
if (!root) return;
// 先删除子节点链
deleteTree(root->firstChild);
// 再删除兄弟节点链
deleteTree(root->nextSibling);
// 最后删除当前节点
delete root;
}
//递归查找
treeNode* find(treeNode* head, int val)
{
if (head == nullptr)return nullptr;
if (head != nullptr && head->data == val)
{
return head;
}
treeNode* temp=find(head->firstChild, val);
if (temp != nullptr && temp->data == val)
{
return temp;
}
treeNode* ans=find(head->nextSibling, val);
if (ans != nullptr && ans->data == val)
{
return ans;
}
}
int main()
{
treeNode* root = buildSampleTree();
cout << "树结构（缩进表示层次）：" << endl;
printTree(root);
treeNode*ans=find(root, 29);
cout << ans->data << endl;
deleteTree(root);
return 0;
}
三、二叉树
1、二叉树的概念与储存
（1）概念
我们将度为 2 的树称为二叉树（一个节点最多只有两个孩子）
（2）两个特殊的二叉树：
满二叉树： ① 如果一个二叉树，除了叶子节点外，其余节点都有两个孩子且所有的叶子节点都在同一层
②如果一颗二叉树，根节点为第一层，那么第i层均为2\^n-1个节点，被称为满二叉树
③满二树的任意节点，要么度为0，要么度为1；
完全二叉树： 对一颗满二叉树，从上到下，从左到右进行编号，去掉若干个最大编号的树称为完全二叉树（相当于满二叉树一分）
（最多有一个度为一的节点）
（3）性质
1、在二叉树的第 i 层最多有 2^（i-1）个节点
2、深度为 k 的二叉树至多有 2-1 个节点
3、
4、具有 n 个节点的完全二叉树，其树的高度/深度为 log2N+1;
5、如果有一棵 n 个结点的完全二叉树，其结点编号按照层次序（从上到下，从左到右），则除根结点外，满足[i/2,i, 2i, 2i+1]的规则
2、二叉树的存储
（1）顺序存储：
直接利用数组存储，依靠性质 5，可以将任意棵二叉树构造成满二叉树结构或完全二叉树结构，依据下标规则，就可以找到⽗结点，子结点。
但是浪费空间比较严重；
（2）链式存储
由于二叉树的每个结点最多只能有两个子树，每个结点定义两个指针域和一个数据域即可。
代码：
// C++_dataStructure_009.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <queue>
using namespace std;
struct treeNode
{
int val;
treeNode* left;
treeNode* right;
treeNode(int value) :val(value), left(nullptr), right(nullptr) {}//初始化
};
class BinaryTree
{
private:
treeNode* root;
// 递归插入辅助函数（二叉搜索树方式）
void insertHelper(treeNode*& node, int value)
{
//当前节点为空：可以插入
if (node == nullptr)
{
node = new treeNode(value);
}
else if (value < node->val)
{
insertHelper(node->left, value);
}
else
{
insertHelper(node->right, value);
}
}
//先序遍历
void preOrder(treeNode* node)
{
if (node == nullptr) return;
cout << node->val << " ";
preOrder(node->left);
preOrder(node->right);
}
//中序遍历
void inOrder(treeNode* node)
{
if (node == nullptr) return;
inOrder(node->left);
cout << node->val << " ";
inOrder(node->right);
}
//后序遍历
void postOrder(treeNode* node)
{
if (node == nullptr) return;
postOrder(node->left);
postOrder(node->right);
cout << node->val << " ";
}
void clear(treeNode* node) {
if (!node) return;
clear(node->left);
clear(node->right);
delete node;
}
public:
BinaryTree() :root(nullptr) {}
~BinaryTree() {
clear(root);
}
// 插入方法（对外接口）
void insert(int value) {
insertHelper(root, value);
}
// 遍历方法（对外接口）
void preOrderTraversal() {
cout << "前序遍历: ";
preOrder(root);
cout << endl;
}
void inOrderTraversal() {
cout << "中序遍历: ";
inOrder(root);
cout << endl;
}
void postOrderTraversal() {
cout << "后序遍历: ";
postOrder(root);
cout << endl;
}
void levelOrderTraversal() {
if (!root) return;
cout << "层序遍历: ";
queue<treeNode*> q;
q.push(root);
while (!q.empty()) {
treeNode* current = q.front();
q.pop();
cout << current->val << " ";
if (current->left) q.push(current->left);
if (current->right) q.push(current->right);
}
cout << endl;
}
};
int main()
{
BinaryTree tree;
// 插入节点
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(2);
tree.insert(4);
tree.insert(6);
tree.insert(8);
// 遍历测试
tree.preOrderTraversal(); // 5 3 2 4 7 6 8
tree.inOrderTraversal(); // 2 3 4 5 6 7 8
tree.postOrderTraversal(); // 2 4 3 6 8 7 5
tree.levelOrderTraversal(); // 5 3 7 2 4 6 8
return 0;
}
四、二叉树的操作
二叉树的操作可分为遍历与线索化
1、遍历
对线性表进行遍历：沿着某条搜索路径，对表中的数据进行遍历且仅遍历一遍（for/while）
二叉树的遍历类似，但不同于线性表的搜索路径唯一，二叉树的搜索路径并不唯一
具体的遍历操作可参考算法通关的 017 和 018
2、根据遍历结构重构二叉树
五、二叉树的线索化
1、引入：
一个二叉链表中存储了具有 n 个节点的二叉树，那这个二叉树就具有 2n 个指针域，其中有 n+1（2n-(n-1)）（总指针域减去已经有节点的指针域）个节点为空（null），这样就会造成空间的浪费
想要找到一个中序遍历的元素的前驱是谁，可以将它遍历一遍，它的前一个就是，这样太慢，假如我们可以再元素中记住它的前驱和后继，这样更加直接，结合上一条，我们是不是可以将那些 null 指针利用起来呢，让它指向前驱或后继
bdcaegfh
但有一些节点他的左右都不为空（n-1）还是保存的孩子
所以我们将 null 指针改为指向他的前驱和后继称为二叉树的线索化
两个问题：
①、我们如何确定一个指针它指向孩子，还是前驱/后继？
在节点结构体中加入标记变量：lflag、rflag（lflag==1，指向前驱，lflag==0，指向左孩子）
②、如果一个节点有左孩子，那么该如何寻找它的前驱？
根据不同的排序特点
2、代码
// c++_datastructure_010.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
using namespace std;
// 定义指针类型标记：CHILD表示指向子节点，THREAD表示线索（指向前驱/后继）
enum PointerTag {CHILD,THREAD};
// 线索二叉树节点结构
struct ThreadNode
{
int data;// 节点存储的数据
ThreadNode* left;// 左指针（可能指向左子节点或前驱节点）
ThreadNode* right; // 右指针（可能指向右子节点或后继节点）
PointerTag leftTag; // 左指针类型标记（CHILD或THREAD）
PointerTag rightTag;// 右指针类型标记（CHILD或THREAD）
// 构造函数初始化节点
ThreadNode(int val):data(val), left(nullptr), right(nullptr),
leftTag(CHILD), rightTag(CHILD) {
}
};
class ThreadedBinaryTree
{
private:
ThreadNode* root;//树的根节点
ThreadNode* pre;//记录前驱节点
// 核心函数：递归实现中序线索化
void inThreading(ThreadNode* curr)
{
if (curr == nullptr) return;//递归的终止条件
// 1. 递归线索化左子树
inThreading(curr->left);//来到最左节点
// ==== 处理当前节点curr的左指针 ====
// 如果当前节点的左子节点为空
if (curr->left == nullptr)
{
curr->left = pre;// 左指针指向前驱节点pre
curr->leftTag = THREAD;// 标记为线索
}else{
curr->leftTag = CHILD;// 否则标记为子节点（虽然可能已默认，但显式设置更安全）
}
// ==== 处理前驱节点pre的右指针 ====
if (pre != nullptr && pre->right != nullptr)
{
pre->right = curr; // 前驱的右指针指向当前节点（即pre的后继是curr）
pre->rightTag = THREAD; // 标记为线索
}
pre = curr;// 关键步骤：更新前驱节点为当前节点，供后续递归使用
// 3. 递归线索化右子树
inThreading(curr->right);
}
public:
// 构造函数初始化空树
ThreadedBinaryTree() :root(nullptr), pre(nullptr) {}
// 构建示例二叉树（硬编码结构方便测试）
void buildSampleTree() {
root = new ThreadNode(1); // 1
root->left = new ThreadNode(2); // / \
root->right = new ThreadNode(3); // 2 3
root->left->left = new ThreadNode(4); // / \
root->left->right = new ThreadNode(5); // 4 5
}
// 中序线索化入口函数
void createInThread()
{
pre = nullptr; // 初始化前驱节点
if (root != nullptr)
inThreading(root); // 从根节点开始递归线索化
// 处理最后一个节点（中序遍历的最后一个节点右指针为空）
if (pre != nullptr) {
pre->right = nullptr; // 明确最后一个节点的右线索为nullptr
pre->rightTag = THREAD; // 标记为线索（虽然可能已经设置，但确保正确）
}
}
// 非递归中序遍历线索二叉树（无需栈，空间O(1)）
void inOrderTraverse()
{
ThreadNode* cur = root;// 从根节点开始遍历
while (cur != nullptr)
{
// 步骤1：找到最左节点（根据CHILD标记深入左子树）
while (cur->leftTag == CHILD)
{
cur = cur->left;
}
cout << cur->data << " "; // 访问最左节点
// 步骤2：沿右线索访问后继节点
while (cur->rightTag == THREAD)
{
cur = cur->right;
cout << cur->data << " ";// 根据线索直接跳转到后继
}
// 步骤3：当遇到非线索右指针时，转向右子树（可能是一个真实子节点）
cur = cur->right;
}
}
};
int main()
{ ThreadedBinaryTree tree;
tree.buildSampleTree(); // 构建示例树：1为根，2、3为左右子节点，4、5为2的左右子节点
tree.createInThread(); // 执行中序线索化
cout << "中序遍历结果: ";
tree.inOrderTraverse(); // 应输出: 4 2 5 1 3
return 0;
}
·
关键代码：
1、核心函数：递归实现中序线索化
// 核心函数：递归实现中序线索化
void inThreading(ThreadNode* curr)
{
if (curr == nullptr) return;//递归的终止条件
// 1. 递归线索化左子树
inThreading(curr->left);//来到最左节点
// ==== 处理当前节点curr的左指针 ====
// 如果当前节点的左子节点为空
if (curr->left == nullptr)
{
curr->left = pre;// 左指针指向前驱节点pre
curr->leftTag = THREAD;// 标记为线索
}else{
curr->leftTag = CHILD;// 否则标记为子节点（虽然可能已默认，但显式设置更安全）
}
// ==== 处理前驱节点pre的右指针 ====
if (pre != nullptr && pre->right != nullptr)
{
pre->right = curr; // 前驱的右指针指向当前节点（即pre的后继是curr）
pre->rightTag = THREAD; // 标记为线索
}
pre = curr;// 关键步骤：更新前驱节点为当前节点，供后续递归使用
// 3. 递归线索化右子树
inThreading(curr->right);
}
这里类似于中序遍历的递归实现，不过多了节点的线索化：其中 pre 指针在正常遍历输出时进行更新，而关于处理 pre 指针当 pre 指针为 null 时说明上一个节点应该线索化即此时的节点为上一个节点的后继节点
2、非递归中序遍历线索二叉树（无需栈，空间 O(1)）
// 非递归中序遍历线索二叉树（无需栈，空间O(1)）
void inOrderTraverse()
{
ThreadNode* cur = root;// 从根节点开始遍历
while (cur != nullptr)
{
// 步骤1：找到最左节点（根据CHILD标记深入左子树）
while (cur->leftTag == CHILD)
{
cur = cur->left;
}
cout << cur->data << " "; // 访问最左节点
// 步骤2：沿右线索访问后继节点
while (cur->rightTag == THREAD)
{
cur = cur->right;
cout << cur->data << " ";// 根据线索直接跳转到后继
}
// 步骤3：当遇到非线索右指针时，转向右子树（可能是一个真实子节点）
cur = cur->right;
}
}
当非递归遍历一个函数时，先来到最左节点，将他输出然后根据这个节点的后继不断进行输出，若没有后继说明可能来到中节点接下来进入到右子树，不断重复进行输出直到整个树结束
六、二叉排序树（BST）
为了方便数据查找，可以利用树形结构
常见的
1、概念
可以看出中序遍历有序：左 中 右、
2、操作
查找：（类似于二分查找）查找数据 x 与根节点比较，若大于进左树查找，若大于进右树查找
插入：
3、代码
// c++_datastructure_011.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
using namespace std;
struct Node
{
int data;
Node* left;
Node* right;
Node(int val) :data(val), left(nullptr), right(nullptr) {}
};
class BST
{
private:
Node* root;// 根节点指针
// 递归销毁子树（用于析构函数）
void destroyTree(Node* node)
{
if (node)
{
destroyTree(node->left); // 先销毁左子树
destroyTree(node->right); // 再销毁右子树
delete(node); // 最后删除当前节点
}
}
// 递归插入节点（返回插入后的子树根节点）
Node* insert(Node*& node, int value)
{
if (node == nullptr)
{
node = new Node(value); // 找到插入位置，创建新节点
}
else if(value > node->data)
{ // 值大于当前节点，往右子树插入
node->right=insert(node->right, value);
}else if(value < node->data)
{
// 值小于当前节点，往左子树插入
node->left=insert(node->left, value);
}
// 如果值已存在，不做任何操作
return node;
}
// 查找子树中的最小值节点（用于删除操作）
Node* findMin(Node* node)
{
// 二叉搜索树的最小值在最左子节点
while (node->left != nullptr)
{
node = node->left;
}
return node;
}
// 递归删除节点（返回删除后的子树根节点）
Node* remove(Node* node, int value)
{
if (node == nullptr) return nullptr; // 空树直接返回
// 1. 查找目标节点
if (value < node->data)
{
node->left = remove(node->left, value);// 往左子树查找
}else if (value > node->data)
{
node->right = remove(node->right, value);// 往右子树查找
} else//value == node->data
{
// 2. 找到目标节点后进行删除操作
// 情况1：只有一个子节点或没有子节点
if (node->left == nullptr)
{
// 只有右子节点，用右子节点替代当前节
Node* tem = node->right;
delete(node);
return tem;
}else if (node->right == nullptr)
{
// 只有左子节点，用右子节点替代当前节
Node* tem = node->left;
delete(node);
return tem;
}
// 情况2：有两个子节点
// 找到右子树的最小节点（或左子树的最大节点）
Node* tem = findMin(node->right);
// 用最小值覆盖当前节点值
node->data = tem->data;
// 删除右子树中的那个最小值节点
node->right = remove(node->right, tem->data);
}
return node;
}
// 递归查找节点
bool search(Node* node, int value) const
{
if (node == nullptr) return false;
if (node->data == value)return true;
/*if (node->data > value)
{
search(node->left, value);
}
else if (node->data < value)
{
search(node->right, value);
}*/
// 根据值大小决定搜索方向
return value < node->data ?
search(node->left, value) :
search(node->right, value);
}
// 递归中序遍历（左-根-右）
void inOrder(Node* node) const
{
if (node == nullptr) return;
inOrder(node->left);
cout << node->data << " ";
inOrder(node->right);
}
public:
BST() :root(nullptr) {}// 构造函数初始化空树
~BST() { destroyTree(root); } // 析构时释放所有内存
// 插入对外接口
void insert(int value) { root = insert(root, value); }
// 删除对外接口
void remove(int value) { root = remove(root, value); }
// 查找对外接口
bool contains(int value) const { return search(root, value); }
// 中序遍历打印接口
void printInOrder() const {
inOrder(root);
cout << endl;
}
};
int main()
{
BST bst;
// 测试插入操作
int values[] = { 5, 3, 7, 2, 4, 6, 8 };
for (int val : values) {
bst.insert(val);
}
cout << "中序遍历结果: ";
bst.printInOrder(); // 输出: 2 3 4 5 6 7 8
// 测试删除叶子节点（7的子节点8会保留）
bst.remove(7);
cout << "删除7后的中序遍历: ";
bst.printInOrder(); // 输出: 2 3 4 5 6 8
// 测试查找功能
cout << "是否存在6? " << (bst.contains(6) ? "是" : "否") << endl; // 是
cout << "是否存在7? " << (bst.contains(7) ? "是" : "否") << endl; // 否
return 0;
}
七、二叉平衡树（AVL）
1、概念
BST 是有缺点的：当数据（n）本身就是有序的时候，建立的 BST 就是一颗斜树数的高度为 n，起不到加快查找的作用
为此我们引入平衡因子：，每一个节点都有平衡因子，一个节点的平衡因子就是左右子树的高度差（满二叉树平衡因子为 0）
进行一个规定：在 BST 基础上增加限制，要求每个节点的平衡因子绝对值不超过 1（为了接近成为一个完全二叉树）----->(AVL 树)
AVL 一定是 BST，但 BST 不一定是 AVL
AVL 树中序遍历也是有序的
2、操作
查找：
与 BST 是一样的
当树的高度大于二的时候可能出现失衡
可以利用旋转（左旋/右旋）来解决失衡问题：
在旋转过程中，节点个数没有发生改变，发生改变的是父子关系
当有多个节点失衡时呢？
优先调整最小失衡子树，调整以 x 为根的子树，x 是距离插入节点最近的平衡节点
插入操作：
1、执行 BST 的插入操作
2、当下层递归调用结束返回本层时，算一下本层递归的根节点的平衡因子，判断有无失衡，如果失衡，对本层失衡的子树进行选择操作调整
选转操作：
判断树的高度差
分别求左孩子与右孩子节点的高度做差
一个节点的高度=左右孩子最高节点长度 +1； x->h=max( x->left->h,x->right->h)+1;
不同情况插入：
① （l l）在节点 x 的左孩子的左子树中插入一个节点，导致 x 成为最小失衡子树的根节点，此时只需要将 x 节点进行右旋即可
② (l r)在节点 x 的左孩子的右子树中插入一个节点时，不能直接右旋
我们可以先将 x 节点的左子树进行左旋-》就变成了 ① 的情况，然后进行右旋即可
其他两种情况类似：
删除操作：
① 先执行二叉排序树 BST 的删除操作，先在保证顺序的前提下把节点删掉
② 考虑失衡
当删除后子树的平衡因子为 0 时应该进行右旋而不是左旋
代码：
// C++_datastructure_012.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
using namespace std;
struct Node
{
int key;
Node* left;
Node* right;
int height; // 节点高度（从该节点到最远叶子的边数）
Node(int k) :key(k), left(nullptr), right(nullptr), height() {}
};
class AVLTree
{
private:
Node* root;
// 获取节点高度（处理空指针情况）
int height(Node*node)
{
return node ? node->height : 0;
}
// 计算节点的平衡因子（左子树高度 - 右子树高度）
int getBalance(Node* node)
{
return node ? height(node->left) - height(node->right) : 0;
}
/* 右旋转操作（处理左左不平衡情况）
y x
/ \ 右旋 / \
x T4 ===> z y
/ \ / \ / \
z T3 T1 T2 T3 T4
/ \
T1 T2
*/
Node* rightRotate(Node* y)
{
Node* x = y->left;// 暂存左子节点x
Node* T2 = x->right; // 保存x的右子树
x->right = y; // y成为x的右子节点
y->left = T2; // T2成为y的左子树
// 更新高度（先更新下层节点y的高度）
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x;
}
/* 左旋转操作（处理右右不平衡情况）
x y
/ \ 左旋 / \
T1 y ===> x z
/ \ / \ / \
T2 z T1 T2 T3 T4
/ \
T3 T4
*/
Node* leftRotate(Node* x)
{
Node* y = x->right;// 暂存左子节点x
Node* T2 = y->left; // 保存x的右子树
y->left = x; // y成为x的右子节点
x->right = T2; // T2成为y的左子树
// 更新高度（先更新下层节点y的高度）
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y;
}
// 递归插入节点（返回新的根节点）
Node* insert(Node* node, int key)
{
// 递归终止条件：找到空位置创建新节点
if (!node) return new Node(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node;// 不允许重复值，直接返回
// 更新当前节点高度（取左右子树高度的最大值+1）
node->height = 1 + max(height(node->left),height(node->right));
// 获取当前节点的平衡因子
int balance = getBalance(node);
// 平衡调整（四种不平衡情况判断）
// 左左情况：需要右旋
if (balance > 1 && key < node->left->key)
{
return rightRotate(node);
}
// 右右情况：需要左旋
if (balance < -1 && key > node->right->key)
{
return leftRotate(node);
}
// 左右情况：先左旋左子树，再右旋当前节点
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}// 右左情况：先右旋右子树，再左旋当前节点
if (balance <-1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
// 如果已经平衡，直接返回当前节点
return node;
}
// 查找子树中的最小节点（用于删除操作）
Node* minValueNode(Node* node) {
Node* current = node;
while (current && current->left)
current = current->left;
return current;
}
// 递归删除节点（返回新的根节点）
Node* deleteNode(Node* root, int key)
{
// 递归终止条件：未找到要删除的节点
if (!root) return root;
// 递归查找要删除的节点
if (key < root->key)
{
root->left = deleteNode(root->left, key);
}
else if (key > root->key)
{
root->right = deleteNode(root->right, key);
}
else
{
// 找到要删除的节点，处理三种情况：
// 情况1/2：只有一个子节点或无子节点
if (!root->left || !root->right)
{
Node* temp = root->left ? root->left : root->right;
if (!temp)// 无子节点
{
temp = root;
root = nullptr;
}
else
{
*root = *temp;
}
delete temp;
}
else {
// 情况3：有两个子节点
// 找到右子树的最小节点作为后继节点
Node* temp = minValueNode(root->right);
root->key = temp->key; // 用后继节点的值替换当前节点值
root->right = deleteNode(root->right, temp->key); // 递归删除右子树中的后继节点
}
}
//删除之后开始调整平衡
if (!root) return root;
// 更新当前节点高度
// 更新当前节点高度（取左右子树高度的最大值+1）
root->height = 1 + max(height(root->left), height(root->right));
// 获取当前节点的平衡因子
int balance = getBalance(root);
// 平衡调整（四种不平衡情况判断）
// 左左情况：需要右旋
if (balance > 1 && getBalance(root->left) >= 0)
{
return rightRotate(root);
}
// 右右情况：需要左旋
if (balance < -1 && getBalance(root->right) <= 0)
{
return leftRotate(root);
}
// 左右情况：先左旋左子树，再右旋当前节点
if (balance > 1 && getBalance(root->left) < 0)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}// 右左情况：先右旋右子树，再左旋当前节点
if (balance < -1 && getBalance(root->right)>0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}
// 如果已经平衡，直接返回当前节点
return root;
}
// 中序遍历辅助函数（按顺序打印节点值）
void inOrder(Node * node) {
if (node) {
inOrder(node->left);
cout << node->key << " ";
inOrder(node->right);
}
}
public:
AVLTree() : root(nullptr) {}
// 公开插入接口
void insert(int key) {
root = insert(root, key);
}
// 公开删除接口
void remove(int key) {
root = deleteNode(root, key);
}
// 打印整棵树（中序遍历）
void print() {
inOrder(root);
cout << endl;
}
};
int main() {
AVLTree tree;
// 测试插入操作
tree.insert(10);
tree.insert(20);
tree.insert(30); // 此处会触发平衡调整
tree.insert(40);
tree.insert(50);
tree.insert(25);
cout << "中序遍历: ";
tree.print(); // 输出: 10 20 25 30 40 50
// 测试删除操作
tree.remove(30); // 删除后需要重新平衡
cout << "删除30后: ";
tree.print();
return 0;
}
注意：获取树高度时要用 height 函数不能直接 root->height 因为 root 可能为空的
AVL logn
适用于没有大量插入/删除操作的查找
八、并查集（树的应用）
假设我们有一些数据集合（不相交），对于这些集合我们有两个操作：
1、给出两个数据 x，y 把 x 所在数据集合与 y 所在数据集合进行合并
2、给出两个数据 x，y 查找这两个数据是否在同一集合
我们会给出若干个操作进行实现
首先我们如何存储一个集合呢？（方便合并与查找）
普通的树形结构就可以（双亲表示法）
合并：直接让一棵树的根节点做另一颗树节点孩子（为了避免形成斜树，让高的做矮的父节点）
询问：两个数据在不在同一颗树中，分别找到两棵树的根节点，看是否相同
优化（路径压缩）：就是在每次查找时，令查找路径上的每个节点都直接指向根节点。
代码：
//并查集
#include <iostream>
#include <vector>
using namespace std;
/**
* 基于树的双亲表示法实现的并查集
* 每个节点直接记录其父节点，形成树状结构
* 根节点的父节点指向自己
*/
class UnionFind
{
private:
vector<int> parent;// 父节点数组：parent[i]表示i节点的父节点索引
vector<int> rank;// 秩数组：rank[i]表示以i为根的树的高度（初始为0）
public:
/**
* 构造函数：初始化并查集
* @param n 元素数量（元素编号从0到n-1）
*/
UnionFind(int n)
{
parent.resize(n);
rank.resize(n,0); // 初始高度都为0
// 初始化时每个元素自成一棵树，父节点指向自己
for (int i = 0; i < n; ++i)
{
parent[i] = i;
}
}
/**
* 查找操作（带路径压缩优化）
* 从指定节点x递归查找其根节点
* 查找过程中会将路径上的所有节点直接连接到根节点，压缩树的高度
* @param x 目标节点
* @return 根节点索引
*/
int find(int x)
{
if (parent[x] != x)
{
parent[x] = find(parent[x]);//实现路径压缩 每次查找时，令查找路径上的每个节点都直接指向根节点。
}
return parent[x];
}
/**
* 合并操作（按秩合并优化）
* 将两个节点所在的树合并为1棵
* @param x 第一个节点
* @param y 第二个节点
*/
void unionSet(int x, int y)
{
int root_x = find(x);
int root_y = find(y);
if (root_x == root_y)
return;
if (rank[root_x] > rank[root_y])
{
parent[root_y] = root_x;
rank[root_x] = max(rank[root_x], rank[root_y] + 1);
}
else
{
parent[root_x] = root_y;
rank[root_y] = max(rank[root_y], rank[root_x] + 1);
}
}
bool isConnected(int x, int y) {
return find(x) == find(y);
}
void debugPrint() {
cout << "索引: ";
for (int i = 0; i < parent.size(); ++i) cout << i << " ";
cout << "\n父节点: ";
for (int val : parent) cout << val << " ";
cout << "\n秩 : ";
for (int val : rank) cout << val << " ";
cout << "\n" << endl;
}
};
int main()
{
UnionFind uf(5);
// 初始状态调试输出
cout << "初始结构：" << endl;
uf.debugPrint();
// 合并操作演示
cout << "合并0和1后：" << endl;
uf.unionSet(0, 1);
uf.debugPrint();
cout << "合并2和3后：" << endl;
uf.unionSet(2, 3);
uf.debugPrint();
// 连通性检测
cout << boolalpha;
cout << "0和1是否连通: " << uf.isConnected(0, 1) << endl; // true
cout << "2和3是否连通: " << uf.isConnected(2, 3) << endl; // true
cout << "1和2初始是否连通: " << uf.isConnected(1, 2) << endl; // false
// 跨树合并
cout << "\n合并1和2后：" << endl;
uf.unionSet(1, 2);
uf.debugPrint();
cout << "合并后检测：" << endl;
cout << "1和2是否连通: " << uf.isConnected(1, 2) << endl; // true
cout << "0和3是否连通: " << uf.isConnected(0, 3) << endl; // true
return 0;
}
高度判断还可以优化，效果一样就不必每次判断了，只在高度相同时判断
// 修正合并逻辑
void unionSet(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
// 按秩合并修正
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootX] = rootY;
if (rank[rootX] == rank[rootY]) {
rank[rootY]++; // 仅当秩相等时增加秩
}
}
}
九、哈夫曼树（树的应用）
1、前导概念
节点的路径长度
树的路径长度
就是树的每个叶⼦结点的路径⻓度之和
节点的带权路径长度
树的带权路径长度（WPL）
2、哈夫曼树
有 n 个带权值的节点，要使用 n 个节点构造一棵二叉树，要求如下：
① 这 n 节点只能做叶子节点，而且叶子节点也只能是这 n 个节点（相当于将 n 个树合并成一颗二叉树，每合并一次少一棵树，最终合并为 1 颗树需要合并 n-1 次）即需要增加 n-1 个非叶子节点
② 合并时，每次把两棵树合并成一棵树，让两棵树的根节点做兄弟给他们添加一个新的父亲节点（）也就说新树的根节点
共有 2n-1 个节点（n-1（新节点）+n（带权值的节点））
③ 父亲节点的权值是其左右节点的权值之和
因为合并的顺序不同（权值）导致形成的树不同，因此我们需要构成 WPL 最小的树，那它一个如何构造呢？
WPL==n 个叶子节点的带权路径之和==W1*L1+W2*L2+W3*L3+...Wn*Ln
Wi 固定不能发生变化，因此可以从 L 路径长度入手（1<=L<=n-1(最多增加 n-1 个节点)）
为了使得 WPL 尽量小：
大权值->短路径->离根节点近
小权值->长路径->离根节点远
最先合并的离的较远，后合并的离的较近
因此优先合并根节点权值小的两棵树
由此得出了哈夫曼树
注：① 合并出来的 WPL 最小二叉树并不唯一，因为合并两颗二叉树时左右都可以，如果权值为
X 的节点有若干个，那么选谁都可以
② wpl 最小的二叉树 wpl 值唯一吗？---唯一的（最小）
3、哈夫曼树的应用（WPL 最小）
对数据进行压缩编码
前缀属性：短编码不能是长编码的前缀
因此变长编码更好
可以利用哈夫曼树进行编码：叶子节点就是要编码的字符，WPL 就是编码消息长度（字符出现的次数*字符的编码长度）
4、哈夫曼编码的代码实现
需求：给出 n 个字符（n<=100）并且给出每个字符在消息中出现的频率（次数）（权重），对着 n 个字符进行哈夫曼编码
#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
//哈夫曼编码的代码实现
struct HuffmanNode
{
int weight;//权值
int fa;//父亲节点的下标
int l, r;//左右孩子的下标
};
void find(HuffmanNode* tree, int x, int& s1, int& s2)//找到权值最小的两个节点
{
int minn = 0;
for (int i = 0; i <=x; i++)
{
if (tree[i].fa == -1)
{
minn = i;
break;
}
}
for (int i = 0; i <= x; i++)
{
if (tree[i].fa == -1 && tree[i].weight < tree[minn].weight)
{
minn = i;
}
}
s1 = minn;
minn = 0;
for (int i = 0; i <= x; i++)
{
if (tree[i].fa == -1&&i!=s1)
{
minn = i;
break;
}
}
for (int i = 0; i <= x; i++)
{
if (tree[i].fa == -1 && i != s1 && tree[i].weight < tree[minn].weight)
{
minn = i;
}
}
s2=minn;
}
HuffmanNode* CreatHuffmanTree(int w[], int n)
{
int m = 2 * n - 1;
HuffmanNode * tree = new HuffmanNode[m];
for (int i = 0; i < n; i++)//先将前n个节点放入树中
{
tree[i].weight = w[i];
tree[i].fa = -1;
tree[i].l = -1;
tree[i].r = -1;
}
int s1, s2;
for (int i = n; i < m; i++)
{
find(tree, i - 1, s1, s2);
tree[i].fa = -1;
tree[i].weight = tree[s1].weight + tree[s2].weight;
tree[i].l = s1;
tree[i].r = s2;
tree[s1].fa = tree[s2].fa = i;
}
return tree;
}
char** Creatcode(HuffmanNode* tree, int n)
{
char* temp = new char[n];
char** codes = new char* [n];
memset(codes, 0, sizeof(char*) * n);
for (int i = 0; i < n;i++)
{
int start = n - 1;
temp[start] = '\0';
int p = i;//当前
int pos = tree[p].fa;
while (pos != -1)
{
--start;
if (p == tree[pos].l)
{
temp[start] = '0';
}
else {
temp[start] = '1';
}
p = pos;
pos = tree[p].fa;
}
codes[i] = new char[n - start];
strcpy_s(codes[i], n - start, &temp[start]);
}
delete[] temp;
return codes;
}
int main()
{
int n;
char a[105];
int w[105];
cin >> n;
cin.ignore(); // 清除输入缓冲区
for (int i = 0; i < n; i++)
{
cin.get(a[i]);
}
for (int i = 0; i < n; i++)
{
cin >> w[i];
}
HuffmanNode* tree = CreatHuffmanTree(w, n);
char* *codes= Creatcode(tree, n);
for (int i = 0; i < n; i++)
{
cout << a[i] << ":" << codes[i] << endl;
delete[]codes[i];
}
delete[]tree;
delete[]codes;
return 0;
}
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于