关于数据结构和算法:数据结构与算法-各类二叉树的概述以及二叉树遍历的三种方式

原文链接: 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 main

import "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

阐明: 以上图片来源于网络