判断一棵树是否是搜索二叉树

名字是乱打的

发布于 2022-05-13 01:51:01

18500

代码可运行

文章被收录于专栏：软件工程软件工程

运行总次数：0

代码可运行

搜索二叉树它是一种节点值之间具有一定数量级次序的二叉树，对于树中每个节点：若其左子树存在，则其左子树中每个节点的值都不大于该节点值；若其右子树存在，则其右子树中每个节点的值都不小于该节点值。

思想:

实际上只要树的中序遍历结果是升序的,那么其就是搜索二叉树

代码实现

package com.algorithm.practice.tree;
import java.util.Stack;

public class SearchTreeJudge {
    public static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node parent;

        public Node(int data) {
            this.value = data;
        }
    }
    public static boolean InOrderJudgeSearch(Node head){
        int falg=Integer.MIN_VALUE;
        if (head!=null){
            Stack<Node> stack=new Stack<>();
            while (!stack.isEmpty()||head!=null){
                if (head!=null){
                    stack.push(head);
                    head=head.left;
                }else {
                    head=stack.pop();
                    if (head.value>falg){
                        falg=head.value;
                    }else {
                        return false;
                    }
                    head=head.right;
                }
            }
        }
        return true;
    }
    public static void main(String[] args){
        Node head = new Node(4);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.left.left.left = new Node(1);
        head.right.left = new Node(7);
        head.right.left.left = new Node(6);
        head.right.right = new Node(10);
        head.right.right.left = new Node(9);
        head.right.right.right = new Node(11);
        System.out.println( InOrderJudgeSearch(head));
    }
}