給網(wǎng)站首頁圖片做外網(wǎng)超鏈接_為什么會彈出一個服務(wù)器登錄窗口網(wǎng)頁制作成品
- 公開視頻 ->?鏈接點擊跳轉(zhuǎn)公開課程
- 博客首頁 ->?鏈接點擊跳轉(zhuǎn)博客主頁
目錄
樹的概念
結(jié)構(gòu)特性
樹的樣式
樹的存儲
樹的遍歷
節(jié)點增刪
二叉搜索樹
平衡二叉樹
樹的概念
-
二叉樹是樹形結(jié)構(gòu)，是一種非線性結(jié)構(gòu)。
-
非線性結(jié)構(gòu)：在二叉樹中，數(shù)據(jù)項的排列不是簡單的線性序列，而是通過節(jié)點間的鏈接構(gòu)成復(fù)雜的層次結(jié)構(gòu)。
-
受限節(jié)點數(shù)目：每個節(jié)點最多有兩個子節(jié)點，這限定了樹的分支寬度。
-
-
節(jié)點(Node)
-
數(shù)據(jù)域：保存或顯示與節(jié)點相關(guān)聯(lián)的信息。
-
左子節(jié)點指針：指向左側(cè)子節(jié)點的鏈接。
-
右子節(jié)點指針：指向右側(cè)子節(jié)點的鏈接。
-
-
根節(jié)點(Root)
-
節(jié)點是樹結(jié)構(gòu)的最頂端節(jié)點，它沒有父節(jié)點，并且是二叉樹結(jié)構(gòu)的起點。
-
-
父節(jié)點(Parent)
-
與子節(jié)點相關(guān)聯(lián)的上一級節(jié)點。
-
-
子節(jié)點(Child)
-
父節(jié)點指向的左子節(jié)點或者右子節(jié)點。
-
-
葉子節(jié)點(Leaf)
-
葉子節(jié)點是指沒有任何子節(jié)點的節(jié)點。在樹的結(jié)構(gòu)中，葉子節(jié)點總是位于最底層。
-
-
兄弟節(jié)點(Brother)
-
在二叉樹中，共享同一父節(jié)點的兩個節(jié)點稱為兄弟節(jié)點。
-
-
節(jié)點的度
-
節(jié)點分支數(shù)。
-
度為0：節(jié)點沒有子節(jié)點，即葉子節(jié)點。
-
度為1：節(jié)點有一個子節(jié)點。
-
度為2：節(jié)點有兩個子節(jié)點。
-
-
結(jié)點層度：根節(jié)點的層次為1，以此遞增。
-
樹的深度：樹種節(jié)點層次的最大值。
結(jié)構(gòu)特性
-
二叉樹中第I層中最多存在2^(I - 1)的節(jié)點數(shù)量。
-
二叉樹中深度為I時最多存在2^I - 1的節(jié)點總數(shù)。
樹的樣式
-
二叉樹
-
-
完美二叉樹
-
完美二叉樹中，除了葉子節(jié)點外其余所有節(jié)點的度都有2。
-
完美二叉樹中，深度為I時節(jié)點數(shù)量為2^I - 1。
-
-
樹的存儲
-
順序存儲
-
基于數(shù)組 - 內(nèi)存中使用連續(xù)的內(nèi)存空間
-
假設(shè)根節(jié)點編號為x
-
左子節(jié)點編號為2 * x
-
右子節(jié)點編號為2 * x + 1
-
-
-
-
鏈?zhǔn)酱鎯?/p>
-
基于鏈表 - ListNode
-
-
樹的遍歷
-
先序遍歷 DLR 根節(jié)點 左子樹 右子樹
-
-
中序遍歷 LDR 左子樹 根節(jié)點 右子樹
-
后序遍歷 LRD 左子樹 右子樹 根節(jié)點
-
-
示例代碼
#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() {//二叉樹節(jié)點 #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*///二叉樹關(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//二叉樹遍歷 #if 1PreorderTraverse(NodeA);InOrderTraverse(NodeA);PostOrderTraverse(NodeA); #endifreturn 0; } -
節(jié)點增刪
-
假如刪除節(jié)點為葉子節(jié)點，直接刪除節(jié)點并修正父節(jié)點對應(yīng)指向為NULL。
-
假如刪除節(jié)點存在一個子節(jié)點，子節(jié)點替換被刪除節(jié)點位置，并對應(yīng)指向。
-
假如刪除節(jié)點存在兩個子節(jié)點。
//二叉樹節(jié)點TreeNode* InsertNode = new TreeNode('J');TreeNode* TempNode = NodeA->Left;NodeA->Left = InsertNode;InsertNode->Left = TempNode;
二叉搜索樹
-
元素關(guān)聯(lián)
-
根節(jié)點的左子樹不為空，則左子樹上的所有節(jié)點的值均小于它根節(jié)點的值。
-
根節(jié)點的右子樹不為空，則右子樹上的所有節(jié)點的值均大于它根節(jié)點的值。
-
根節(jié)點的左子樹以及右子樹均為二叉排序樹。
-
-
-
元素排列
-
中序遍歷 LDR 左子樹 根節(jié)點 右子樹
-
10 20 30 40 50 60 70 80 90
-
-
-
元素搜索
-
通過根節(jié)點按左子節(jié)點遍歷下去為最小值節(jié)點。
-
通過根節(jié)點按右子節(jié)點遍歷下去為最大值節(jié)點。
-
查找指定節(jié)點二分(左小右大)。
-
-
刪除節(jié)點
-
刪除節(jié)點為葉子節(jié)點 - 直接刪除節(jié)點，不會對當(dāng)前結(jié)構(gòu)產(chǎn)生影響。
-
刪除節(jié)點僅存在左子樹 - 刪除節(jié)點左子樹替換。
-
刪除節(jié)點僅存在右子樹 - 刪除節(jié)點右子樹替換。
-
刪除節(jié)點同時存在左子樹以及右子樹 - 刪除節(jié)點左子樹內(nèi)容掛在刪除節(jié)點右子樹中的左子節(jié)點，刪除節(jié)點的右子節(jié)點替換被刪除節(jié)點。
-
示例代碼
#include <iostream>class TreeNode { public:int value;TreeNode* left;TreeNode* right;TreeNode(int Num) : value(Num), left(nullptr), right(nullptr){} };class BinarySearchTree { public://插入節(jié)點TreeNode* Insert(TreeNode* Node, int value){//50, 30, 20, 40, 70, 60, 80, 10, 90//空節(jié)點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é)點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é)點TreeNode* Delete(TreeNode* Root, int value){if (Root == NULL) return NULL;//刪除節(jié)點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; } -
平衡二叉樹
-
平衡二叉樹
-
二叉排序樹。
-
任何一個節(jié)點的左子樹以及右子樹都是平衡二叉樹。
-
任何一個節(jié)點的左子樹與右子樹的高度差值的絕對值不能大于一。
-
-
平衡因子
-
節(jié)點的平衡因子為其節(jié)點左子樹的高度減去其右子樹的高度(0/1/-1)。
-
-
最小不平衡子樹
-
二叉樹中插入節(jié)點時，距離插入節(jié)點位置最近的BF值大于一的節(jié)點作為最小不平衡子樹。
-
-
節(jié)點失衡
-
二叉樹插入節(jié)點時，出現(xiàn)平衡因子絕對值大于一的最小不平衡子樹。
-
通過“旋轉(zhuǎn)”來修正最小不平衡子樹。
-
-
旋轉(zhuǎn)方式
-
左旋
-
失衡節(jié)點的右子節(jié)點作為新的根節(jié)點。
-
將失衡節(jié)點作為新的根節(jié)點的左子節(jié)點。
-
新根節(jié)點如果存在左子樹則轉(zhuǎn)到舊根節(jié)點右子樹下。
-
-
右旋
-
失衡節(jié)點的左子節(jié)點作為新的根節(jié)點。
-
將失衡節(jié)點作為新的根節(jié)點的右子節(jié)點。
-
新根節(jié)點如果存在右子樹則轉(zhuǎn)到舊根節(jié)點左子樹下。
-
-
旋轉(zhuǎn)類型
-
LL(單右旋轉(zhuǎn))
-
觸發(fā) - 插入節(jié)點發(fā)生在左子樹的左側(cè)
-
操作 - 失衡節(jié)點的左子節(jié)點作為新的根節(jié)點，將失衡節(jié)點作為新的根節(jié)點的右子節(jié)點。
-
圖解
3 2/ / \2 1 3/ 1- RR(單左旋轉(zhuǎn))- 觸發(fā) - 插入節(jié)點發(fā)生在右子樹的右側(cè)- 操作 - 失衡節(jié)點的右子節(jié)點作為新的根節(jié)點，將失衡節(jié)點作為新的根節(jié)點的左子節(jié)點。- 圖解```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é)點結(jié)構(gòu) typedef struct _Node {int value;int height;struct _Node* left;struct _Node* right; }Node;//節(jié)點高度 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é)點的右子節(jié)點作為新的根節(jié)點Node* Root = node->right;Node* Temp = Root->left;//將失衡節(jié)點作為新的根節(jié)點的左子節(jié)點Root->left = node;//新根節(jié)點如果存在左子樹則轉(zhuǎn)到舊根節(jié)點右子樹下node->right = Temp;//修正節(jié)點高度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é)點的左子節(jié)點作為新的根節(jié)點Node* Root = node->left;Node* Temp = Root->right;//將失衡節(jié)點作為新的根節(jié)點的右子節(jié)點Root->right = node;//新根節(jié)點如果存在右子樹則轉(zhuǎn)到舊根節(jié)點左子樹下node->left = Temp;//修正節(jié)點高度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é)點 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é)點 Node* Insert(Node* Root, int value) {//空的結(jié)構(gòu)if (Root == NULL) return NewNode(value);//節(jié)點關(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é)點高度Root->height = max(GetNodeHeight(Root->left), GetNodeHeight(Root->right)) + 1;//節(jié)點失衡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; }-
示例代碼????????
-
-