Go语言数据结构之二叉树必会知识点总结

在Golang实战开发的过程中，我们经常会遇到一些这样那样的问题，然后要卡好半天，等问题解决了才发现原来一些细节知识点还是没有掌握好。今天golang学习网就整理分享《Go语言数据结构之二叉树必会知识点总结》，聊聊语言二叉树，希望可以帮助到正在努力赚钱的你。

二叉树概念

二叉树是具有两个节点的树形结构，通常左边的子树被称为左子树，右边的子树称为右子树，图示如下：

在代码中我们可以用代码来定义一个二叉树结构：

type treeNode struct {
    Val string 	    //节点值
    left *treeNode 	//左节点
    right *treeNode //右节点
}

二叉树的性质

若二叉树结点的层次从1开始，则在二叉树第i层最多有2i-1 (i > 0)个节点。

深度为k的二叉树至少有k个结点，最多有2i - 1个结点。

对任何一个二叉树，如果其叶结点有n0 个，度为2的非叶结点有n2 个，则有 n0 = n2 + 1

具有n个结点的完全二叉树的深度为⌈log2(?+1)⌉

创建二叉树

// 创建节点
func CreateBinaryTree(data string) *treeNode {
    return &treeNode{data, nil, nil}
}

// 插入节点
func (node *treeNode) Insert(n *treeNode, data string) bool {
    cur := n
    for cur != nil {
        if cur.Val 
<h2>树的遍历</h2>
<p>树的遍历分为三种方式，分别为前序遍历，中序遍历，后序遍历。</p>
<h3>前序遍历(V-L-R)</h3>
<p>前序遍历访问顺序为先输 root 结点，然后再输出左子树，然后再输出右子树。</p>
<p>我们通过递归的方式进行遍历</p>
<p style="text-align:center"><img alt="" src="/uploads/20221224/167188860463a6fedc51cdc.png"></p>
<pre class="brush:go;">func preOrder(root *bt) {
	if root != nil {
		fmt.Print(root.Val, " ")
		preOrder(root.Left)
		preOrder(root.Right)
	}
}

中序遍历(L-V-R)

中序遍历访问顺序为先输出 root 的左子树，再输 root 结点，最后输出 root 的右子树。

func inOrder(root *bt) {
	if root != nil {
		inOrder(root.Left)
		fmt.Print(root.Val, " ")
		inOrder(root.Right)
	}
}

后序遍历(L-R-V)

后序遍历访问顺序为先输出 root 的左子树，最后输出 root 的右子树，再输 root 结点。

func posOrder(root *bt) {
	if root != nil {
		posOrder(root.Left)
		posOrder(root.Right)
		fmt.Print(root.Val, " ")
	}
}

今天关于《Go语言数据结构之二叉树必会知识点总结》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！