樹是一種數據結構，它是由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

}

更多内容請關注每日編程，每天進步一點。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!