原文链接: https://gobea.cn/blog/detail/p6aeO26N.html, 转载请注明出处!
二叉树的品种
满二叉树
如上图所示,满二叉树的性质如下:
- 除最初一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。
- 第k层上的节点数为: 2^(k-1)
- 一个层数为k的满二叉树的总结点数为: (2^k) - 1
齐全二叉树
如上图所示,满二叉树的性质如下:
- 在满二叉树的根底上,最底层从右往左删去若干节点，失去的都是齐全二叉树
- 最低层能够不满,但最底层的节点都必须集中在最右边,也就是说次底层的节点肯定会有左子节点,但可能没有右子节点
如果对一棵有n个结点的齐全二叉树的结点按层序编号, 则对任一结点i (1≤i≤n):
- 如果i=1, 则结点i是二叉树的根, 无双亲;如果i>1, 则i节点的父节点是i/2(取整,不四舍五入)
- 如果2i>n, 则结点i无左孩子, 否则其左孩子是结点2i;
- 如果2i+1>n, 则结点i无右孩子, 否则其右孩子是结点2i+1
均衡二叉树
- 树的左右子树的高度差不超过1的数
- 空树也是均衡二叉树的一种
二叉搜寻树
- 二叉搜寻树的特点：对于树中的每个节点，它的左子树中所有关键字值小于父节点关键字值，而它的右子树中所有关键字值大于父节点的关键字值。
- 依据这个性质，对一个二叉树进行中序遍历，如果是枯燥递增的，则能够阐明这个树是二叉搜寻树。
- 二叉搜寻树能够用栈构造来实现，并不一定要用递归
b树
https://www.cnblogs.com/mayjors/p/11144874.html
b树是一种多路均衡查找树,每一个节点最多蕴含m个子节点,m被成为b树的阶,m的大小取决于磁盘页的大小,b树次要用于文件系统以及局部数据库索引,例如mongodb
- 最多有m个子节点,起码有m/2个子节点,m是b树的阶
- 每个节点有多个key,key数量比子节点少1(除叶子节点)
- 所有叶子节点都在同一层,并且是有序的
b树和二叉树的区别
- b树一个节点能够有多个子节点,而二叉树只能有两个
- mysql应用
b+树是因为能够缩小io次数,二叉树最坏状况下io次数等于树的高度 - b树是矮胖,二叉树是高瘦
- 如果一个页蕴含更多key,查问效率可能更快
b+树
b+树是b树的变种,具体如下:
- 每个节点的key数量等于子节点数量,每个key不保留数据,只保留索引,所有数据存储在子节点上
- 所有叶子节点蕴含了全副的key
- 在最底层,每一个叶子节点指向下一个叶子节点的指针,造成了一个有序链表
b树和b+树的区别
- b+树节点不蕴含数据,所有能够领有更多的key,所以更加矮胖,io次数更少
- b+树肯定会查找到叶子节点,查问性能稳固
- 反对范畴查问
二叉树的遍历
前序遍历
先序遍历就是先拜访根节点，在拜访左节点，最初拜访右节点
中序遍历
中序遍历就是先拜访左节点，再拜访根节点，最初拜访右节点
后序遍历
后序遍历就是先拜访左节点，再拜访右节点，最初拜访根节点
二叉树遍历代码
package mainimport "fmt"// 二叉树的数据结构type TreeNode struct { Data int Left *TreeNode Right *TreeNode}// 二叉树的实现type Tree struct { root *TreeNode}// 增加数据func (self *Tree) Add(data int) { var queue []*TreeNode newNode := &TreeNode{Data:data} if self.root == nil { self.root = newNode }else { queue = append(queue, self.root) for len(queue) != 0 { cur := queue[0] queue = append(queue[:0], queue[0+1:]...) // 往右树增加 if data > cur.Data { if cur.Right == nil { cur.Right = newNode } else { queue = append(queue, cur.Right) } // 往左数增加 } else { if cur.Left == nil { cur.Left = newNode } else { queue = append(queue, cur.Left) } } } }}// 前序遍历 根 ---> 左 --->右func (self *Tree )preorderTraverse(node *TreeNode) { if node == nil { return } else { fmt.Print(node.Data, " ") self.preorderTraverse(node.Left) self.preorderTraverse(node.Right) }}// 中序遍历 左 ---> 根 --->右func (self *Tree) inorderTraverse(node *TreeNode) { if node == nil { return } else { self.inorderTraverse(node.Left) fmt.Print(node.Data, " ") self.inorderTraverse(node.Right) }}// 后序遍历 左 ----> 右 ---> 根func (self *Tree) postTraverse(node *TreeNode) { if node == nil { return } else { self.postTraverse(node.Left) self.postTraverse(node.Right) fmt.Print(node.Data, " ") }}func main() { tree := &Tree{} tree.Add(50) tree.Add(45) tree.Add(40) tree.Add(48) tree.Add(51) tree.Add(61) tree.Add(71) fmt.Println("前序遍历") tree.preorderTraverse(tree.root) fmt.Println("") fmt.Println("中序遍历") tree.inorderTraverse(tree.root) fmt.Println("") fmt.Println("后续遍历") tree.postTraverse(tree.root)}以上代码来源于: https://blog.csdn.net/lucky404/article/details/92440857
参考
- https://gobea.cn/blog/detail/p6aeO26N.html
- https://www.cnblogs.com/mayjors/p/11144874.html
- https://blog.csdn.net/lucky404/article/details/92440857
阐明: 以上图片来源于网络