C++二叉树
C++ 二叉树
二叉树由许多节点组成。每个节点都包含⼀个项和两个指向其他节点（⼦节点）的指针。子节点分为左节点和右节点。[具体视下方图表]
graph TD
A{"二叉树"} --> B["父节点<br>（root）"]
B-->| 条件1 | C["子节点<br>（上一节点的左节点）<br>（下一节点的父节点）"]
B -->| 条件2 | D["子节点<br>（上一节点的左节点）<br>（下一节点的父节点）"]
C -->| 条件1 | E["子节点"]
C -->| 条件2 | F["子节点"]
D -->| 条件1 | G["子节点"]
D -->| 条件2 | H["子节点"]
实例一（1）：二叉树主体
class Node //定义节点类
{
public:
//定义变量
int Key; //节点位变量
int Value; //节点内数据变量
Node* Left; //左节点
Node* Right; //右节点
//初始化数据
public:
Node(int key, int value)
{
Key = key;
Value = value;
Left = nullptr;
Right = nullptr;
}
};
class Tree //定义节点类
{
public:
Node* Head = nullptr; //root节点
public:
//函数--添加新节点
Void Add(int key, int value) //命名Add（节点位,节点内数据值）
{
Node* newNode = new Node(key, value); //分配内存建立新节点
if (Head == nullptr) //当root节点为空时(代表树未开始)
{
Head = newNode; //直接使root为新节点
return; //返回
}
AddNode(Head, newNode); //当root有数据，进入AddNode中进行添加
}
//函数--添加新节点(非开头)
void AddNode(Node* target, Node* newNode) //命名AddNode(当前节点(父节点),新节点)
{
if (newNode->Key < target->Key) //当新节点位的值小于当前父节点
{
if (target->Left == nullptr) //当子节点的左节点为空时
{
target->Left = newNode; //将新节点赋予子节点左节点
return; //返回
}
AddNode(target->Left, newNode); //当左节点不是空，再次进入AddNode（左节点，新节点）中进行添加判断
}
else
{
if (target->Right == nullptr) //当子节点的右节点为空时
{
target->Right = newNode; //将新节点赋予子节点右节点
return; //返回
}
AddNode(target->Right, newNode); //当右节点不是空，再次进入AddNode（右节点，新节点）中进行添加判断
}
}
//函数--获取第key位数据
int Get(int key)
{
Node* node = GetNode(key, Head); //进入GetNode获取key位节点
return node == nullptr ? 0 : node ->Value;
//三元运算符--逻辑分解
//return --->返回
//node == nullptr --->条件判断
//? 0 --->根据上面的条件判断，如果node是空指针，则返回0
//: node->Value --->如果不是空指针，返回节点内的Value数据
//此行代码可以完全等价于
/*
if (node == nullptr)
{
return 0;
}
else
{
return node->Value;
}
*/
}
//函数--获取key位节点
Node* GetNode(int key,Node* target) //命名GetNode(需求的key位,当前节点(父节点))
{
if (target == nullptr) //如果为空，树不含内容
{
return nullptr; //返回空
}
if (key == target->Key) //如果当前节点Key值与key相等
{
return target; //输出当前节点
}
if (key < target->Key) //当key值小于当前节点Key，说明需要进入左节点继续判断
{
return GetNode(key, target->Left); //返回来自GetNode(左节点判断)的值
}
else
{
return GetNode(key, target->Right); //返回来自GetNode(右节点判断)的值
}
}
//函数--获取最小值
Node* FindMin(Node* node) //定义FindeMin(当前节点) （第一次应该从root的右节点开始判断）
{
while (node->Left != nullptr) //当当前节点的左节点不为空时(说明还有更小值)
{
node = node->Left; //使得node变为当前节点的左节点
}
return node;
}
//函数--非root节点移除第key位 （此段可结合文末图表思考）
Node* Remove(Node* target, int key) //定义Remove(当前节点，需要删的key位)
{
if (target == nullptr) return nullptr; //如果当前值为空，返回空（说明key位不存在）
if (key < target->Key) //当目标key小于当前节点位（说明在此左侧）
{
target->Left = Remove(target->Left, key);
//代入Remove继续判断
}
else if (key > target-> Key) //当目标key大于当前节点位（说明在此右侧）
{
target->Right = Remove(target->Right, key);
//代入Remove继续判断
}
else //当key与当前节点Key相等
{
if (target->Left == nullptr && target->Right == nullptr)
//当当前节点左右节点都为空，则为末尾
{
delete target; //直接删除
return nullptr; //返回空
}
else if (target->Left == nullptr) //当左节点为空，说明只有右节点
{
Node* temp = target->Right; //新建节点用于替换当前节点
delete target; //删除目标
return temp; //如果位root返回到外部，否则返回到上一层函数
}
else if (target->Right == nullptr) //当右节点为空，说明只有左节点
{
Node* temp = target->Left; //新建节点用于替换当前节点
delete target; //删除目标
return temp; //如果位root返回到外部，否则返回到上一层函数
}
else //当左右都有节点
{
Node* minNode = FindMin(target->Right);
//找到右节点的最小左节点
target->Key = minNode->Key; //使当前节点位改为最小左节点值
target->Value = minNode->Value; //使当前节点位改为最小左节点数
target->Right = Remove(target->Right,minNode->Key);
//再代入右节点进行对最小节点的删除
}
}
return target; //返回给root节点
}
//函数--移除第key位
void RemoveKey(int key) //定义RemoveKey（要删除的第key位）
{
if (Head == nullptr) return; //如果树不存在直接停止
Head = Remove(Head, key); //从Head开始排查到key位移除
}
};
实例一（2）：使用二叉树
int main()
{
Tree tree; //定义tree
tree.Add(100, 123); //加入位数
tree.Add(101, 987); //加入位数
std::cout << tree.Get(101); //获取101位数值
tree.Remove(tree.Head, 100); //移除100位
}
实例：示意图
graph TD
A{"二叉树"} --> B["100"]
B -->| 小于 | C["88"]
B -->| 大于 | D["108"]
C -->| 小于 | E["78"]
C -->| 大于 | F["98"]
D -->| 小于 | G["106"]
D -->| 大于 | H["128"]
E -->| 小于 | I["68"]
E -->| 大于 | J["80"]
F -->| 小于 | K["92"]
F -->| 大于 | L["99"]
G -->| 小于 | M["102"]
G -->| 大于 | N["107"]
H -->| 小于 | O["118"]
H -->| 大于 | P["148"]
C++二叉树
https://chooseqiu.com/posts/207c2e3f/