时间戳

首页 > 解决方案 > 在二叉树中打印无法通过二分搜索搜索到的节点

java - 在二叉树中打印无法通过二分搜索搜索到的节点

问题描述

我正在尝试打印所有无法通过二叉搜索算法搜索的二叉树节点。由于 BST 也基于二进制搜索算法，所以我试图打印不符合 BST 结构的节点。

下面的代码片段在右叶值大于根的根的情况下失败，例如：

public class PrintBinarySearchable {
    static class Node {
        int key, height;
        Node left, right;

        public Node(int d) {
            key = d;
            left = right = null;
        }
    }

    Node prev;

    private void printSearchable(Node node, Node prev, boolean isRight) {
        if (node == null)
            return;
        if (prev == null)
            System.out.print(node.key + " ");

        printSearchable(node.left, node, false);

        if (!isRight && prev != null && node.key < prev.key)
            System.out.print(node.key + " ");

        if (isRight && prev != null && node.key > prev.key)
            System.out.print(node.key + " ");

        printSearchable(node.right, node, true);

    }

    public static void main(String[] args) {
        Node root = new Node(7);
        root.left = new Node(2);
        root.right = new Node(9);
        root.left.left = new Node(1);
        root.left.right = new Node(51);

        PrintBinarySearchable tree = new PrintBinarySearchable();
        tree.printSearchable(root);
    }

    private void printSearchable(Node root) {
        printSearchable(root, null, false);
    }
}

标签： javabinary-treebinary-search

解决方案

这感觉像是一项家庭作业，所以我不会在这里给出完整的答案。相反，我会给你一些关于如何解决这个问题的提示。

  • 与其担心一个节点是左还是右以及它的父节点是什么来确定它是否可搜索，不如从父节点进行检查。如果您有父级，则可以确定其子代是否可搜索。
  • 如果您是从父级做出决定，则递归中不需要特殊情况 - 只需调用printSearchable(node.right);and printSearchable(node.left)within printSearchable。然后你可以打电话printSearchable(root)，它会打印所有的节点。

推荐阅读