如何打印二叉树的子树？

Question

在我的程序中，我已经初始化了一个二叉树，我想搜索该二叉树中是否存在一个节点。如果它确实存在，那么我将打印该节点的子树及其找到的级别。我能够执行我的 search 方法，但我不确定 如何打印找到的那个节点的子树及其级别 。

例如，这是我的二叉树[K=3 L=[K=1 R=[K=2]] R=[K=5 L=[K=4]]。如果我搜索节点 1，那么它将 return 节点（不为空），因为它存在于我的二叉树中。

Problem: I need to print only the subtree of the node and the level where it was found: [K=1 R=[K=2]], level=1.

这里是我的源代码供参考：

主要Class

// instantiate BST object
BST<Character> bst = new BST<>(); 

// insert values to bst1
String str = "31254";
char[] letter = str.toCharArray();

for (int i = 0; i < letter.length; i++) {
    Character c = letter[i];

    bst1.insert(c);
}

// print bst
System.out.println("\nht=" + bst1.height + " " + bst1.toString() + "\n");

// search values in bst1
String str2 = "016483"; 
char[] letter2 = str2.toCharArray();

for (int i = 0; i < letter2.length; i++) {
    Character c = letter2[i];
    
    if (bst1.search(c) != null) { // if found, print the node (w/ subtree) and its level
        // ** part that should print the subtree and its level
    }
    else {
        System.out.println(c + " is not found.");
    }
}

BST Class - 声明我的 search 方法的地方

public class BST<T extends Comparable<T>> extends BT<T> {
    // insert() method

    // search method
    public BTNode<T> search(T k) {// my method
        
            BTNode<T> n = root;
            
            while (n != null) {
                if (n.info.compareTo(k) == 0)  {
                    return n;
                }
                else {
                    if (n.info.compareTo(k) > 0) {
                        n = n.left;
                    }
                    else {
                        n = n.right;
                    }
                }
            }
            return null;
        }
}

提前致谢！

Answer 1

我没有修改你的代码。相反，我使用了我编写的虚构 class 节点。另外，我把它们都写成了半伪半java代码。假设你的节点只有一个int类型变量和两个子节点。

class Node{
    int data;
    Node left;
    Node right;
}

您的 BST class 中有一个 printExistingSubTree 方法可以满足您的要求：

printExistingSubTree(Node node, int key):
    if (find(node.left, key, 0) != -1)
        then 
            printTree(node.left)
            print(find(node.left, key, 0))
    if (find(node.right, key, 0) != -1)
        then printTree(node.right)
            printTree(node.right)
            print(find(node.right, key, 0))

您的 BST class 中有一个 find 方法可以找到索引：

int find(Node node,int key, int level)
    if(node.data is equal to the key)
        then return level
    int left = -1;
    
    if(node.leftChild is not null)
        then left = find(node.left, key, level+1)
    if(left != -1)
        return left
    int right = -1;
    if(node.rightChild is not null)
        then right = find(node.right, key, level+1)
    return right

然后，要打印，您应该决定要如何遍历子树。

你的 BST class 中有一个 printTree 方法，它在 postorder:

中打印子树

void printTree(Node node){
    if (node == null)
        return;
     printTree(node.left);
 
     printTree(node.right);
 
     print(node.data + " ");
}

注意：我没看懂你的全部代码。因此，我刚刚以伪代码格式写下了您问题的答案。我认为，您可以从中编写自己的代码。

注2：可能会有一些错别字和错误的命名。请不要私刑。请在评论中写下，我会更正。

如何打印二叉树的子树？

How to print a subtree of a binary tree?

java

tree

binary-tree

subtree

binary-search-tree