java - 二叉搜索树 - Java

Question

嘿，大家好，我对深度(查找二叉树的深度)和 printTree(按顺序打印树)有问题。这是我的代码。

import java.util.LinkedList;
import java.util.Queue;

public class BSTDictionary<T1, T2>{

private static class Node<T>{
    public Node<T> left;
    public Node<T> right;
    public T data;
    public Node(T data)
    {
        this.data = data;
    }
    public Node<T> getLeft()
    {
        return this.left;
    }
    public void setLeft(Node<T> left)
    {
        this.left = left;
    }
    public Node<T> getRight()
    {
        return this.right;
    }
    public void setRight(Node<T> right)
    {
        this.right = right;
    }
}

public int depth(Node root){

    if(root == null) {
        return 0;
    }
    else return 1 + Math.max((root.getLeft(), root.getRight());
}

public void printTree(){

    Node<?> n;
    Queue<Node<?>> nodequeue = new LinkedList<Node<?>>();
    while (!nodequeue.isEmpty())
    {
        Node<?> next = nodequeue.remove();
        System.out.print(next.data + " ");
        if (next.getLeft() != null)
        {
            nodequeue.add(next.getLeft());
        }
        if (next.getRight() != null)
        {
            nodequeue.add(next.getRight());
        }
    }}}

这是我为测试这些方法而提供的 Test 类。

    public class DictionaryAdvancedTest {
protected static String[] entries = new String[26 * 26];

protected static void fill() {
    // Insert 26 * 26 entries
    for (int i = 0; i < 26; i++)
        for (int j = 0; j < 26; j++) {
            StringBuffer s = new StringBuffer();
            s.append((char) ((int) 'A' + i));
            s.append((char) ((int) 'A' + j));
            entries[i * 26 + j] = s.toString();
        }
} // fill method

public static void main(String[] args) {
    BSTDictionary<String, SortableString> dict1 = new BSTDictionary<String, SortableString>();
    AVLDictionary<String, SortableString> dict2 = new AVLDictionary<String, SortableString>();

    // Insert lots of entries
    fill();
    for (int i = 0; i < 26 * 26; i++) {
        int e;
        do {
            e = (int) (Math.random() * (26 * 26));
        } while (entries[e] == null);

        dict1.insert(new SortableString(entries[e]), entries[e]);
        dict2.insert(new SortableString(entries[e]), entries[e]);
        entries[e] = null;
    }

    // print the two dictionaries
    dict1.printTree();
    dict2.printTree();
    // print the depth
    System.out.println("The initial BST tree has a maximum depth of "
            + dict1.depth());
    System.out.println("The initial AVL tree has a maximum depth of "
            + dict2.depth());

    // Delete half the entries
    fill();
    for (int i = 0; i < 13 * 26; i++) {
        int e;
        do {
            e = (int) (Math.random() * (26 * 26));
        } while (entries[e] == null);

        dict1.delete(new SortableString(entries[e]));
        dict2.delete(new SortableString(entries[e]));
    }

    System.out
            .println("After deletes, the BST tree has a maximum depth of "
                    + dict1.depth());
    System.out
            .println("After deletes, the AVL tree has a maximum depth of "
                    + dict2.depth());

    // Add a quarter the entries
    fill();
    for (int i = 0; i < 6 * 26; i++) {
        int e;
        do {
            e = (int) (Math.random() * (26 * 26));
        } while (entries[e] == null);

        dict1.insert(new SortableString(entries[e]), entries[e]);
        dict2.insert(new SortableString(entries[e]), entries[e]);
    }

    System.out
            .println("After insertions, the BST tree has a maximum depth of "
                    + dict1.depth());
    System.out
            .println("After insertions, the AVL tree has a maximum depth of "
                    + dict2.depth());

    // Search for a few random entries
    fill();
    for (int i = 0; i < 6; i++) {
        int e;
        do {
            e = (int) (Math.random() * (26 * 26));
        } while (entries[e] == null);

        System.out.print("Searching for " + entries[e] + ": ");
        if (dict1.search(new SortableString(entries[e])) == null) {
            System.out.print("Not found in Dict1, ");
        } else {
            System.out.print("Found in Dict1, ");
        }
        if (dict2.search(new SortableString(entries[e])) == null) {
            System.out.println("not found in Dict2.");
        } else {
            System.out.println("found in Dict2.");
        }
    }
}} 

谢谢大家:)

Answer 1

public int depth(Node root){

if(root == null) {
    return 0;
}
else return 1 + Math.max((root.getLeft(), root.getRight());
}

将最后一行替换为else return 1 + Math.max(深度(root.getLeft()), height(root.getRight()));

其余消息来自搜索功能，您未将其包含在问题中。