数据结构（一）二叉树

作者: 又语 | 来源:发表于2021-11-02 20:46 被阅读0次

二叉树（Binary Tree）是n个有限元素的集合，该集合或者为空，或者由一个称为根（root）的元素及两个不相交的、被称为左子树和右子树的二叉树组成，是有序树。在二叉树中，一个元素也称作一个节点。
二叉树（Binary Tree）又指树中节点的度不大于2的有序树。

二叉树有两种特殊类型：

满二叉树（Full Binary Tree）是高度为k，且拥有(2^k)-1个节点的二叉树。一颗满二叉树每个节点，要么都有两棵子树，要么都没有子树。
完全二叉树（Complete Binary Tree，假设完全二叉树高度为k）遵循以下规则：
- 所有叶子节点都出现在k层或k-1层，并且从1 ~ k-1层必须达到最大节点数；
- 第k层可以是不满的，但是第k层的所有节点必须集中在最左边。

Java 代码实现

1. 二叉树定义

首先，定义树节点，参考附录部分第一段代码。
其次，定义树：

public class BinaryTree {
    
    private BinaryTreeNode root;

    public BinaryTree() {
    }

    public BinaryTree(BinaryTreeNode root) {
        this.root = root;
    }

    // Getter & Setter 略
}

2. 清空二叉树

首先，定义一个清空某节点下子树的方法，利用递归删除每个节点。
然后，定义一个删除树的方法。

    /**
     * 清空以某个节点为根节点的子树及当前节点的方法，既递归地删除每个节点
     */
    public void clear(BinaryTreeNode node) {
        if (node != null) {
            clear(node.getLeftChild());
            clear(node.getRightChild());
            // 删除节点
            node = null;
        }
    }

    /**
     * 清空二叉树
     */
    public void clear() {
        clear(this.root);
    }

3. 判断树是否为空

只需要判断根节点是否存在。

    /**
     * 判断二叉树是否为空
     */
    public boolean isEmpty() {
        return this.root == null;
    }

4. 获取树高度

    /**
     * 获取以某节点为根节点的子树的高度，包括当前节点
     */
    public int height(BinaryTreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftHeight = height(node.getLeftChild());
        int rightHeight = height(node.getRightChild());
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

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

5. 求节点数

    /**
     * 获取以某节点为根节点的所有子节点数，包括当前节点
     */
    public int size(BinaryTreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + size(node.getLeftChild()) + size(node.getRightChild());
    }

    /**
     * 获取二叉树全部节点数
     */
    public int size() {
        return size(this.root);
    }

6. 返回父节点

    /**
     * 给定一个子树subTree，获取某节点在此子树中的父节点
     */
    public BinaryTreeNode getParent(BinaryTreeNode subTree, BinaryTreeNode node) {
        if (subTree == null) {
            return null;
        }
        if (subTree.getLeftChild() == node || subTree.getRightChild() == node) {
            return subTree;
        }
        BinaryTreeNode parent = getParent(subTree.getLeftChild(), node);
        return parent != null ? parent : getParent(subTree.getRightChild(), node);
    }

    /**
     * 获取某节点在二叉树中的父节点
     */
    public BinaryTreeNode getParent(BinaryTreeNode node) {
        return (this.root == null || this.root == node) ? null : getParent(this.root, node);
    }

7. 返回左右子树

    /**
     * 获取某节点的左子树
     */
    public BinaryTreeNode getLeftTree(BinaryTreeNode node) {
        return node.getLeftChild();
    }

    /**
     * 获取某节点的右子树
     */
    public BinaryTreeNode getRightTree(BinaryTreeNode node) {
        return node.getRightChild();
    }

8. 插入

    /**
     * 给某节点插入左子节点
     */
    public void insertLeftChild(BinaryTreeNode parent, BinaryTreeNode newLeftChild) {
        parent.setLeftChild(newLeftChild);
    }

    /**
     * 给某节点插入右子节点
     */
    public void insertRightChild(BinaryTreeNode parent, BinaryTreeNode newRightChild) {
        parent.setRightChild(newRightChild);
    }

9. 遍历

9.1 前序遍历

考察到一个节点后，即刻输出该节点的值，并继续遍历其左右子树。(根左右)

    /**
     * 前序遍历（递归实现）
     */
    public void preOrderTraversalRecursion(BinaryTreeNode node) {
        if (node != null) {
            System.out.println(node.getData());
            preOrderTraversalRecursion(node.getLeftChild());
            preOrderTraversalRecursion(node.getRightChild());
        }
    }

    /**
     * 前序遍历（非递归实现）
     */
    public void preOrderTraversal(BinaryTreeNode node) {
        // 用以暂存节点的栈
        Stack<BinaryTreeNode> nodeStack = new Stack<>();
        // 新建一个节点赋值为待遍历的节点
        BinaryTreeNode temp = node;
        // 当遍历到最后一个节点时，无论其左右子树，又或是节点栈，都应该为空
        while (temp != null || !nodeStack.isEmpty()) {
            while (temp != null) {
                System.out.println(temp.getData());
                nodeStack.push(temp);
                temp = temp.getLeftChild();
            }
            if (!nodeStack.isEmpty()) {
                temp = nodeStack.pop();
                temp = temp.getRightChild();
            }
        }
    }

9.2 中序遍历

考察到一个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树。(左根右)

    /**
     * 中序遍历（递归实现）
     */
    public void inOrderTraversalRecursion(BinaryTreeNode node) {
        inOrderTraversalRecursion(node.getLeftChild());
        System.out.println(node.getData());
        inOrderTraversalRecursion(node.getRightChild());
    }

    /**
     * 中序遍历（非递归实现）
     */
    public void inOrderTraversal(BinaryTreeNode node) {
        Stack<BinaryTreeNode> nodeStack = new Stack<>();
        BinaryTreeNode temp = node;
        while (temp != null || !nodeStack.isEmpty()) {
            while (temp != null) {
                nodeStack.push(temp);
                temp = temp.getLeftChild();
            }
            if (!nodeStack.isEmpty()) {
                temp = nodeStack.pop();
                System.out.println(temp.getData());
                temp = temp.getRightChild();
            }
        }
    }

9.3 后序遍历

后序：考察到一个节点后，将其暂存，遍历完左右子树后，再输出该节点的值。(左右根)

    /**
     * 后续遍历（递归实现）
     */
    public void postOrderTraversalRecursion(BinaryTreeNode node) {
        if (node != null) {
            postOrderTraversalRecursion(node.getLeftChild());
            postOrderTraversalRecursion(node.getRightChild());
            System.out.println(node.getData());
        }
    }

    /**
     * 后续遍历（非递归实现）
     */
    public void postOrderTraversal(BinaryTreeNode node) {
        Stack<BinaryTreeNode> nodeStack = new Stack<>();
        BinaryTreeNode temp = node;
        BinaryTreeNode lastVisit = node;
        while (temp != null || !nodeStack.isEmpty()) {
            while (temp != null) {
                nodeStack.push(temp);
                temp = temp.getLeftChild();
            }
            // 查看当前栈顶元素
            temp = nodeStack.peek();
            // 如果其右子树也为空，或右子树已经访问，则可以直接输出当前节点的值
            if (temp.getRightChild() == null || temp.getRightChild() == lastVisit) {
                System.out.println(temp.getData());
                nodeStack.pop();
                lastVisit = temp;
                temp = null;
            } else {
                temp = temp.getRightChild();
            }
        }
    }

附：完整代码

二叉树节点

/**
 * 二叉树的左右链表表示法
 */
public class BinaryTreeNode {

    private int data;
    private BinaryTreeNode leftChild;
    private BinaryTreeNode rightChild;

    // Getter & Setter 略
    // hashCode & equals 略
}

二叉树

public class BinaryTree {
    
    private BinaryTreeNode root;

    public BinaryTree() {
    }

    public BinaryTree(BinaryTreeNode root) {
        this.root = root;
    }

    /**
     * 清空以某个节点为根节点的子树及当前节点的方法，既递归地删除每个节点
     */
    public void clear(BinaryTreeNode node) {
        if (node != null) {
            clear(node.getLeftChild());
            clear(node.getRightChild());
            // 删除节点
            node = null;
        }
    }

    /**
     * 清空二叉树
     */
    public void clear() {
        clear(this.root);
    }

    /**
     * 判断二叉树是否为空
     */
    public boolean isEmpty() {
        return this.root == null;
    }

    /**
     * 获取以某节点为根节点的子树的高度，包括当前节点
     */
    public int height(BinaryTreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftHeight = height(node.getLeftChild());
        int rightHeight = height(node.getRightChild());
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

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

    /**
     * 获取以某节点为根节点的所有子节点数，包括当前节点
     */
    public int size(BinaryTreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + size(node.getLeftChild()) + size(node.getRightChild());
    }

    /**
     * 获取二叉树全部节点数
     */
    public int size() {
        return size(this.root);
    }

    /**
     * 给定一个子树subTree，获取某节点在此子树中的父节点
     */
    public BinaryTreeNode getParent(BinaryTreeNode subTree, BinaryTreeNode node) {
        if (subTree == null) {
            return null;
        }
        if (subTree.getLeftChild() == node || subTree.getRightChild() == node) {
            return subTree;
        }
        BinaryTreeNode parent = getParent(subTree.getLeftChild(), node);
        return parent != null ? parent : getParent(subTree.getRightChild(), node);
    }

    /**
     * 获取某节点在二叉树中的父节点
     */
    public BinaryTreeNode getParent(BinaryTreeNode node) {
        return (this.root == null || this.root == node) ? null : getParent(this.root, node);
    }

    /**
     * 获取某节点的左子树
     */
    public BinaryTreeNode getLeftTree(BinaryTreeNode node) {
        return node.getLeftChild();
    }

    /**
     * 获取某节点的右子树
     */
    public BinaryTreeNode getRightTree(BinaryTreeNode node) {
        return node.getRightChild();
    }

    /**
     * 给某节点插入左子节点
     */
    public void insertLeftChild(BinaryTreeNode parent, BinaryTreeNode newLeftChild) {
        parent.setLeftChild(newLeftChild);
    }

    /**
     * 给某节点插入右子节点
     */
    public void insertRightChild(BinaryTreeNode parent, BinaryTreeNode newRightChild) {
        parent.setRightChild(newRightChild);
    }

    /**
     * 前序遍历（递归实现）
     */
    public void preOrderTraversalRecursion(BinaryTreeNode node) {
        if (node != null) {
            System.out.println(node.getData());
            preOrderTraversalRecursion(node.getLeftChild());
            preOrderTraversalRecursion(node.getRightChild());
        }
    }

    /**
     * 前序遍历（非递归实现）
     */
    public void preOrderTraversal(BinaryTreeNode node) {
        // 用以暂存节点的栈
        Stack<BinaryTreeNode> nodeStack = new Stack<>();
        // 新建一个节点赋值为待遍历的节点
        BinaryTreeNode temp = node;
        // 当遍历到最后一个节点时，无论其左右子树，又或是节点栈，都应该为空
        while (temp != null || !nodeStack.isEmpty()) {
            while (temp != null) {
                System.out.println(temp.getData());
                nodeStack.push(temp);
                temp = temp.getLeftChild();
            }
            if (!nodeStack.isEmpty()) {
                temp = nodeStack.pop();
                temp = temp.getRightChild();
            }
        }
    }

    /**
     * 中序遍历（递归实现）
     */
    public void inOrderTraversalRecursion(BinaryTreeNode node) {
        inOrderTraversalRecursion(node.getLeftChild());
        System.out.println(node.getData());
        inOrderTraversalRecursion(node.getRightChild());
    }

    /**
     * 中序遍历（非递归实现）
     */
    public void inOrderTraversal(BinaryTreeNode node) {
        Stack<BinaryTreeNode> nodeStack = new Stack<>();
        BinaryTreeNode temp = node;
        while (temp != null || !nodeStack.isEmpty()) {
            while (temp != null) {
                nodeStack.push(temp);
                temp = temp.getLeftChild();
            }
            if (!nodeStack.isEmpty()) {
                temp = nodeStack.pop();
                System.out.println(temp.getData());
                temp = temp.getRightChild();
            }
        }
    }

    /**
     * 后续遍历（递归实现）
     */
    public void postOrderTraversalRecursion(BinaryTreeNode node) {
        if (node != null) {
            postOrderTraversalRecursion(node.getLeftChild());
            postOrderTraversalRecursion(node.getRightChild());
            System.out.println(node.getData());
        }
    }

    /**
     * 后续遍历（非递归实现）
     */
    public void postOrderTraversal(BinaryTreeNode node) {
        Stack<BinaryTreeNode> nodeStack = new Stack<>();
        BinaryTreeNode temp = node;
        BinaryTreeNode lastVisit = node;
        while (temp != null || !nodeStack.isEmpty()) {
            while (temp != null) {
                nodeStack.push(temp);
                temp = temp.getLeftChild();
            }
            // 查看当前栈顶元素
            temp = nodeStack.peek();
            // 如果其右子树也为空，或右子树已经访问，则可以直接输出当前节点的值
            if (temp.getRightChild() == null || temp.getRightChild() == lastVisit) {
                System.out.println(temp.getData());
                nodeStack.pop();
                lastVisit = temp;
                temp = null;
            } else {
                temp = temp.getRightChild();
            }
        }
    }

    // Getter & Setter 略
    // hashCode & equals 略
}