数据结构与算法 - 树,BST 树

2022-03-17 本文已影响0人 husky_1

1.1 基本术语

树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根（Root）的结点；（2）当n>1时，其余结点可以分为互不相交的有限集T1、T2、……Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）

tree

基本术语

节点：
使用树结构存储的每一个数据元素都被称为结点，例如节点A,B,C,D，E,F,G,H,I,J,K,L,M

父节点：也叫双亲节点，若一个节点含有子节点，则这个节点称为其子节点的父节点，例如节点B，C，D 的父节点是A， B又是E,F 的父节点
兄弟节点：拥有相同的父节点的节点，例如A是B，C，D的父节点，所以B,C,D 是彼此的兄弟节点
子节点：又称孩子节点，即与节点相连的下属第一层的节点，例如，B，C，D是A节点的子节点，E，F是B的子节点
子孙节点/ 祖先节点 ：以某节点为根的子树中任一节点都称为该节点的子孙，例如，B，C，D，E，F，G，H，I，J，K，L，M 都可通过A节点通过路径相连，所以他们都是A的子孙节点，节点的子节点一定也是子孙节点
叶子节点：如果结点没有任何子结点，那么此结点称为叶子结点（叶结点）。例如图中，结点 K、L、F、G、M、I、J 都是这棵树的叶子结点
节点的度：节点含有子节点的数量，例如节点A的度为3，节点B的度为2
节点的层次：也叫节点的深度从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推。。。。 A的层为1， B，C，D的层为2.。。。
堂兄弟节点：位于同一层的，并且父节点之间是兄弟结点的结点互为堂兄弟结点，上图中，E，G，H为堂兄弟结点，F和G，H也是堂兄弟结点，他们的父节点是兄弟结点
树的深度：与树的度对应于结点的度一样，树的深度也是选取结点中的最大深度（或最大层次），上图中的树的深度为4
树的度：选取所有结点中最大的度，就是树的度，例如上述树中节点最大的度为3，所以树的度为3

1.2 二叉树

树中的每一个节点最多有两个子节点的树，或者说是树中的每一个节点的度最大为2 。二叉树的子节点分别称为左节点和右节点

二叉树

二叉树的深度优先遍历：
前序遍历：根结点 ---> 左子树 ---> 右子树 (1,2,4,5,3,6)

中序遍历：左子树---> 根结点 ---> 右子树. (4,2,5,1,6,3)

后序遍历：左子树 ---> 右子树 ---> 根结点 (4,5,2,6,3,1)
二叉树的层次遍历：按层从左到右依次遍历(1,2,3,4,5,6)

二叉树具有以下几个性质：

二叉树中，第 i 层最多有 2i-1 个结点。
如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。
二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1

1.2.1 满二叉树

所有的非叶子节点都存在左右子节点，并且所有的叶子节点都在最后一层

image.png

满二叉树除了满足普通二叉树的性质，还具有以下性质：

满二叉树中第 i 层的节点数为 2n-1 个。
深度为 k 的满二叉树必有 2k-1 个节点，叶子数为 2k-1。
满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
具有 n 个节点的满二叉树的深度为 log2(n+1)。

1.2.2 完全二叉树

如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。满二叉树一定是完全二叉树

image.png

完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质，比如说，n 个结点的完全二叉树的深度为 ⌊log2 n⌋+1。

⌊log2n⌋ 表示取小于 log2n 的最大整数。例如，⌊log24⌋ = 2，而 ⌊log25⌋ 结果也是 2。

对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号（如图 3a)），对于任意一个结点 i ，完全二叉树还有以下几个结论成立：

当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
如果 2i>n（总结点的个数），则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2i 。
如果 2i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2i+1

1.2.3 二叉搜索树（binary search tree）

也叫二叉排序树，指除了叶子节点外，左子节点的值要小于当前节点，右子节点的值要大于当前节点

# golang 语言定义bst 树， 

type BST struct {
    root *Node // 根节点
    size int   //  节点个数
}

type Node struct {
    val   int
    left  *Node // 左节点
    right *Node // 右节点
}

添加元素

func (bst *BST) AddElement(val int) {
    bst.root=bst.addElement(bst.root,val)
}

func (bst *BST)addElement(node *Node, val int) *Node {
    if node == nil {
        bst.size++
        return &Node{
            val: val,
        }
    }
    if node.val > val {
        // 插入左子树
        node.left=bst.addElement(node.left, val)
    }else if node.val < val {
        // 插入右树
        node.right=bst.addElement(node.right,val)
    } else {
        fmt.Println(node.val,val)
        panic("bst tree find equal nums")
    }
    return node
}


func main(){
    bst:=new(BST)
    bst.AddElement(3)
    bst.AddElement(10)
    bst.AddElement(1)
    bst.AddElement(7)
    bst.AddElement(5)
    bst.AddElement(9)
    bst.AddElement(12)
    fmt.Println(bst.size)
}

查找元素


func (bst *BST) Search(val int) *Node {
    return search(bst.root, val)

}

func search(node *Node, val int) *Node {
    // 未找到
    if node == nil {
        return nil
    }
    // 找到
    if node.val == val {
        return node
    }
    // 右子树查找
    if node.val < val {
        return search(node.right, val)
    } else {
        // 左子树查找
        return search(node.left, val)
    }
}


func main(){
    bst:=new(BST)
    bst.AddElement(3)
    bst.AddElement(10)
    bst.AddElement(1)
    bst.AddElement(7)
    bst.AddElement(5)
    bst.AddElement(9)
    bst.AddElement(12)
    fmt.Println(bst.Search(1))
}

查找父节点

func (bst *BST) SearchParent(val int) *Node {
    return searchParent(bst.root, val)
}

func searchParent(node *Node, val int) *Node {
    // 未找到
    if node == nil {
        return nil
    }
    left := node.left
    right := node.right

    // 找到父节点
    if (left != nil && left.val == val) || (right != nil && right.val == val) {
        return node
    }
    // 未找到,从右子树找
    if left != nil && left.val < val {
        return searchParent(right, val)
    }

    // 未找到,从左子树找
    if right != nil && right.val > val {
        return searchParent(left, val)
    }
    return nil
}

遍历

// 前序遍历
func preOrder(node *Node) {
    if node == nil {
        return
    }
    fmt.Printf("%d\t ",node.val)
    preOrder(node.left)
    preOrder(node.right)
}

// 中序遍历
func midOrder(node *Node) {
    if node == nil {
        return
    }
    midOrder(node.left)
    fmt.Printf("%d\t ",node.val)
    midOrder(node.right)
}

// 后序遍历
func backOrder(node *Node) {
    if node == nil {
        return
    }
    backOrder(node.left)
    backOrder(node.right)
    fmt.Printf("%d\t ",node.val)
}


// 广度优先级遍历，即逐层遍历
func levelOrder(node *Node){
    queue:=list.New()
    if node==nil{
        return
    }
    queue.PushBack(node)
    for queue.Len()!=0{
        e:=queue.Front()
        n:=e.Value.(*Node)
        fmt.Printf("%d\t ",n.val)
        queue.Remove(e)
        if n.left!=nil{
            queue.PushBack(n.left)
        }
        if n.right!=nil{
            queue.PushBack(n.right)
        }
    }
}




func main(){
    bst:=new(BST)
    bst.AddElement(7)
    bst.AddElement(3)
    bst.AddElement(10)
    bst.AddElement(1)
    bst.AddElement(5)
    bst.AddElement(9)
    bst.AddElement(12)
    bst.Traverse(preOrder)
    fmt.Println("前序")
    bst.Traverse(midOrder)
    fmt.Println("中序")
    bst.Traverse(backOrder)
    fmt.Println("后序")
    bst.Traverse(levelOrder)
    fmt.Println("逐层")

删除节点
节点处于不同的位置，删除的逻辑也不同
1. 删除的节点是叶子节点，直接删除即可
2. 删除的节点只有一个子节点，删除节点，并将唯一的子树节点上移
3. 删除的节点有左右子节点，删除节点，取该节点的左子树中最大的节点代替该节点，或者取右子树的最小的节点代替该节点

func (bst *BST) Remove(val int) {
    remove(bst.root, val)
}

func remove(node *Node, val int) *Node {
    if node == nil {
        return nil
    }
    //  遍历元素
    if node.val > val {
        // 遍历左子树
        node.left = remove(node.left, val)
        return node
    } else if node.val < val {
        // 遍历右子树
        node.right = remove(node.right, val)
        return node
    } else {
        //找到对应的元素，此时对应是叶子节点的，不做单独处理，处理逻辑可用只有一个子节点的逻辑
        if node.left == nil {
            // 删除节点只有右孩子节点
            right := node.right
            node.right = nil
            return right
        }
        if node.right == nil {
            // 删除的节点只有左孩子
            left := node.left
            node.left = nil
            return left
        }
        // 有左右子节点的， 这边采用找右子树的最小节点来代替
        minNode := minNode(node.right)
        // 将新的节点待替代删除的节点
        minNode.right = remove(node.right, minNode.val)
        minNode.left = node.left
        node.left = nil
        node.right = nil
        return minNode
    }
}