我的二叉树是否正确添加了节点？

Question

我刚刚创建了一个方法来测试我的二叉树实现的高度，如下所示：

public int height() {
    return height(rootNode);
}
private int height(BinaryTreeNode node) {
    if(node == null) return -1;
    else return 1 + Math.max(height(node.getLeftChild()), height(node.getRightChild()));
}

但是当我添加节点 1-6 时，它 returns 高度为 6，而不是 7。

这是我的二叉树代码：

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree<E extends Comparable<E>>
{
    private class BinaryTreeNode
    {
        private E value;
        private BinaryTreeNode leftChild, rightChild;

        public BinaryTreeNode(E value) {
            this(value, null, null);
        }

        public BinaryTreeNode(E value, BinaryTreeNode leftChild, BinaryTreeNode rightChild) {
            this.value = value;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }

        public E getValue() {
            return value;
        }

        public BinaryTreeNode getLeftChild() {
            return leftChild;
        }

        public BinaryTreeNode getRightChild() {
            return rightChild;
        }

        public void setLeftChild(BinaryTreeNode newLeftChild) {
            this.leftChild = newLeftChild;
        }

        public void setRightChild(BinaryTreeNode newRightChild) {
            this.rightChild = newRightChild;
        }
    }

    private BinaryTreeNode rootNode;

    public BinaryTree() {
        this.rootNode = null;
    }

    public void addNode(E value) {
        if(rootNode == null)
            rootNode = new BinaryTreeNode(value);
        else
            addNode(value, rootNode);
    }

    //TODO: Implement removeNode()

    public void printLevelOrder() {
        printLevelOrder(rootNode);
    }

    public int height() {
        return height(rootNode);
    }

    public void inOrderTraversal() {
        if(rootNode != null) inOrderTraversal(rootNode);
        else System.out.println("The tree is empty!");
    }

     private void addNode(E value, BinaryTreeNode node) {
        if(node.getValue().compareTo(value) > 0) {
            if(node.getLeftChild() != null)
                addNode(value, node.getLeftChild());
            else
                node.setLeftChild(new BinaryTreeNode(value));
        } else {
            if(node.getRightChild() != null)
                addNode(value, node.getRightChild());
            else
                node.setRightChild(new BinaryTreeNode(value));
        }
    }

    private void printLevelOrder(BinaryTreeNode node) {
        Queue<BinaryTreeNode> currentLevel = new LinkedList<BinaryTreeNode>();
        Queue<BinaryTreeNode> nextLevel = new LinkedList<BinaryTreeNode>();

        currentLevel.add(node);

        while (!currentLevel.isEmpty()) {
            Iterator<BinaryTreeNode> iter = currentLevel.iterator();
            while (iter.hasNext()) {
                BinaryTreeNode currentNode = iter.next();
                if (currentNode.leftChild != null) {
                    nextLevel.add(currentNode.leftChild);
                }
                if (currentNode.rightChild != null) {
                    nextLevel.add(currentNode.rightChild);
                }
                System.out.print(currentNode.value + " ");
            }
            System.out.println();
            currentLevel = nextLevel;
            nextLevel = new LinkedList<BinaryTreeNode>();

        }
    }

    private int height(BinaryTreeNode node) {
        if(node == null) return -1;
        else return 1 + Math.max(height(node.getLeftChild()), height(node.getRightChild()));
    }

    private void inOrderTraversal(BinaryTreeNode node) {
        if(node != null) {
            inOrderTraversal(node.leftChild);
            System.out.println(node.getValue() + " ");
            inOrderTraversal(node.getRightChild());
        }
    }

    public BinaryTreeNode getRoot() {
        return rootNode;
    }
}

我认为问题出在将我的节点添加到树中，但我查看了其他示例，但它们似乎都在做同样的事情。所以我无法意识到问题所在！

谢谢！

Answer 1

private int height(BinaryTreeNode node) {
if(node == null) return 0;
else return 1 + Math.max(height(node.getLeftChild()), height(node.getRightChild()));

}

你在 node==null 上 returning -1 而你应该 return 0。

当我们到达叶子时，条件为真，例如，如果我们添加 1-2，那么我们的高度为 1+Max(leftof(1),rightof(1))=
1+Max(height(null),height(2))=
1+Max(0,1+Max(leftof(2),rightof(2)))=
1+Max(0,1+Max(height(null),height(null)))=
1+Max(0,1+Max(0,0))=
1+Max(0,1+0)=
1+1=2。

尝试把前面例子中的height(null)换成-1自己看

顺便说一下，您的 BinaryTree 实现实际上是一个二叉搜索树，因为您将较少的元素放在左侧，将较大的元素放在右侧，如果搜索树是您的意图，那么可以，但是如果您想实现一个一般二叉树那么你应该改变添加功能。

我的二叉树是否正确添加了节点？

Is my Binary Tree adding nodes properly?

java

binary-tree