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

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()));

}

node==null当你应该返回0时,你正在返回-1 .

当我们到达叶子时条件为真,例如,如果我们加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实现实际上是一个二叉搜索树,因为你在左边放了更少的元素,在右边放了更大的元素,如果你的意图是搜索树,那么Ok,但如果你想实现一般的二叉树,那么你应该改变添加功能.