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