zhe.ink二叉树是由节点组成的数据结构，其中每个节点最多有两个子节点(也称为"左"和"右"子节点)。二叉树中的节点由边连接，边表示节点之间的链接。树中最顶层的节点称为根节点，除根节点外的每个节点都连接到唯一的父节点。
二叉树通常用于表示分层数据结构，例如家谱、组织结构图和文件系统目录。它们还被用作许多算法的底层数据结构，例如二进制搜索、排序和图形遍历算法。
二叉树有几个重要的属性，包括：
l级别的最大节点数为2(h+1)-1。
二叉树的高度是从根节点到叶节点(没有子节点的节点)的最长路径上的边数。空树的高度定义为 -1。
如果每个节点的左右子树的高度最多相差1，则称二叉树是平衡的。平衡二叉树的高度为O(log n)，其中n是树中的节点数。
二叉树可以通过多种方式遍历，包括按顺序(左子树、根节点、右子树)、前序(根节点、左子树、右子树)和后序(左子树、右子树、根节点)遍历。
二叉树有许多变体，包括二叉搜索树 (BST)、AVL树和红黑树，它们具有不同的规则来对树中的节点进行排序和平衡。
示例代码：它实现了一个二叉搜索树 (BST) 并以图形格式打印树的节点。
package main
import (
"fmt"
"os"
"io"
)
type BinaryNode struct {
left *BinaryNode
right *BinaryNode
data int64
}
type BinaryTree struct {
root *BinaryNode
}
func (t *BinaryTree) insert(data int64) *BinaryTree {
if t.root == nil {
t.root = &BinaryNode{data: data, left: nil, right: nil}
} else {
t.root.insert(data)
}
return t
}
func (n *BinaryNode) insert(data int64) {
if n == nil {
return
} else if data <= n.data {
if n.left == nil {
n.left = &BinaryNode{data: data, left: nil, right: nil}
} else {
n.left.insert(data)
}
} else {
if n.right == nil {
n.right = &BinaryNode{data: data, left: nil, right: nil}
} else {
n.right.insert(data)
}
}
}
func print(w io.Writer, node *BinaryNode, ns int, ch rune) {
if node == nil {
return
}
for i := 0; i < ns; i++ {
fmt.Fprint(w, " ")
}
fmt.Fprintf(w, "%c:%v\n", ch, node.data)
print(w, node.left, ns+2, 'L')
print(w, node.right, ns+2, 'R')
}
func main() {
tree := &BinaryTree{}
tree.insert(100).
insert(-20).
insert(-50).
insert(-15).
insert(-60).
insert(50).
insert(60).
insert(55).
insert(85).
insert(15).
insert(5).
insert(-10)
print(os.Stdout, tree.root, 0, 'M')
}
输出：
M:100
L:-20
L:-50
L:-60
R:-15
R:50
L:15
L:5
L:-10
R:60
L:55
R:85
苏公网安备
32050902101537号