Java教程

算法笔记-判断是否二叉搜索树

本文主要是介绍算法笔记-判断是否二叉搜索树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

  二叉搜索树定义:二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

  我们来看一下定义:左子树小于父节点小于右子树,这咋和我之前的二叉树中序遍历一样的呢,通俗解释:二叉树中序遍历是有序增长的。

  这样就简单了啊,我都遍历出来了,遍历的时候顺带比较一下前后大小是否一一增长不就行了吗,代码:

/**
     * 中序遍历
     * @param head
     */
    public static boolean inOrderUnRecur(Node head) {

        if(head != null) {
            Stack<Node> stack = new Stack<>();
            int pre= Integer.MIN_VALUE;
            while(!stack.empty() || head != null){
                if(head != null){
                    stack.push(head);
                    head = head.left;
                }else{
                    head = stack.pop();
                    if(head.value < pre){
                        return false;
                    }
                    pre = head.value;
                    head = head.right;
                }
            }
            System.out.println();
        }
        return true;
    }

这里我增加了一个变量,记录一下前置节点的值,在原来打印的地方比较一下是否完全符合增长逻辑,一旦不符合直接返回失败,这是非递归方式的修改,递归方式的要复杂一点:

public static boolean inOrderRecur(Node head) {

        boolean[] isBST = new boolean[1];
        isBST[0] = true;
        inOrderRecur(head,new int[]{Integer.MIN_VALUE},isBST);
        return isBST[0];
    }

    /**
     * 中序遍历
     * @param head
     */
    public static void inOrderRecur(Node head, int[] pre, boolean[] isBST) {
        if (head == null) {
            return;
        }
        inOrderRecur(head.left,pre,isBST);
        System.out.print(head.value + " ");
        if(pre[0] > head.value){
            isBST[0] = false;
        }
        pre[0] = head.value;
        inOrderRecur(head.right,pre,isBST);
    }

道理是差不多的,只不过我多加了一个标识是否是搜索树,这里前置节点pre一开始我用的是int变量,后来测试发现有问题,又理了一遍,发现如下图所示2和7所在的节点其实都是使用left节点递归进入的,虽然我修改了pre的值,但是回到节点2其实还是初始的值,因此必须使用一个全局变量形式的值来保存,因此改为数组形式或者任意形式的全局唯一变量都可以。

 

这篇关于算法笔记-判断是否二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!