前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >判断一棵树是否是搜索二叉树

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

作者头像
名字是乱打的
发布2022-05-13 09:51:01
1580
发布2022-05-13 09:51:01
举报
文章被收录于专栏:软件工程

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

思想:

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

代码实现

代码语言:javascript
复制
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));
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-05-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 思想:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档