树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。二叉树是每个结点最多有两个子树的树结构。二叉树是最简单的树结构，树结构为层次结构，与之对应的是线性结构。
二叉树分类：
一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下层的叶结点集中在靠左的若干位置上，这样的二叉树称为完全二叉树。
高度为h，并且由2h-1个结点组成的二叉树，称为满二叉树
二叉树的性质
性质1：二叉树第i层上的结点数目最多为2i-1(i>=1)
性质2：深度为k的二叉树至多有2k-1个结点（k>=1）
性质3：包含n个结点的二叉树的高度至少为(log2n) 1
性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2 1
二叉树排序：
前序遍历
1.访问根节点
2.前序遍历根节点的左子树
3.前序遍历根节点的右子树
中序遍历
1.中序遍历根节点的左子树
2.访问根节点
3.中序遍历根节点的右子树
后序遍历
1.后序遍历根节点的左子树
2.后序遍历根节点的右子树
3.访问根节点
二叉排序树又叫二叉查找树或者二叉搜索树，它首先是一个二叉树，而且必须满足下面的条件：
1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值；
2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值
3）左、右子树也分别为二叉排序树
4）没有键值相等的节点
实现：
在实际使用时会根据链表和有序数组等数据结构的不同优势进行选择。
有序数组的优势在于二分查找；
链表的优势在于数据项的插入和数据项的删除；
结构：
二叉树需要定义指向左孩子和右孩子节点的指针，还有存储的数据；
type BinaryTree struct {
Data interface{}
Lchild *BinaryTree
Rchild *BinaryTree
}
go 示例：
// binary_tree 二叉树
package Algorithm
import (
"reflect"
)
// 二叉树定义
type BinaryTree struct {
Data interface{}
Lchild *BinaryTree
Rchild *BinaryTree
}
// 构造方法
func NewBinaryTree(data interface{}) *BinaryTree {
return &BinaryTree{Data: data}
}
// 先序遍历
func (bt *BinaryTree) PreOrder() []interface{} {
t := bt
stack := NewStack(reflect.TypeOf(bt))
res := make([]interface{}, 0)
for t != nil || !stack.Empty() {
for t != nil {
res = append(res, t.Data)
stack.Push(t)
t = t.Lchild
}
if !stack.Empty() {
v, _ := stack.Pop()
t = v.(*BinaryTree)
t = t.Rchild
}
}
return res
}
// 中序遍历
func (bt *BinaryTree) InOrder() []interface{} {
t := bt
stack := NewStack(reflect.TypeOf(bt))
res := make([]interface{}, 0)
for t != nil || !stack.Empty() {
for t != nil {
stack.Push(t)
t = t.Lchild
}
if !stack.Empty() {
v, _ := stack.Pop()
t = v.(*BinaryTree)
res = append(res, t.Data)
t = t.Rchild
}
}
return res
}
// 后续遍历
func (bt *BinaryTree) PostOrder() []interface{} {
t := bt
stack := NewStack(reflect.TypeOf(bt))
s := NewStack(reflect.TypeOf(true))
res := make([]interface{}, 0)
for t != nil || !stack.Empty() {
for t != nil {
stack.Push(t)
s.Push(false)
t = t.Lchild
}
for flag, _ := s.Top(); !stack.Empty() && flag.(bool); {
s.Pop()
v, _ := stack.Pop()
res = append(res, v.(*BinaryTree).Data)
flag, _ = s.Top()
}
if !stack.Empty() {
s.Pop()
s.Push(true)
v, _ := stack.Top()
t = v.(*BinaryTree)
t = t.Rchild
}
}
return res
}
更多内容请关注每日编程，每天进步一点。
,
