将二进制的高度添加到插入方法

Question

我正在创建一个程序，将字符（数字/字母）插入二进制树中。到目前为止，我能够产生输出，但这不是我所期望的。这些是我遇到的问题：

1. 插入方法无法打印树的正确高度。我不确定在哪里应该插入height ++;语句以获取正确的输出。

2. insert方法只能在右侧添加节点。

预期输出：ht = 3 [k = 3 l = [k = 1 r = [k = 2]] r = [k = 5 l = [k = 4]] < /p>

我的输出：ht = 4 [k = 3 r = [k = 1 r = [k = 2 r = [k = 5 r = [k = 4]]]

（全部节点仅添加到正确的“ r”）

这是我的课程：

主要类

BST<Character> bst = new BST<>();

bst.insert('3');
bst.insert('1');
bst.insert('2');
bst.insert('5');
bst.insert('4');

System.out.println("ht=" + bst.height + " " + bst.toString());

bst class - 其中插入声明

public class BST<T> extends BT<T> {
    // insert() method
    public void insert(char k) 
    {
        if (root == null) {
            root = new BTNode(k);
            return;
        }
        
        BTNode<T> n = root;
        BTNode<T> p = null; // parent
    
        while (n != null) {
            p = n;
            
            if (k < n.value) {
                n = n.left;
            } else {
                n = n.right;
            }
        }
        
        if (k < p.value) {
            p.left = new BTNode(k);
        } else {
            p.right = new BTNode(k);
            height++;   // adds 1 to height when a new level is made
        }
    }
}

btnode class

public class BTNode<T> {
    T info;
    int value, level;
    BTNode<T> left, right;
    
    public BTNode(T el) {
        this(el, null, null);
    }
    
    public BTNode(T el, BTNode<T> l, BTNode<T> r) {
        info = el;
        left = l;
        right = r;
    }
}

bt class - toString宣布

public class BT<T> {
    BTNode<T> root = null;
    int height = 0;
    
    public BT() {
        BTNode<T> node = new BTNode("");
    }
    
    // other methods
    
    // toString()
    public String toString() {
        return toString(root);
    }
    
    public String toString(BTNode<T> n) {
        String s = "";
        
        if (n == null) {
            return "";
        }
        
        if (n != null) {
            s = "[K=" + n.info;
            
            if (n.left != null) {
                s = s + " L=" + toString(n.left) + "]";
            }
            if (n.right != null) {
                s = s + " R=" + toString(n.right) + "]";
            }
        }
        return s;
    }
}

希望您可以帮助我，谢谢！

Answer 1

您的代码中有很多问题。我将列出一些即时项目，但您确实需要学习使用交互式调试器和单元测试来解决您所看到的各种问题。

1. 您在比较中参考value字段 btnode 中的字段，但永远不会设置它。您应该真正参考info（这是节点中的实际数据）。

2. 但是给定的信息是一种通用类型，您无法使用标准比较操作员。相反，您需要将其定义为＆lt; t扩展可比＆lt; t＆gt;＆gt;，然后使用n.info.compareto（k）＆gt; 0。

3. 传递到插入的密钥也应为类型t

4. ，这意味着其他类还需要确保t扩展可比性。。 P>

5. 当节点被添加到右侧时，高度才会增加。

仅当节点与根最大值插入更远时，才需要提高高度。如下：

int depth = 0;
while (n != null) {
    depth++;
    p = n;
...
}

depth++;
if (depth > height)
    height = depth;

您应该习惯使您的字段私密并通过Getters访问它们。在您的情况下，A compareValue方法可能很有意义。