怎么做代刷网站教程网络营销策略的演变
- 公开视频 -> 链接点击跳转公开课程
- 博客首页 -> 链接点击跳转博客主页
目录
树的概念
结构特性
树的样式
树的存储
树的遍历
节点增删
二叉搜索树
平衡二叉树
树的概念
-
二叉树是树形结构，是一种非线性结构。
-
非线性结构：在二叉树中，数据项的排列不是简单的线性序列，而是通过节点间的链接构成复杂的层次结构。
-
受限节点数目：每个节点最多有两个子节点，这限定了树的分支宽度。
-
-
节点(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; }-
示例代码
-
-