README
¶
binaryTree
go语言实现的二叉树，avl树和红黑树学习例子
example:
package main
import (
"fmt"
bt "github.com/gorustyt/binaryTree"
)
func main() {
arr := []int{7, 4, 9, 2, 5, 8, 11, 3, 12, 1}
tree := bt.NewBinaryTree[int]()
for _, v := range arr {
tree.Add(v)
}
bt.PrintBinaryTree[int](tree.Root, func(node *bt.BinaryTreeNode[int]) string {
return fmt.Sprintf("%v", node.GetElement()) //自定义显示值的方法
})
tree.Remove(9)
bt.PrintBinaryTree[int](tree.Root, func(node *bt.BinaryTreeNode[int]) string {
return fmt.Sprintf("%v", node.GetElement()) //自定义显示值的方法
})
}
结果：
===================================================================
7
┌─────┴─────┐
4 9
┌─────┴──┐ ┌──┴───┐
2 5 8 11
┌──┴──┐ └──┐
1 3 12
===================================================================
7
┌─────┴──────┐
4 11
┌─────┴──┐ ┌───┴───┐
2 5 8 12
┌──┴──┐
1 3
我相信最难的可能不只是如何轻松实现红黑树，还有如何实现上面树状打印结果，后面会出一篇文章专门讲解
你可以用任何语言轻松实现树状打印。方法为自己研究，之前找了很久网上的文章，想打印一颗二叉树，观察代码是否正确，找了很久都没找到，最后还是自己去研究，最后研究出来这个方法，纯套公式，可以控制打印结果，兼容汉字。有问题的朋友评论区留言，抽空解答。
关于红黑树的研究，网上有很多最全教程都有问题，结果就是困扰自己很久，后面通过断点调试，慢慢还原了整个场景，总结出了整套方法
Documentation
¶
Index ¶
- Constants
- func PrintBinaryTree[T CmpT](node *BinaryTreeNode[T], cb func(node *BinaryTreeNode[T]) string)
- type BinaryTree
- func (t *BinaryTree[T]) Add(ele T)
- func (t *BinaryTree[T]) FindNode(ele T) (*BinaryTreeNode[T], bool)
- func (t *BinaryTree[T]) FindSuccessor(node *BinaryTreeNode[T]) *BinaryTreeNode[T]
- func (t *BinaryTree[T]) Height() int
- func (t *BinaryTree[T]) InOrder(cb func(node *BinaryTreeNode[T]))
- func (t *BinaryTree[T]) InOrderByVisitor(cb func(node *BinaryTreeNode[T]))
- func (t *BinaryTree[T]) Len() int
- func (t *BinaryTree[T]) LevelOrder(cb func(node *BinaryTreeNode[T]))
- func (t *BinaryTree[T]) LevelOrderByVisitor(cb func(node *BinaryTreeNode[T]))
- func (t *BinaryTree[T]) PostOrder(cb func(node *BinaryTreeNode[T]))
- func (t *BinaryTree[T]) PostOrderByVisitor(cb func(node *BinaryTreeNode[T]))
- func (t *BinaryTree[T]) PreOrder(cb func(node *BinaryTreeNode[T]))
- func (t *BinaryTree[T]) PreOrderByVisitor(cb func(node *BinaryTreeNode[T]))
- func (t *BinaryTree[T]) Predecessor(node *BinaryTreeNode[T]) *BinaryTreeNode[T]
- func (t *BinaryTree[T]) Remove(ele T)
- type BinaryTreeNode
- func (n *BinaryTreeNode[T]) ColorBlack()
- func (n *BinaryTreeNode[T]) ColorRed()
- func (n *BinaryTreeNode[T]) GetElement() interface{}
- func (n *BinaryTreeNode[T]) HasTwoChildren() bool
- func (n *BinaryTreeNode[T]) Height() int
- func (n *BinaryTreeNode[T]) IsAvlBalance() bool
- func (n *BinaryTreeNode[T]) IsBlack() bool
- func (n *BinaryTreeNode[T]) IsLeaf() bool
- func (n *BinaryTreeNode[T]) IsLeftChild() bool
- func (n *BinaryTreeNode[T]) IsRed() bool
- func (n *BinaryTreeNode[T]) IsRightChild() bool
- func (n *BinaryTreeNode[T]) LeftHeight() int
- func (n *BinaryTreeNode[T]) RightHeight() int
- func (n *BinaryTreeNode[T]) UpdateHeight()
- type CmpT
- type SimpleQueue
Constants ¶
View Source
const ( BinarySearchTreeType = iota AvlTreeType RbTreeType )
Variables ¶
This section is empty.
Functions ¶
func PrintBinaryTree ¶
func PrintBinaryTree[T CmpT](node *BinaryTreeNode[T], cb func(node *BinaryTreeNode[T]) string)
//树状字符 //"└" "─" "┌─────────┴─────────┐" "┬" //"├" //"─┴─"
Types ¶
type BinaryTree ¶
type BinaryTree[T CmpT] struct { Root *BinaryTreeNode[T] TreeType int // contains filtered or unexported fields }
二叉树
func NewBinaryTree ¶
func NewBinaryTree[T CmpT]() *BinaryTree[T]
func NewRbTree ¶
func NewRbTree[T CmpT]() *BinaryTree[T]
func (*BinaryTree[T]) Add ¶
func (t *BinaryTree[T]) Add(ele T)
func (*BinaryTree[T]) FindNode ¶
func (t *BinaryTree[T]) FindNode(ele T) (*BinaryTreeNode[T], bool)
根据元素找到节点
func (*BinaryTree[T]) FindSuccessor ¶
func (t *BinaryTree[T]) FindSuccessor(node *BinaryTreeNode[T]) *BinaryTreeNode[T]
找后继者
func (*BinaryTree[T]) InOrder ¶
func (t *BinaryTree[T]) InOrder(cb func(node *BinaryTreeNode[T]))
func (*BinaryTree[T]) InOrderByVisitor ¶
func (t *BinaryTree[T]) InOrderByVisitor(cb func(node *BinaryTreeNode[T]))
func (*BinaryTree[T]) Len ¶
func (t *BinaryTree[T]) Len() int
func (*BinaryTree[T]) LevelOrder ¶
func (t *BinaryTree[T]) LevelOrder(cb func(node *BinaryTreeNode[T]))
func (*BinaryTree[T]) LevelOrderByVisitor ¶
func (t *BinaryTree[T]) LevelOrderByVisitor(cb func(node *BinaryTreeNode[T]))
func (*BinaryTree[T]) PostOrder ¶
func (t *BinaryTree[T]) PostOrder(cb func(node *BinaryTreeNode[T]))
func (*BinaryTree[T]) PostOrderByVisitor ¶
func (t *BinaryTree[T]) PostOrderByVisitor(cb func(node *BinaryTreeNode[T]))
func (*BinaryTree[T]) PreOrder ¶
func (t *BinaryTree[T]) PreOrder(cb func(node *BinaryTreeNode[T]))
func (*BinaryTree[T]) PreOrderByVisitor ¶
func (t *BinaryTree[T]) PreOrderByVisitor(cb func(node *BinaryTreeNode[T]))
func (*BinaryTree[T]) Predecessor ¶
func (t *BinaryTree[T]) Predecessor(node *BinaryTreeNode[T]) *BinaryTreeNode[T]
找前驱
func (*BinaryTree[T]) Remove ¶
func (t *BinaryTree[T]) Remove(ele T)
type BinaryTreeNode ¶
type BinaryTreeNode[T CmpT] struct { Index int //在二叉树中索引,打印辅助 // contains filtered or unexported fields }
func NewBinaryTreeNode ¶
func NewBinaryTreeNode[T CmpT](element T, parent *BinaryTreeNode[T]) *BinaryTreeNode[T]
func RotateLeft ¶
func RotateLeft[T CmpT](node *BinaryTreeNode[T]) *BinaryTreeNode[T]
func RotateRight ¶
func RotateRight[T CmpT](node *BinaryTreeNode[T]) *BinaryTreeNode[T]
func (*BinaryTreeNode[T]) ColorBlack ¶
func (n *BinaryTreeNode[T]) ColorBlack()
func (*BinaryTreeNode[T]) ColorRed ¶
func (n *BinaryTreeNode[T]) ColorRed()
func (*BinaryTreeNode[T]) GetElement ¶
func (n *BinaryTreeNode[T]) GetElement() interface{}
func (*BinaryTreeNode[T]) HasTwoChildren ¶
func (n *BinaryTreeNode[T]) HasTwoChildren() bool
是否有2个孩子
func (*BinaryTreeNode[T]) Height ¶
func (n *BinaryTreeNode[T]) Height() int
func (*BinaryTreeNode[T]) IsBlack ¶
func (n *BinaryTreeNode[T]) IsBlack() bool
func (*BinaryTreeNode[T]) IsLeaf ¶
func (n *BinaryTreeNode[T]) IsLeaf() bool
func (*BinaryTreeNode[T]) IsLeftChild ¶
func (n *BinaryTreeNode[T]) IsLeftChild() bool
func (*BinaryTreeNode[T]) IsRed ¶
func (n *BinaryTreeNode[T]) IsRed() bool
func (*BinaryTreeNode[T]) IsRightChild ¶
func (n *BinaryTreeNode[T]) IsRightChild() bool
func (*BinaryTreeNode[T]) LeftHeight ¶
func (n *BinaryTreeNode[T]) LeftHeight() int
func (*BinaryTreeNode[T]) RightHeight ¶
func (n *BinaryTreeNode[T]) RightHeight() int
func (*BinaryTreeNode[T]) UpdateHeight ¶
func (n *BinaryTreeNode[T]) UpdateHeight()
type SimpleQueue ¶
type SimpleQueue struct {
// contains filtered or unexported fields
}
func NewSimpleQueue ¶
func NewSimpleQueue() *SimpleQueue
func (*SimpleQueue) Empty ¶
func (q *SimpleQueue) Empty() bool
func (*SimpleQueue) Len ¶
func (q *SimpleQueue) Len() int
func (*SimpleQueue) Offer ¶
func (q *SimpleQueue) Offer(ele interface{})
func (*SimpleQueue) Poll ¶
func (q *SimpleQueue) Poll() (ele interface{})
Source Files
Directories
Click to show internal directories.
Click to hide internal directories.