Back to
top
二叉树的操作 - 杨挺的博客 | Tommy's Blog

二叉树的操作

"Operation of Binary Tree"

Posted by Tommy on April 15, 2019

二叉树的操作

二叉树的相关介绍,这是之前在学习二叉树的遍历方式的时候的相关总结,有需要的可以看一看。现在我们主要说说二叉树的操作:包括创建二叉树(在二叉树的介绍中有提到),添加结点,删除结点,清空二叉树,获取二叉树的高度,获取二叉树的父节点,获取二叉树的结点数等。下面我们将通过代码一一介绍。

二叉树的添加结点

添加节点分为添加左节点和添加右节点

    /**
     * 添加左结点
     *
     * @param child 添加该结点到左子树
     */
    public void setLeftChild(BinaryTreeNode child) {
        this.root.setLeftNode(child);
    }

    /**
     * 添加右结点
     *
     * @param child 添加该结点到右子树
     */
    public void setRightChild(BinaryTreeNode child) {
        this.root.setRightNode(child);
    }

删除节点

删除节点,可以删除指定节点,获取清空整个二叉树 删除指定节点

    /**
     * 删除结点
     *
     * @param node 删除该节点
     * @return
     */
    public void deleteNode(BinaryTreeNode node) {
        if (node == null) {
            return;
        }

        deleteNode(node.getLeftNode());
        deleteNode(node.getRightNode());
        node = null;
    }

清空二叉树 则只用将清空的指定结点换成二叉树的根节点即可

    /**
     * 清空二叉树
     *
     * @return
     */

    public void clear() {
        if (this.root != null) {
            this.deleteNode(this.root);
        }
    }

获取树高

二叉树中,树的高度是各个节点度的最大值。 因此获得树的高度需要递归获取所有节点的高度,然后取最大值。

获取指定节点的高度

    /**
     * 获取二叉树指定结点的高度
     *
     * @param node 获取该节点的高度
     */
    public int getHeight(BinaryTreeNode node) {
        if (node == null) {
            return 0;
        }

        return Math.max(getHeight(node.getLeftNode()), getHeight(node.getRightNode())) + 1;
    }

获取树高

    /**
     * 获取二叉树的高度
     *
     * @return int
     */
    public int getTreeHeight() {
        return this.getHeight(this.root);
    }

获取节点数

获得二叉树的节点数,需要遍历所有子树,然后加上总和。

获取指定节点的节点数

    /**
     * 获取二叉树指定节点的节点个数(包括指定节点)
     *
     * @param node 获取该节点的节点数
     * @return int
     */
    public int getChildSize(BinaryTreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftSize = getChildSize(node.getLeftNode());
        int rightSize = getChildSize(node.getRightNode());

        return leftSize + rightSize + 1;
    }

获取树的节点数

    /**
     * 获取二叉树的节点数
     *
     * @return int
     */
    public int getSize() {
        return this.getChildSize(this.root);
    }

获取指定节点的父亲节点

由于我们使用左右子树表示的节点,不含有父亲节点引用,因此有时候可能也需要一个方法,返回二叉树中,指定节点的父亲节点; 需要从顶向下遍历各个子树,若该子树的根节点的孩子就是目标节点,返回该节点,否则递归遍历它的左右子树。

    /**
     * 获取指定节点的父亲节点
     *
     * @param node
     * @return BinaryTreeNode
     */
    public BinaryTreeNode getParent(BinaryTreeNode node) {
        if (this.root == null || this.root == node) {
            return null;
        }
        return getParent(this.root, node);
    }

    /**
     * 递归对比 节点的孩子节点 与 指定节点 是否一致
     *
     * @param subTree 子二叉树根节点
     * @param node    指定节点
     * @return
     */
    public BinaryTreeNode getParent(BinaryTreeNode subTree, BinaryTreeNode node) {
        if (subTree == null){
            return null;
        }

        if (subTree.getLeftNode() == node || subTree.getRightNode() == node){
            return subTree;
        }

        BinaryTreeNode parent;
        if((parent = getParent(subTree.getLeftNode(), node)) != null){
            return parent;
        }

        return getParent(subTree.getRightNode(), node);
    }

总结

以上式二叉树的相关操作,二叉树的遍历。 有问题大家可以在下面讨论,有错误可以指出。谢谢!