做网站需要哪些工程师,东莞网络推广怎么样,建站公司专业团队,学习网站建设课程公开视频 - 链接点击跳转公开课程博客首页 - 链接点击跳转博客主页
目录
树的概念
结构特性
树的样式
树的存储
树的遍历
节点增删
二叉搜索树
平衡二叉树 树的概念 二叉树是树形结构#xff0c;是一种非线性结构。 非线性结构#xff1a;在二叉树中#x…公开视频 - 链接点击跳转公开课程博客首页 - 链接点击跳转博客主页
目录
树的概念
结构特性
树的样式
树的存储
树的遍历
节点增删
二叉搜索树
平衡二叉树 树的概念 二叉树是树形结构是一种非线性结构。 非线性结构在二叉树中数据项的排列不是简单的线性序列而是通过节点间的链接构成复杂的层次结构。 受限节点数目每个节点最多有两个子节点这限定了树的分支宽度。 节点(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 iostreamclass 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 iostreamclass 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-C3 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;
}示例代码
