go语言判断一棵树是否是二叉搜索树

点击个人博客，查看更多文章https://elonjelinek.github.io

二叉搜索树主要用来实现搜索操作，二叉搜索树在最坏情况下平均搜索和插入的时间复杂度为O(log n)。

在二叉搜索树中，所有左子树的节点的元素小于根节点数据，所有右子树的节点的元素大于根节点数据，并且树中的每个节点都满足该性质。

1. 左子树所有节点的值均小于它的根节点的值；
2. 右子树所有节点的值均大于它的根节点的值；
3. 任意节点的左右子树也分别为二叉搜索树。

二叉树的声明与一般树的声明没有区别，唯一的区别在于数据而不是结构，声明如下

type Tree struct {
    Value int
    Left  *Tree
    Right *Tree
}

判断一棵树是否为二叉搜索树的思路为：将所有节点的值用中序遍历追加到一个数组中，然后判断这个数组是否是递增数组，如果是递增数组，那么这棵树为二叉搜索树，否则不是二叉搜索树，具体实现如下：

声明一个全局数组

var arr []int

用中序遍历把所有节点的值追加到数组中

func inOrder(Tree *Tree) []int {
    if Tree != nil {
        inOrder(Tree.Left)
        arr = append(arr, Tree.Value)
        inOrder(Tree.Right)
    }
    return arr
}

判断是否为递增数组

func isBinaryTree(tree *Tree) bool {

    arr := inOrder(tree)

    for i := 0; i < len(arr)-1; i++ {
        if arr[i] <= arr[i+1] {
            continue
        } else {
            return false
        }
    }

    return true
}

用插入节点的方式生成一个二叉搜索树

func (t *Tree) Insert(value int) {
    Tree := new(Tree)
    Tree.Value = value
    if t == nil {
        t = Tree
    } else {
        insertTree(t, Tree)
    }
}

func insertTree(Tree, newTree *Tree) {
    if newTree.Value < Tree.Value {
        if Tree.Left == nil {
            Tree.Left = newTree
        } else {
            insertTree(Tree.Left, newTree)
        }
    } else {
        if Tree.Right == nil {
            Tree.Right = newTree
        } else {
            insertTree(Tree.Right, newTree)
        }
    }
}

下面分别创建两棵树，第一棵为二叉搜索树，第二棵不是，第二棵树的根节点为11，其左节点为9，右节点为12，9的左节点为7，右节点为13，这里左子树的最右节点为13，大于根节点的右节点12，所以不是二叉搜索树。
其中第二棵树的结构如图

func main() {
    t := new(Tree)
    t.Value = 8
    t.Insert(4)
    t.Insert(5)
    t.Insert(9)
    t.Insert(7)
    t.Insert(10)
    t.Insert(3)

    var tree1 = new(Tree)
    var tree2 = new(Tree)
    tree3 := new(Tree)
    tree4 := new(Tree)
    tree5 := new(Tree)
    tree1.Value = 11
    tree2.Value = 9
    tree3.Value = 7
    tree4.Value = 13
    tree5.Value = 12

    tree1.Left = tree2
    tree1.Right = tree5
    tree2.Left = tree3
    tree2.Right = tree4

    fmt.Println(isBinaryTree(t))
    fmt.Println(isBinaryTree(tree1))

    fmt.Println("中序遍历第一棵树")
    printTree(t)
    fmt.Println()
    fmt.Println("中序遍历第二棵树")
    printTree(tree1)

}

运行结果

true
false
中序遍历第一棵树
3   4   5   7   8   9   10  
中序遍历第二棵树
7   9   13  11  12  

完整代码

package main

import (
    "fmt"
)

type Tree struct {
    Value int
    Left  *Tree
    Right *Tree
}

var arr []int

func inOrder(Tree *Tree) []int {
    if Tree != nil {
        inOrder(Tree.Left)
        arr = append(arr, Tree.Value)
        inOrder(Tree.Right)
    }
    return arr
}

func (t *Tree) Insert(value int) {
    Tree := new(Tree)
    Tree.Value = value
    if t == nil {
        t = Tree
    } else {
        insertTree(t, Tree)
    }
}

func insertTree(Tree, newTree *Tree) {
    if newTree.Value < Tree.Value {
        if Tree.Left == nil {
            Tree.Left = newTree
        } else {
            insertTree(Tree.Left, newTree)
        }
    } else {
        if Tree.Right == nil {
            Tree.Right = newTree
        } else {
            insertTree(Tree.Right, newTree)
        }
    }
}

func isBinaryTree(tree *Tree) bool {

    arr := inOrder(tree)

    for i := 0; i < len(arr)-1; i++ {
        if arr[i] <= arr[i+1] {
            continue
        } else {
            return false
        }
    }

    return true
}

func printTree(tree *Tree) {
    if tree != nil {
        printTree(tree.Left)
        fmt.Print(tree.Value, "\t")
        printTree(tree.Right)
    }
}

func main() {
    t := new(Tree)
    t.Value = 8
    t.Insert(4)
    t.Insert(5)
    t.Insert(9)
    t.Insert(7)
    t.Insert(10)
    t.Insert(3)

    var tree1 = new(Tree)
    var tree2 = new(Tree)
    tree3 := new(Tree)
    tree4 := new(Tree)
    tree5 := new(Tree)
    tree1.Value = 11
    tree2.Value = 9
    tree3.Value = 7
    tree4.Value = 13
    tree5.Value = 12

    tree1.Left = tree2
    tree1.Right = tree5
    tree2.Left = tree3
    tree2.Right = tree4

    fmt.Println(isBinaryTree(t))
    fmt.Println(isBinaryTree(tree1))

    fmt.Println("中序遍历第一棵树")
    printTree(t)
    fmt.Println()
    fmt.Println("中序遍历第二棵树")
    printTree(tree1)

}

点击个人博客，查看更多文章https://elonjelinek.github.io