Java 打印二叉搜索树的顶视图

Question

给出的问题：给定一个指向二叉树根的指针，打印二叉树的顶视图。从节点顶部看到的树称为树的顶视图。

这是我为树的顶视图编写的代码。我的代码是运行仅适用于某些情况。我想知道我写的代码有什么问题。

我的想法是为每个节点提供索引，并且只会打印获得特定索引的第一个节点。

 public static void rhs(Node root,int index,ArrayList list){
        if(root==null){
            return;
        }
        for (int i=0;i<list.size();i++){
            if (index==list.get(i)){
               rhs(root.left,index-1,list);
               rhs(root.right,index+1,list);
               return;
            }
        }
         System.out.print(root.data+" ");
                list.add(index);
                rhs(root.left,index-1,list);
                rhs(root.right,index+1,list); 
    }

public static void topView(Node root) {
    if (root==null){
        return;
    }
    ArrayList<Integer> list=new ArrayList<>();
    list.add(0);
 
    System.out.print(root.data+" ");

    rhs(root.left,-1,list);
  
    rhs(root.right,1,list);         


}

它不起作用的一个案例是 -

15
1 14 3 7 4 5 15 6 13 10 11 2 12 8 9

预期输出（顺序无关紧要）：

2 1 14 15 12

我的输出：

1 14 2 6 12

已经预定义，无法更改-

public static Node insert(Node root, int data) {
        if(root == null) {
            return new Node(data);
        } else {
            Node cur;
            if(data <= root.data) {
                cur = insert(root.left, data);
                root.left = cur;
            } else {
                cur = insert(root.right, data);
                root.right = cur;
            }
            return root;
        }
    }
public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int t = scan.nextInt();
    Node root = null;
    while(t-- > 0) {
        int data = scan.nextInt();
        root = insert(root, data);
    }
    scan.close();
    topView(root);
}

}

Answer 1

// Java program to print top
// view of binary tree
import java.util.LinkedList;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.TreeMap;
 
// class to create a node
class Node {
    int data;
    Node left, right;
 
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}
 
// class of binary tree
class BinaryTree {
    Node root;
 
    public BinaryTree() { root = null; }
 
    // function should print the topView of
    // the binary tree
    private void TopView(Node root)
    {
        class QueueObj {
            Node node;
            int hd;
 
            QueueObj(Node node, int hd)
            {
                this.node = node;
                this.hd = hd;
            }
        }
        Queue<QueueObj> q = new LinkedList<QueueObj>();
        Map<Integer, Node> topViewMap
            = new TreeMap<Integer, Node>();
 
        if (root == null) {
            return;
        }
        else {
            q.add(new QueueObj(root, 0));
        }
 
        System.out.println(
            "The top view of the tree is : ");
 
        // count function returns 1 if the container
        // contains an element whose key is equivalent
        // to hd, or returns zero otherwise.
        while (!q.isEmpty()) {
            QueueObj tmpNode = q.poll();
            if (!topViewMap.containsKey(tmpNode.hd)) {
                topViewMap.put(tmpNode.hd, tmpNode.node);
            }
 
            if (tmpNode.node.left != null) {
                q.add(new QueueObj(tmpNode.node.left,
                                   tmpNode.hd - 1));
            }
            if (tmpNode.node.right != null) {
                q.add(new QueueObj(tmpNode.node.right,
                                   tmpNode.hd + 1));
            }
        }
        for (Entry<Integer, Node> entry :
             topViewMap.entrySet()) {
            System.out.print(entry.getValue().data);
        }
    }
 
    // Driver Program to test above functions
    public static void main(String[] args)
    {
        /* Create following Binary Tree
            1
        / \
        2 3
        \
            4
            \
            5
            \
                6*/
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.right = new Node(4);
        tree.root.left.right.right = new Node(5);
        tree.root.left.right.right.right = new Node(6);
        System.out.println(
            "Following are nodes in top view of Binary Tree");
        tree.TopView(tree.root);
    }
}

Answer 2

您的代码的问题在于，它假定当您在 第一次 时间到达某个索引时，这也将具有从最佳。这在在那一刻肯定是正确的，但可能会发生稍后访问的节点可能会在相同的索引处结束，和在树中更高，因此隐藏了先前可见的节点。

这是一个小例子：

index:   -1  0  1

tree:        4
            / \
           1   5
            \
             2
              \
               3

对于这棵树，你的算法会先处理根的左子树，所以先访问3 然后 5，所以你会输出“3”对于索引 1.

因此，要解决此问题，您实际上应该避免输出任何内容，直到您遍历了整棵树。在遍历时将值和深度与每个索引相关联（可能使用 Map），并在你有一个新的候选者具有更小的深度值时更新关联值。

Java 打印二叉搜索树的顶视图

Java print top view of binary search tree

java

algorithm

data-structures

tree

binary-search-tree