9.3 KiB

Raw Permalink Blame History

title	tags	categories	date
用go实现二叉树	数据结构	数据结构, 二叉树	2022-05-08 20:01:00

用go实现二叉树

二叉查找树（Binary Search Tree，简称BST）是一棵二叉树，它的左子节点的值比父节点的值要小，右节点的值要比父节点的值大。它的高度决定了它的查找效率。在理想的情况下，二叉查找树增删查改的时间复杂度为O(logN) (其中N为节点数），最坏的情况下为O(N)。当它的高度为logN+1时，我们就说二叉查找树是平衡的。

二叉树的构成

因为二叉树的节点需要可比较，所以定义了一个接口，包含了比较大小的方法和是否相等的方法


// 实现该接口则代表可比较
type compare interface {
	// 如果大于返回true,否则返回false
	compare(data interface{}) bool
	// 判断是否相等
	equals(data interface{}) bool
}

// 二叉树节点
type BST struct {
	// 节点值
	data      compare
	// 左节点
	LeftNode  *BST
	// 右节点
	RightNode *BST
}

// 节点值得结构体，实现了compare接口
type data struct {
    key   int
    value interface{}
}

func (d *data) equals(d1 interface{}) bool {
    if d.key == d1.(*data).key {
        return true
    }
        return false
}

func (d *data) compare(d1 interface{}) bool {
    if d.key > d1.(*data).key {
        return true
    }
        return false
}

二叉树的插入

二叉树的插入非常简单，先判断根节点是否为空，为空则直接作为根节点，若不为空则找到需要插入位置的父节点，从根节点开始比较，小于则向左子节点靠近，大于则靠近右子节点，找到插入位置的父节点后，再进行比较插入就行。

// insert 插入
func (b *BST) insert(content compare) {
	var parent *BST
	temp := b
	// 先判断根节点是否为空
	if temp.data == nil {
		temp.data = content
		return
	}
	// 循环遍历找到父节点
	for true {
		// 当节点为null时，
		if temp == nil {
			break
		}
		parent = temp
		// 如果当前节点值小于插入的值，则跳向左子节点
		if temp.data.compare(content) {
			temp = temp.LeftNode
		} else {
			temp = temp.RightNode
		}
	}
    // 比较值，进行插入赋值
	if parent.data.compare(content) {
		parent.LeftNode = &BST{
			data:      content,
			LeftNode:  nil,
			RightNode: nil,
		}
	} else {
		parent.RightNode = &BST{
			data:      content,
			LeftNode:  nil,
			RightNode: nil,
		}
	}
}

func main() {
    bst := NewBST()
    bst.insert(&data{
    key:   3,
    value: "123",
    })
    
    bst.insert(&data{
    key:   2,
    value: "234",
    })
    bst.insert(&data{
    key:   1,
    value: "345",
    })
    bst.insert(&data{
    key:   4,
    value: "456",
    })
    fmt.Println(bst)
}

通过goland断点调试查看插入结果

二叉树节点查询

二叉树查询只需要依次比较大小进行判断就能找到需要的值

// 查询
func (b *BST) query(node compare) compare {
	temp := b
	for true {
		// 判断节点是否为空
		if temp == nil {
			return nil
		}
		// 判断节点的值是否匹配
		if temp.data.equals(node) {
			return temp.data
		}
        // 根据节点值得大小移动当前位置
		if temp.data.compare(node) {
			temp = temp.LeftNode
		} else {
			temp = temp.RightNode
		}
	}
	return nil
}

func main() {
        bst := NewBST()
        bst.insert(&data{
            key:   3,
            value: "123",
        })
        
        bst.insert(&data{
            key:   2,
            value: "234",
        })
        bst.insert(&data{
            key:   1,
            value: "345",
        })
        bst.insert(&data{
            key:   4,
            value: "456",
        })
        // &{4 456}
        fmt.Println(bst.query(&data{key: 4}))
}

二叉树更新

更新二叉树节点得值和插入类似，依次遍历找到节点更新即可

func (b *BST) update(node compare) error {
	temp := b
	for true {
		if temp == nil {
			return errors.New("not found")
		}
		if temp.data.equals(node) {
			temp.data = node
			return nil
		}

		if temp.data.compare(node) {
			temp = temp.LeftNode
		} else {
			temp = temp.RightNode
		}
	}
	return nil
}

节点遍历

节点遍历分为三种方式，分别为前序遍历，中序遍历，后续遍历

前序遍历
前序遍历访问顺序为当前节点，左节点，右节点我们通过递归的方式进行遍历该二叉树我们通过前序遍历的顺序为3 2 4 7 6 9

    // 前序遍历
func (b *BST) frontItem(slice []compare) []compare {
        if b.data == nil {
            return nil
        }
        slice = append(slice, b.data)
        if b.LeftNode != nil {
            slice = b.LeftNode.frontItem(slice)
        }
        if b.RightNode != nil {
            slice = b.RightNode.frontItem(slice)
        }
        return slice
}

中序遍历
中序遍历访问顺序为当左子节点，当前节点，右子节点前面的二叉树我们通过中序遍历的顺序为2 3 4 7 6 9

// 中序遍历
func (b *BST) midItem(slice []compare) []compare {
	if b.data == nil {
		return nil
	}
	if b.LeftNode != nil {
		slice = b.LeftNode.frontItem(slice)
	}
	slice = append(slice, b.data)
	if b.RightNode != nil {
		slice = b.RightNode.frontItem(slice)
	}
	return slice
}

后序遍历
后序遍历访问顺序为左节点，右节点，当前节点前面二叉树我们通过后续遍历访问顺序为2 6 9 7 4 3

// 后序遍历
func (b *BST) rearItem(slice []compare) []compare {
	if b.data == nil {
		return nil
	}
	if b.LeftNode != nil {
		slice = b.LeftNode.rearItem(slice)
	}
	if b.RightNode != nil {
		slice = b.RightNode.rearItem(slice)
	}
	slice = append(slice, b.data)
	return slice
}

二叉树删除

二叉树得删除分为三种情况

节点左右子节点都为空

该情况只需要将该节点从父节点的指向删除即可
节点的子节点有一个为空

该情况需要将该节点的唯一子节点根据大小连接向该节点的父节点从该二叉树中删除节点6，只需要将节点7的左子节点指向5即可
节点的左右子节点都存在

该情况需要进行节点交换，需要先获取到当前节点的右子节点的中序遍历的第一个节点，然后交换两个节点的值，如果该右子节点的前序遍历首节点存在右子节点，则继续获取并交换，知道将该节点交换到叶子节点。

若将该二叉树的节点7删除，先需要获取右子节点的中序遍历守节点，因为节点9不存在左子节点，所以该节点就为9，我们就将节点9与节点7 进行交换，因为仍不为叶子节点，所以继续获取，将节点11与节点7交换，最终交换结果为：我们直接将该叶子节点删除即可

// 删除节点
func (b *BST) delete(node compare) error {
	temp := b
	if temp == nil {
		return errors.New("root")
	}
	isRoot := false
	var parent *BST
	// 获取要删除节点的位置和父节点位置
	for true {
        // 判断节点是否为根节点
		if b.data.equals(node) {
			isRoot = true
			break
		}
        // 判断节点的值的大小
		if temp.data.compare(node) {
			if temp.LeftNode == nil {
				return errors.New("not found")
			}
			if temp.LeftNode.data.equals(node) {
				parent = temp
				temp = temp.LeftNode
				break
			} else {
				temp = temp.LeftNode
			}
		} else {
			if temp.RightNode == nil {
				return errors.New("not found")
			}
			if temp.RightNode.data.equals(node) {
				parent = temp
				temp = temp.RightNode
				break
			} else {
				temp = temp.RightNode
			}
		}
	}

	// case1: 删除节点即无左节点也无右节点
	if temp.LeftNode == nil && temp.RightNode == nil {
		if parent.data.compare(node) {
			parent.LeftNode = nil
		} else {
			parent.RightNode = nil
		}
		return nil

		// case2: 删除节点有左节点无右节点
	} else if temp.LeftNode != nil && temp.RightNode == nil {

		if isRoot {
			b.data = temp.LeftNode.data
			b.LeftNode = temp.LeftNode.LeftNode
			b.RightNode = temp.LeftNode.RightNode
			return nil
		}

		if parent.LeftNode == temp {
			parent.LeftNode = temp.LeftNode
		} else {
			parent.RightNode = temp.LeftNode
		}
		return nil

		// case3: 删除节点有右节点无左节点
	} else if temp.LeftNode == nil && temp.RightNode != nil {
		if isRoot {
			b.data = temp.RightNode.data
			b.LeftNode = temp.RightNode.LeftNode
			b.RightNode = temp.RightNode.RightNode
			return nil
		}
		if parent.LeftNode == temp {
			parent.LeftNode = temp.RightNode
		} else {
			parent.RightNode = temp.RightNode
		}
		return nil

		// case3: 删除节点有右节点有左节点
	} else {
		for temp.RightNode != nil {
			firstMidNode := temp.RightNode.firstMidNode()
			firstMidNode.data, temp.data = temp.data, firstMidNode.data
			temp = firstMidNode
		}
		return b.delete(node)
	}
}

// 获取中序遍历第一个节点
func (b *BST) firstMidNode() *BST {
    temp := b
    for true {
        if temp.LeftNode == nil {
        return temp
    }
        temp = temp.LeftNode
    }
    return nil
}

9.3 KiB Raw Permalink Blame History Unescape Escape

用go实现二叉树

二叉树的构成

二叉树的插入

二叉树节点查询

二叉树更新

节点遍历

前序遍历

中序遍历

后序遍历

二叉树删除

个人博客 https://shhy.xyz

9.3 KiB

Raw Permalink Blame History