将二叉树的高度添加到insert方法中

Question

我正在创建一个将字符 (number/letter) 插入二叉树的程序。到目前为止，我能够生成输出，但这不是我所期望的。这些是我遇到的问题：

insert 方法无法打印正确的 height 树。我不确定应该在哪里插入我的 height++; 语句以获得正确的输出。
insert方法只能在右侧添加节点

Expected Output: ht=3 [K=3 L=[K=1 R=[K=2]] R=[K=5 L=[K=4]]]

My Output: ht=4 [K=3 R=[K=1 R=[K=2 R=[K=5 R=[K=4]]]]

(所有节点只加到右边'R')

下面是我的类供参考：

主要Class

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 - insert 方法声明的地方

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

您的代码中有不少问题。我将列出一些直接的项目，但您确实需要学习使用交互式调试器和单元测试来解决您遇到的各种问题。

您在比较中引用了 BTNode 中的 value 字段，但从未设置过。你真的应该指的是 info （这是节点中的实际数据）。
但是鉴于 info 是泛型类型，您不能使用标准比较运算符。相反，您需要将其定义为 <T extends Comparable<T>> 然后使用 n.info.compareTo(k) > 0.
传入insert的key也应该是T
类型
这意味着另一个类也需要确保T扩展Comparable.
高度只有在向右添加节点时才会增加，这是没有意义的。

仅当插入的节点距根的距离超过当前最大值时，才需要增加高度。类似于以下内容：

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

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

您应该习惯将您的字段设为私有并通过 getters 访问它们。在您的情况下，compareValue 方法可能有意义。

将二叉树的高度添加到insert方法中

Adding height of binary tree to insert method

java

binary-tree

insert

tostring

binary-search