Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现-阿里云开发者社区

开发者社区> 一个处女座的程序猿> 正文

Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现

简介: Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
+关注继续查看

树的基础知识


1、二叉树的遍—前序、中序、后序


一、二叉树


1、CBT


2、BST—二叉查找树BST的增删改查


1、BST的查找节点


2、BST的插入节点


3、BST的删除节点


3、BBT—平衡二叉树BBT→AVL/RBT


0、RBT红黑树和AVL


1、BBT的旋转


2、BBT的插入


3、BBT的查找


4、BBT的删除


4、堆


5、哈夫曼树HT/最优二叉树


二、多路查找树:多叉树——二叉到多叉的思考


1、多叉树


1、多叉树的查找与插入


2、B树及其变种——分裂节点、合并节点


3、R树—R树在实践中的应用


树相关算法的代码实现


1、二叉树的遍历——前中后、通过前中求后


2、二叉查找树、BST的插入节点、BST的删除


3、BBT单旋转、双旋转、BBT的插入、BBT的删除



参考文章:Algorithm:【Algorithm算法进阶之路】之数据结构基础知识


树的基础知识


      树Tree是一种抽象数据类型ADT,或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:


(1)、每个节点有零个或多个子节点;

(2)、没有父节点的节点称为根节点;

(3)、每一个非根节点有且只有一个父节点;

(4)、除了根节点外,每个子节点可以分为多个不相交的子树;

1、二叉树的遍—前序、中序、后序


二叉树的遍历,都要从先从左区域开始遍历。


1、前序遍历、中序遍历、后序遍历

注:根结点Degree、左子树L、右子树R

先(根)序遍历(根左右DLR):

中(根)序遍历(左根右LDR):BST的中序一定是递增有序的序列!

后(根)序遍历(左右根LRD):

结论:

(1)、二叉树结点的DLR、LDR、LRD中,所有叶子结点的先后顺序都是一致的,因为所有的叶节点都是从左到右的!


前序遍历:先(根)序遍历,根左右DLR

根节点→前序遍历左子树(DLR)→前序遍历右子树(DLR)

中序遍历:中(根)序遍历,左根右LDR。BST的中序一定是递增有序的序列!

中序遍历左子树(LDR)→根节点→中序遍历右子树(LDR)

(1)、比如35是因为3就是节点5的左子数;67是因为7是6的右子树,所以先遍历6的左子树即空→根节点6→右子树7

后序遍历:后(根)序遍历,左右根LRD

后序遍历左子树(LRD)→后序遍历右子树(LRD)→根节点

2、相关结论

(1)、二叉树结点的DLR、LDR、LRD中,所有叶子结点的先后顺序都是一致的,因为所有的叶节点都是从左区域到右区域的!


3、问题类型

(1)、通过前序中序求后序


Algorithm:【Algorithm算法进阶之路】之数据结构(数组、字符串、链表、栈、队列、树、图、哈希、堆)相关习题

https://yunyaniu.blog.csdn.net/article/details/100699314


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
《数据结构和算法分析》具有O(logN)对数特点的三个基本算法
对分查找 给定一个整数X和整数A0,A1,…,AN-1,后者已经预先排序并存在内存中,求使得Ai=X的下标i,如果X不在数据中,则返回i=-1。 int BinarySearch (const ElementType A[], ElementType x, int N)...
633 0
Algorithm:C++语言实现之字符串相关算法(字符串的循环左移、字符串的全排列、带有同个字符的全排列、串匹配问题的BF算法和KMP算法)(一)
Algorithm:C++语言实现之字符串相关算法(字符串的循环左移、字符串的全排列、带有同个字符的全排列、串匹配问题的BF算法和KMP算法)
19 0
经典算法面试题目-判断s2是否是s1的旋转字符串(1.8)
题目 Assume you have a method isSubstring which checks if one word is a substring of another.
787 0
kubeadm高可用master节点部署文档
kubeadm的标准部署里,etcd和master都是单节点的。 但上生产,至少得高可用。 etcd的高可用,用kubeadm微微扩散一下就可以。 但master却官方没有提及。 于是搜索了几篇文档,过几天测试一下。
1704 0
Spring Security笔记:使用BCrypt算法加密存储登录密码
在前一节使用数据库进行用户认证(form login using database)里,我们学习了如何把“登录帐号、密码”存储在db中,但是密码都是明文存储的,显然不太讲究。这一节将学习如何使用spring security3新加入的bcrypt算法,将登录加密存储到db中,并正常通过验证。
1540 0
经典算法面试题目-矩阵旋转90度(1.6)
题目 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place? 一张图像表示成NxN的矩阵,图像中每个像素是4个字节,写一个函数把图像旋转90度。
2209 0
经典算法面试题目-置矩阵行列元素为0(1.7)
题目 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0. 写一个函数处理一个MxN的矩阵,如果矩阵中某个元素为0,那么把它所在的行和列都置为0. 解答 简单题。
840 0
ML之LiR&SGDR:基于二种算法(LiR、SGDR)对Boston(波士顿房价)数据集(506,13+1)进行价格回归预测并对比各自性能
ML之LiR&SGDR:基于二种算法(LiR、SGDR)对Boston(波士顿房价)数据集(506,13+1)进行价格回归预测并对比各自性能
19 0
+关注
一个处女座的程序猿
国内互联网圈知名博主、人工智能领域优秀创作者,全球最大中文IT社区博客专家、CSDN开发者联盟生态成员、中国开源社区专家、华为云社区专家、51CTO社区专家、Python社区专家等,曾受邀采访和评审十多次。仅在国内的CSDN平台,博客文章浏览量超过2500万,拥有超过57万的粉丝。
1701
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载