当前位置： 首页 > news >正文

数据结构 - C/C++ - 树

news 2025/7/5 10:07:10
  • 公开视频 -> 链接点击跳转公开课程
  • 博客首页 -> 链接点击跳转博客主页

目录

树的概念

结构特性

树的样式

树的存储

树的遍历

节点增删

二叉搜索树

平衡二叉树

树的概念

  • 二叉树是树形结构，是一种非线性结构。

    • 非线性结构：在二叉树中，数据项的排列不是简单的线性序列，而是通过节点间的链接构成复杂的层次结构。

    • 受限节点数目：每个节点最多有两个子节点，这限定了树的分支宽度。

  • 节点(Node)

    • 数据域：保存或显示与节点相关联的信息。

    • 左子节点指针：指向左侧子节点的链接。

    • 右子节点指针：指向右侧子节点的链接。

  • 根节点(Root)

    • 节点是树结构的最顶端节点，它没有父节点，并且是二叉树结构的起点。

  • 父节点(Parent)

    • 与子节点相关联的上一级节点。

  • 子节点(Child)

    • 父节点指向的左子节点或者右子节点。

  • 叶子节点(Leaf)

    • 叶子节点是指没有任何子节点的节点。在树的结构中，叶子节点总是位于最底层。

  • 兄弟节点(Brother)

    • 在二叉树中，共享同一父节点的两个节点称为兄弟节点。

  • 节点的度

    • 节点分支数。

    • 度为0：节点没有子节点，即叶子节点。

    • 度为1：节点有一个子节点。

    • 度为2：节点有两个子节点。

  • 结点层度：根节点的层次为1，以此递增。

  • 树的深度：树种节点层次的最大值。

结构特性

  • 二叉树中第I层中最多存在2^(I - 1)的节点数量。

  • 二叉树中深度为I时最多存在2^I - 1的节点总数。

树的样式

  • 二叉树

  • 完美二叉树

    • 完美二叉树中，除了叶子节点外其余所有节点的度都有2。

    • 完美二叉树中，深度为I时节点数量为2^I - 1。

树的存储

  • 顺序存储

    • 基于数组 - 内存中使用连续的内存空间

    • 假设根节点编号为x

      • 左子节点编号为2 * x

      • 右子节点编号为2 * x + 1

  • 链式存储

    • 基于链表 - ListNode

树的遍历

  • 先序遍历 DLR 根节点 左子树 右子树

  • 中序遍历 LDR 左子树 根节点 右子树

  • 后序遍历 LRD 左子树 右子树 根节点

    • 示例代码

    #include <iostream>class TreeNode
{
public:char ch;TreeNode* Left;TreeNode* Righ;TreeNode(char value) : ch(value), Left(nullptr), Righ(nullptr) {}
};void PreorderTraverse(TreeNode* T)
{if (T == NULL) return;printf("%c ", T->ch);PreorderTraverse(T->Left);PreorderTraverse(T->Righ);
}void InOrderTraverse(TreeNode* T)
{if (T == NULL) return;InOrderTraverse(T->Left);printf("%c ", T->ch);InOrderTraverse(T->Righ);
}void PostOrderTraverse(TreeNode* T)
{if (T == NULL) return;PostOrderTraverse(T->Left);PostOrderTraverse(T->Righ);printf("%c ", T->ch);
}int main()
{//二叉树节点
#if 1TreeNode* NodeA = new TreeNode('A');TreeNode* NodeB = new TreeNode('B');TreeNode* NodeC = new TreeNode('C');TreeNode* NodeD = new TreeNode('D');TreeNode* NodeE = new TreeNode('E');TreeNode* NodeF = new TreeNode('F');TreeNode* NodeG = new TreeNode('G');TreeNode* NodeH = new TreeNode('H');TreeNode* NodeI = new TreeNode('I');
#endif//二叉树图解/*A/ \B   C/   / \D   E   F/ \   \G   H   I*///二叉树关联
#if 1NodeA->Left = NodeB;NodeB->Left = NodeD;NodeD->Left = NodeG;NodeD->Righ = NodeH;NodeA->Righ = NodeC;NodeC->Left = NodeE;NodeE->Righ = NodeI;NodeC->Righ = NodeF;
#endif//二叉树遍历
#if 1PreorderTraverse(NodeA);InOrderTraverse(NodeA);PostOrderTraverse(NodeA);
#endifreturn 0;
}

节点增删

  • 假如删除节点为叶子节点，直接删除节点并修正父节点对应指向为NULL。

  • 假如删除节点存在一个子节点，子节点替换被删除节点位置，并对应指向。

  • 假如删除节点存在两个子节点。

    //二叉树节点TreeNode* InsertNode = new TreeNode('J');TreeNode* TempNode = NodeA->Left;NodeA->Left = InsertNode;InsertNode->Left = TempNode;

二叉搜索树

  • 元素关联

    • 根节点的左子树不为空，则左子树上的所有节点的值均小于它根节点的值。

    • 根节点的右子树不为空，则右子树上的所有节点的值均大于它根节点的值。

    • 根节点的左子树以及右子树均为二叉排序树。

  • 元素排列

    • 中序遍历 LDR 左子树 根节点 右子树

    • 10 20 30 40 50 60 70 80 90

  • 元素搜索

    • 通过根节点按左子节点遍历下去为最小值节点。

    • 通过根节点按右子节点遍历下去为最大值节点。

    • 查找指定节点二分(左小右大)。

  • 删除节点

    • 删除节点为叶子节点 - 直接删除节点，不会对当前结构产生影响。

    • 删除节点仅存在左子树 - 删除节点左子树替换。

    • 删除节点仅存在右子树 - 删除节点右子树替换。

    • 删除节点同时存在左子树以及右子树 - 删除节点左子树内容挂在删除节点右子树中的左子节点，删除节点的右子节点替换被删除节点。

    • 示例代码

    #include <iostream>class TreeNode
{
public:int value;TreeNode* left;TreeNode* right;TreeNode(int Num) : value(Num), left(nullptr), right(nullptr){}
};class BinarySearchTree
{
public://插入节点TreeNode* Insert(TreeNode* Node, int value){//50, 30, 20, 40, 70, 60, 80, 10, 90//空节点if (Node == NULL) return new TreeNode(value);//判断大小if (value < Node->value){Node->left = Insert(Node->left, value);}else{Node->right = Insert(Node->right, value);}return Node;}//中序遍历void InOrderTraverse(TreeNode* Root){if (Root == NULL) return;InOrderTraverse(Root->left);std::cout << Root->value << std::endl;InOrderTraverse(Root->right);}//查找节点TreeNode* Search(TreeNode* Node, int value){if (Node == NULL) return NULL;if (Node->value == value) return Node;if (value < Node->value){return Search(Node->left, value);}else{return Search(Node->right, value);}}//删除节点TreeNode* Delete(TreeNode* Root, int value){if (Root == NULL) return NULL;//删除节点if (Root->value == value){if (Root->left == NULL && Root->right == NULL){delete Root;return NULL;}else if (Root->right == NULL && Root->left != NULL){TreeNode* retNode = Root->left;delete Root;return retNode;}else if (Root->right != NULL && Root->left == NULL){TreeNode* retNode = Root->right;delete Root;return retNode;}else{TreeNode* lastLeft = Root->right;while (lastLeft->left != NULL) lastLeft = lastLeft->left;lastLeft->left = Root->left;TreeNode* deleteNode = Root;Root = Root->right;delete deleteNode;return Root;}}if (Root->value > value){Root->left = Delete(Root->left, value);}if (Root->value < value){Root->right = Delete(Root->right, value);}return NULL;}
};int main()
{BinarySearchTree BST;TreeNode* Root = NULL;int Arr[] = {30, 20, 40, 35,70, 60, 80, 10, 90 };Root = BST.Insert(Root, 50);for (size_t i = 0; i < sizeof(Arr) / sizeof(Arr[0]); i++){BST.Insert(Root, Arr[i]);}BST.InOrderTraverse(Root);TreeNode* Temp = BST.Search(Root, 35);BST.Delete(Root, 70);return 0;
}

平衡二叉树

  • 平衡二叉树

    • 二叉排序树。

    • 任何一个节点的左子树以及右子树都是平衡二叉树。

    • 任何一个节点的左子树与右子树的高度差值的绝对值不能大于一。

  • 平衡因子

    • 节点的平衡因子为其节点左子树的高度减去其右子树的高度(0/1/-1)。

  • 最小不平衡子树

    • 二叉树中插入节点时，距离插入节点位置最近的BF值大于一的节点作为最小不平衡子树。

  • 节点失衡

    • 二叉树插入节点时，出现平衡因子绝对值大于一的最小不平衡子树。

    • 通过“旋转”来修正最小不平衡子树。

  • 旋转方式

    • 左旋

      • 失衡节点的右子节点作为新的根节点。

      • 将失衡节点作为新的根节点的左子节点。

      • 新根节点如果存在左子树则转到旧根节点右子树下。

    • 右旋

      • 失衡节点的左子节点作为新的根节点。

      • 将失衡节点作为新的根节点的右子节点。

      • 新根节点如果存在右子树则转到旧根节点左子树下。

    • 旋转类型

      • LL(单右旋转)

        • 触发 - 插入节点发生在左子树的左侧

        • 操作 - 失衡节点的左子节点作为新的根节点，将失衡节点作为新的根节点的右子节点。

        • 图解

                 3          2/          / \2          1   3/ 1    

            - RR(单左旋转)- 触发 - 插入节点发生在右子树的右侧- 操作 - 失衡节点的右子节点作为新的根节点，将失衡节点作为新的根节点的左子节点。- 图解```Objective-C++3              6\            / \6          3   8/ \         \5   8         5

  • 模拟旋转

    • 30 20 10 40 50 60 70 100 90

    • #include <stdio.h>
#include <stdlib.h>
#include <memory.h>//节点结构
typedef struct _Node
{int value;int height;struct _Node* left;struct _Node* right;
}Node;//节点高度
int GetNodeHeight(Node* node)
{if (node == NULL) return NULL;return node->height;
}//平衡因子
int GetNodeBalanceFactor(Node* node)
{if (node == NULL) return NULL;return GetNodeHeight(node->left) - GetNodeHeight(node->right);
}//左旋处理
Node* LeftRotate(Node* node)
{//失衡节点的右子节点作为新的根节点Node* Root = node->right;Node* Temp = Root->left;//将失衡节点作为新的根节点的左子节点Root->left = node;//新根节点如果存在左子树则转到旧根节点右子树下node->right = Temp;//修正节点高度node->height = max(GetNodeHeight(node->left), GetNodeHeight(node->right)) + 1;Root->height = max(GetNodeHeight(Root->left), GetNodeHeight(Root->right)) + 1;return Root;
}//右旋处理
Node* RightRotate(Node* node)
{//失衡节点的左子节点作为新的根节点Node* Root = node->left;Node* Temp = Root->right;//将失衡节点作为新的根节点的右子节点Root->right = node;//新根节点如果存在右子树则转到旧根节点左子树下node->left = Temp;//修正节点高度node->height = max(GetNodeHeight(node->left), GetNodeHeight(node->right)) + 1;Root->height = max(GetNodeHeight(Root->left), GetNodeHeight(Root->right)) + 1;return Root;
}//创建节点
Node* NewNode(int value)
{Node* node = malloc(sizeof(Node));if (node == NULL) return NULL;memset(node, 0, sizeof(Node));node->value = value;node->height = 1;node->left = NULL;node->right = NULL;return node;
}//插入节点
Node* Insert(Node* Root, int value)
{//空的结构if (Root == NULL) return NewNode(value);//节点关联if (Root->value > value){Root->left = Insert(Root->left, value);}else if (Root->value < value){Root->right = Insert(Root->right, value);}else{return Root;}//节点高度Root->height = max(GetNodeHeight(Root->left), GetNodeHeight(Root->right)) + 1;//节点失衡int nBalance = GetNodeBalanceFactor(Root);//左左if (nBalance > 1 &&  value < Root->left->value){return RightRotate(Root);};//右右if (nBalance < -1 && value > Root->right->value){return LeftRotate(Root);}//左右if (nBalance > 1 && value > Root->left->value){Root->left = LeftRotate(Root->left);return RightRotate(Root);}//右左if (nBalance < -1 && value < Root->right->value){Root->right = RightRotate(Root->right);return LeftRotate(Root);}return Root;
}int main()
{Node* Root = NULL;Root = Insert(Root, 30);Root = Insert(Root, 20);Root = Insert(Root, 25);return 0;
}

      • 示例代码        

http://www.lryc.cn/news/390581.html

相关文章：

  • Linux源码阅读笔记12-RCU案例分析
  • 【C++】双线性差值算法实现RGB图像缩放
  • 计算机网络知识普及之四元组
  • 深度探讨网络安全：挑战、防御策略与实战案例
  • “穿越时空的机械奇观：记里鼓车的历史与科技探秘“
  • DevOps CMDB平台整合Jira工单
  • Vue-路由
  • 【Rust入门教程】安装Rust
  • Character.ai因内容审查流失大量用户、马斯克：Grok-3用了10万块英伟达H100芯片
  • Spring源码九：BeanFactoryPostProcessor
  • 大模型笔记1: Longformer环境配置
  • 类和对象（提高）
  • 免费最好用的证件照制作软件，一键换底+老照片修复+图片动漫化，吊打付费！
  • antfu/ni 在 Windows 下的安装
  • Linux 生产消费者模型
  • 深入浅出：MongoDB中的背景创建索引
  • Spring事务十种失效场景
  • JELR-630HS漏电继电器 30-500mA 导轨安装 约瑟JOSEF
  • 如何实现一个简单的链表或栈结构
  • 抖音外卖服务商入驻流程及费用分别是什么？入驻官方平台的难度大吗？
  • “小红书、B站崩了”，背后的阿里云怎么了？
  • nginx的配置文件
  • 艾滋病隐球菌病的病原学诊断方法包括？
  • jQuery Tooltip 插件使用教程
  • 访问者模式在金融业务中的应用及其框架实现
  • .npy格式图像如何进行深度学习模型训练处理，亲测可行
  • XFeat快速图像特征匹配算法
  • 普元EOS学习笔记-低开实现图书的增删改查
  • 动态住宅代理IP详细解析
  • 等保2.0 实施方案之信息软件验证要求