• 公開(kāi)視頻 ->?鏈接點(diǎn)擊跳轉(zhuǎn)公開(kāi)課程
• 博客首頁(yè) ->?鏈接點(diǎn)擊跳轉(zhuǎn)博客主頁(yè)

目錄

樹(shù)的概念

結(jié)構(gòu)特性

樹(shù)的樣式

樹(shù)的存儲(chǔ)

樹(shù)的遍歷

節(jié)點(diǎn)增刪

二叉搜索樹(shù)

平衡二叉樹(shù)

---

樹(shù)的概念

• 二叉樹(shù)是樹(shù)形結(jié)構(gòu)，是一種非線性結(jié)構(gòu)。

  • 非線性結(jié)構(gòu)：在二叉樹(shù)中，數(shù)據(jù)項(xiàng)的排列不是簡(jiǎn)單的線性序列，而是通過(guò)節(jié)點(diǎn)間的鏈接構(gòu)成復(fù)雜的層次結(jié)構(gòu)。

  • 受限節(jié)點(diǎn)數(shù)目：每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，這限定了樹(shù)的分支寬度。

• 節(jié)點(diǎn)(Node)

  • 數(shù)據(jù)域：保存或顯示與節(jié)點(diǎn)相關(guān)聯(lián)的信息。

  • 左子節(jié)點(diǎn)指針：指向左側(cè)子節(jié)點(diǎn)的鏈接。

  • 右子節(jié)點(diǎn)指針：指向右側(cè)子節(jié)點(diǎn)的鏈接。

• 根節(jié)點(diǎn)(Root)

  • 節(jié)點(diǎn)是樹(shù)結(jié)構(gòu)的最頂端節(jié)點(diǎn)，它沒(méi)有父節(jié)點(diǎn)，并且是二叉樹(shù)結(jié)構(gòu)的起點(diǎn)。

• 父節(jié)點(diǎn)(Parent)

  • 與子節(jié)點(diǎn)相關(guān)聯(lián)的上一級(jí)節(jié)點(diǎn)。

• 子節(jié)點(diǎn)(Child)

  • 父節(jié)點(diǎn)指向的左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)。

• 葉子節(jié)點(diǎn)(Leaf)

  • 葉子節(jié)點(diǎn)是指沒(méi)有任何子節(jié)點(diǎn)的節(jié)點(diǎn)。在樹(shù)的結(jié)構(gòu)中，葉子節(jié)點(diǎn)總是位于最底層。

• 兄弟節(jié)點(diǎn)(Brother)

  • 在二叉樹(shù)中，共享同一父節(jié)點(diǎn)的兩個(gè)節(jié)點(diǎn)稱為兄弟節(jié)點(diǎn)。

• 節(jié)點(diǎn)的度

  • 節(jié)點(diǎn)分支數(shù)。

  • 度為0：節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)，即葉子節(jié)點(diǎn)。

  • 度為1：節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)。

  • 度為2：節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)。

• 結(jié)點(diǎn)層度：根節(jié)點(diǎn)的層次為1，以此遞增。

• 樹(shù)的深度：樹(shù)種節(jié)點(diǎn)層次的最大值。

結(jié)構(gòu)特性

• 二叉樹(shù)中第I層中最多存在2^(I - 1)的節(jié)點(diǎn)數(shù)量。

• 二叉樹(shù)中深度為I時(shí)最多存在2^I - 1的節(jié)點(diǎn)總數(shù)。

樹(shù)的樣式

• 二叉樹(shù)

  • 

• 完美二叉樹(shù)

  • 完美二叉樹(shù)中，除了葉子節(jié)點(diǎn)外其余所有節(jié)點(diǎn)的度都有2。

  • 完美二叉樹(shù)中，深度為I時(shí)節(jié)點(diǎn)數(shù)量為2^I - 1。

  • 

樹(shù)的存儲(chǔ)

• 順序存儲(chǔ)

  • 基于數(shù)組 - 內(nèi)存中使用連續(xù)的內(nèi)存空間

  • 假設(shè)根節(jié)點(diǎn)編號(hào)為x

    • 左子節(jié)點(diǎn)編號(hào)為2 * x

    • 右子節(jié)點(diǎn)編號(hào)為2 * x + 1

    • 

• 鏈?zhǔn)酱鎯?chǔ)

  • 基于鏈表 - ListNode

    • 

樹(shù)的遍歷

• 先序遍歷 DLR 根節(jié)點(diǎn) 左子樹(shù) 右子樹(shù)

  • 

• 中序遍歷 LDR 左子樹(shù) 根節(jié)點(diǎn) 右子樹(shù)

• 后序遍歷 LRD 左子樹(shù) 右子樹(shù) 根節(jié)點(diǎn)

  • 

  • 示例代碼

  #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()
  {//二叉樹(shù)節(jié)點(diǎn)
  #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//二叉樹(shù)圖解/*A/ \B   C/   / \D   E   F/ \   \G   H   I*///二叉樹(shù)關(guān)聯(lián)
  #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//二叉樹(shù)遍歷
  #if 1PreorderTraverse(NodeA);InOrderTraverse(NodeA);PostOrderTraverse(NodeA);
  #endifreturn 0;
  }
  

節(jié)點(diǎn)增刪

• 假如刪除節(jié)點(diǎn)為葉子節(jié)點(diǎn)，直接刪除節(jié)點(diǎn)并修正父節(jié)點(diǎn)對(duì)應(yīng)指向?yàn)镹ULL。

• 假如刪除節(jié)點(diǎn)存在一個(gè)子節(jié)點(diǎn)，子節(jié)點(diǎn)替換被刪除節(jié)點(diǎn)位置，并對(duì)應(yīng)指向。

• 假如刪除節(jié)點(diǎn)存在兩個(gè)子節(jié)點(diǎn)。

    //二叉樹(shù)節(jié)點(diǎn)TreeNode* InsertNode = new TreeNode('J');TreeNode* TempNode = NodeA->Left;NodeA->Left = InsertNode;InsertNode->Left = TempNode;

二叉搜索樹(shù)

• 元素關(guān)聯(lián)

  • 根節(jié)點(diǎn)的左子樹(shù)不為空，則左子樹(shù)上的所有節(jié)點(diǎn)的值均小于它根節(jié)點(diǎn)的值。

  • 根節(jié)點(diǎn)的右子樹(shù)不為空，則右子樹(shù)上的所有節(jié)點(diǎn)的值均大于它根節(jié)點(diǎn)的值。

  • 根節(jié)點(diǎn)的左子樹(shù)以及右子樹(shù)均為二叉排序樹(shù)。

  • 

• 元素排列

  • 中序遍歷 LDR 左子樹(shù) 根節(jié)點(diǎn) 右子樹(shù)

  • 10 20 30 40 50 60 70 80 90

  • 

• 元素搜索

  • 通過(guò)根節(jié)點(diǎn)按左子節(jié)點(diǎn)遍歷下去為最小值節(jié)點(diǎn)。

  • 通過(guò)根節(jié)點(diǎn)按右子節(jié)點(diǎn)遍歷下去為最大值節(jié)點(diǎn)。

  • 查找指定節(jié)點(diǎn)二分(左小右大)。

• 刪除節(jié)點(diǎn)

  • 刪除節(jié)點(diǎn)為葉子節(jié)點(diǎn) - 直接刪除節(jié)點(diǎn)，不會(huì)對(duì)當(dāng)前結(jié)構(gòu)產(chǎn)生影響。

  • 刪除節(jié)點(diǎn)僅存在左子樹(shù) - 刪除節(jié)點(diǎn)左子樹(shù)替換。

  • 刪除節(jié)點(diǎn)僅存在右子樹(shù) - 刪除節(jié)點(diǎn)右子樹(shù)替換。

  • 刪除節(jié)點(diǎn)同時(shí)存在左子樹(shù)以及右子樹(shù) - 刪除節(jié)點(diǎn)左子樹(shù)內(nèi)容掛在刪除節(jié)點(diǎn)右子樹(shù)中的左子節(jié)點(diǎn)，刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)替換被刪除節(jié)點(diǎn)。

  • 示例代碼

  #include <iostream>class TreeNode
  {
  public:int value;TreeNode* left;TreeNode* right;TreeNode(int Num) : value(Num), left(nullptr), right(nullptr){}
  };class BinarySearchTree
  {
  public://插入節(jié)點(diǎn)TreeNode* Insert(TreeNode* Node, int value){//50, 30, 20, 40, 70, 60, 80, 10, 90//空節(jié)點(diǎn)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);}//查找節(jié)點(diǎn)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);}}//刪除節(jié)點(diǎn)TreeNode* Delete(TreeNode* Root, int value){if (Root == NULL) return NULL;//刪除節(jié)點(diǎn)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;
  }
  

平衡二叉樹(shù)

• 平衡二叉樹(shù)

  • 二叉排序樹(shù)。

  • 任何一個(gè)節(jié)點(diǎn)的左子樹(shù)以及右子樹(shù)都是平衡二叉樹(shù)。

  • 任何一個(gè)節(jié)點(diǎn)的左子樹(shù)與右子樹(shù)的高度差值的絕對(duì)值不能大于一。

• 平衡因子

  • 節(jié)點(diǎn)的平衡因子為其節(jié)點(diǎn)左子樹(shù)的高度減去其右子樹(shù)的高度(0/1/-1)。

• 最小不平衡子樹(shù)

  • 二叉樹(shù)中插入節(jié)點(diǎn)時(shí)，距離插入節(jié)點(diǎn)位置最近的BF值大于一的節(jié)點(diǎn)作為最小不平衡子樹(shù)。

• 節(jié)點(diǎn)失衡

  • 二叉樹(shù)插入節(jié)點(diǎn)時(shí)，出現(xiàn)平衡因子絕對(duì)值大于一的最小不平衡子樹(shù)。

  • 通過(guò)“旋轉(zhuǎn)”來(lái)修正最小不平衡子樹(shù)。

• 旋轉(zhuǎn)方式

  • 左旋

    • 失衡節(jié)點(diǎn)的右子節(jié)點(diǎn)作為新的根節(jié)點(diǎn)。

    • 將失衡節(jié)點(diǎn)作為新的根節(jié)點(diǎn)的左子節(jié)點(diǎn)。

    • 新根節(jié)點(diǎn)如果存在左子樹(shù)則轉(zhuǎn)到舊根節(jié)點(diǎn)右子樹(shù)下。

  • 右旋

    • 失衡節(jié)點(diǎn)的左子節(jié)點(diǎn)作為新的根節(jié)點(diǎn)。

    • 將失衡節(jié)點(diǎn)作為新的根節(jié)點(diǎn)的右子節(jié)點(diǎn)。

    • 新根節(jié)點(diǎn)如果存在右子樹(shù)則轉(zhuǎn)到舊根節(jié)點(diǎn)左子樹(shù)下。

  • 旋轉(zhuǎn)類型

    • LL(單右旋轉(zhuǎn))

      • 觸發(fā) - 插入節(jié)點(diǎn)發(fā)生在左子樹(shù)的左側(cè)

      • 操作 - 失衡節(jié)點(diǎn)的左子節(jié)點(diǎn)作為新的根節(jié)點(diǎn)，將失衡節(jié)點(diǎn)作為新的根節(jié)點(diǎn)的右子節(jié)點(diǎn)。

      • 圖解

               3          2/          / \2          1   3/ 1    
        

          - RR(單左旋轉(zhuǎn))- 觸發(fā) - 插入節(jié)點(diǎn)發(fā)生在右子樹(shù)的右側(cè)- 操作 - 失衡節(jié)點(diǎn)的右子節(jié)點(diǎn)作為新的根節(jié)點(diǎn)，將失衡節(jié)點(diǎn)作為新的根節(jié)點(diǎn)的左子節(jié)點(diǎn)。- 圖解```Objective-C++3              6\            / \6          3   8/ \         \5   8         5
        

• 模擬旋轉(zhuǎn)

  • 30 20 10 40 50 60 70 100 90

  • 

  • 

    #include <stdio.h>
    #include <stdlib.h>
    #include <memory.h>//節(jié)點(diǎn)結(jié)構(gòu)
    typedef struct _Node
    {int value;int height;struct _Node* left;struct _Node* right;
    }Node;//節(jié)點(diǎn)高度
    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)
    {//失衡節(jié)點(diǎn)的右子節(jié)點(diǎn)作為新的根節(jié)點(diǎn)Node* Root = node->right;Node* Temp = Root->left;//將失衡節(jié)點(diǎn)作為新的根節(jié)點(diǎn)的左子節(jié)點(diǎn)Root->left = node;//新根節(jié)點(diǎn)如果存在左子樹(shù)則轉(zhuǎn)到舊根節(jié)點(diǎn)右子樹(shù)下node->right = Temp;//修正節(jié)點(diǎn)高度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)
    {//失衡節(jié)點(diǎn)的左子節(jié)點(diǎn)作為新的根節(jié)點(diǎn)Node* Root = node->left;Node* Temp = Root->right;//將失衡節(jié)點(diǎn)作為新的根節(jié)點(diǎn)的右子節(jié)點(diǎn)Root->right = node;//新根節(jié)點(diǎn)如果存在右子樹(shù)則轉(zhuǎn)到舊根節(jié)點(diǎn)左子樹(shù)下node->left = Temp;//修正節(jié)點(diǎn)高度node->height = max(GetNodeHeight(node->left), GetNodeHeight(node->right)) + 1;Root->height = max(GetNodeHeight(Root->left), GetNodeHeight(Root->right)) + 1;return Root;
    }//創(chuàng)建節(jié)點(diǎn)
    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;
    }//插入節(jié)點(diǎn)
    Node* Insert(Node* Root, int value)
    {//空的結(jié)構(gòu)if (Root == NULL) return NewNode(value);//節(jié)點(diǎn)關(guān)聯(lián)if (Root->value > value){Root->left = Insert(Root->left, value);}else if (Root->value < value){Root->right = Insert(Root->right, value);}else{return Root;}//節(jié)點(diǎn)高度Root->height = max(GetNodeHeight(Root->left), GetNodeHeight(Root->right)) + 1;//節(jié)點(diǎn)失衡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;
    }
    

    • 示例代碼????????