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

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 时，它返回高度 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()));

}

当您应该返回 0 时，您在 node==null 上返回 -1。

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

尝试将上例中的height(null)替换为-1，自己看看。

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