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

• 公开视频 -> 链接点击跳转公开课程
• 博客首页 -> 链接点击跳转博客主页

目录

树的概念

结构特性

树的样式

树的存储

树的遍历

节点增删

二叉搜索树

平衡二叉树

---

树的概念

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

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

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

• 节点(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;
    }
    

    • 示例代码