go语言 二叉树

 

package main

import (
	"fmt"
	"reflect"
)

type binarynode struct {
	data   interface{} //数据
	lchild *binarynode //左子树
	rchild *binarynode //右子树
}

//创建二叉树
func (node *binarynode) create() {
	node = new(binarynode)
}

//先序遍历
func (node *binarynode) preorder() {
	if node == nil {
		return
	}
	//dlr — 先序遍历，即先根再左再右
	fmt.println(node.data)

	//递归遍历左子树
	node.lchild.preorder()
	//递归遍历右子树
	node.rchild.preorder()

}

//中序遍历
func (node *binarynode) midorder() {
	if node == nil {
		return
	}

	//ldr — 中序遍历，即先左再根再右
	//递归遍历左子树
	node.lchild.midorder()
	//打印数据
	fmt.println(node.data)
	//递归遍历右子树
	node.rchild.midorder()

}

//后序遍历
func (node *binarynode) rearorder() {
	if node == nil {
		return
	}

	//lrd — 后序遍历，即先左再右再根
	//递归遍历左子树
	node.lchild.rearorder()
	//递归遍历右子树
	node.rchild.rearorder()
	//打印数据
	fmt.println(node.data)
}

//二叉树高度 深度
func (node *binarynode) treeheight() int {
	if node == nil {
		return 0
	}
	//进入下一层遍历
	lh := node.lchild.treeheight()
	rh := node.rchild.treeheight()
	if lh > rh {
		lh++
		return lh
	} else {
		rh++
		return rh
	}

}

//二叉树叶子节点个数
//叶子节点是没有后继的节点
func (node *binarynode) leafcount(num *int) {
	if node == nil {
		return
	}
	//判断没有后继的节点为叶子节点
	if node.lchild == nil && node.rchild == nil {
		(*num)++
	}
	node.lchild.leafcount(num)
	node.rchild.leafcount(num)
}

//二叉树数据查找
func (node *binarynode) search(data interface{}) {
	if node == nil {
		return
	}

	//== 不支持slice 和 map
	//reflect.deepequal()
	if reflect.typeof(node.data) == reflect.typeof(data) && node.data == data {
		fmt.println("找到数据", node.data)
		return
	}
	node.lchild.search(data)
	node.rchild.search(data)
}

//二叉树销毁
func (node *binarynode) destroy() {
	if node == nil {
		return
	}

	node.lchild.destroy()
	node.lchild = nil
	node.rchild.destroy()
	node.rchild = nil
	node.data = nil

}

//二叉树反转
//如果想反转二叉树 二叉树必须是一个满二叉树
func (node *binarynode) reverse() {
	if node == nil {
		return
	}

	//交换节点  多重赋值
	node.lchild, node.rchild = node.rchild, node.lchild

	node.lchild.reverse()
	node.rchild.reverse()

}

//二叉树拷贝
func (node *binarynode) copy() *binarynode {
	if node == nil {
		return nil
	}
	lchild:=node.lchild.copy()
	rchild:=node.rchild.copy()

	//创建写节点 拷贝数据
	newnode:=new(binarynode)
	newnode.data=node.data
	newnode.lchild=lchild
	newnode.rchild=rchild
	return newnode
}