关于二叉树

/ 数据结构与算法 / 3 条评论 / 1843浏览

提示:完整代码放在了我的 gitee 上面

定义

在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作左子树右子树

性质

二叉树的每个结点至多只有二棵子树(不存在度大于 2 的结点),二叉树的子树有左右之分,次序不能颠倒;

二叉树的第 i 层至多有 2i-1 个结点;

深度为 k 的二叉树至多有 2k-1 个结点;

优点

在实际使用时会根据链表和有序数组等数据结构的不同优势进行选择。

有序数组的优势在于二分查找,链表的优势在于数据项的插入和数据项的删除。

但是在有序数组中插入数据就会很慢,同样在链表中查找数据项效率就很低。

综合以上情况,二叉树可以利用链表和有序数组的优势,同时可以合并有序数组和链表的优势,二叉树也是一种常用的数据结构。

缺点

可以看出插入和删除速度都快。

二叉树的缺点是,不能随机访问。

定义二叉树的节点

首先定义二叉树的节点。

代码

public class TreeNode {

    private final char value;
    private TreeNode left;
    private TreeNode right;
    private TreeNode parent;

    public TreeNode(char value) {
        this.value = value;
        this.left = null;
        this.right = null;
        this.parent = null;
    }

    public char getValue() {
        return value;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
        if (this.left != null) {
            // 为左节点赋值时,将自己作为其父母节点
            this.left.setParent(this);
        }
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
        if (this.right != null) {
            this.right.setParent(this);
        }
    }

    public TreeNode getParent() {
        return parent;
    }

    private void setParent(TreeNode parent) {
        this.parent = parent;
    }
}

建立二叉树

如图,以这是一棵二叉树。

代码

public class TreeCreator {

    public TreeNode createSampleTree() {
        TreeNode root = new TreeNode('A');
        root.setLeft(new TreeNode('B'));
        root.getLeft().setLeft(new TreeNode('D'));
        root.getLeft().setRight(new TreeNode('E'));
        root.getLeft().getRight().setLeft(new TreeNode('G'));
        root.setRight(new TreeNode('C'));
        root.getRight().setRight(new TreeNode('F'));
        return root;
    }

二叉树的遍历

对这棵二叉树进行前序、中序、后序遍历。

前序遍历

中序遍历

后序遍历

代码

public class TreeTraversal {
    /**
     * 前序
     *
     * @param root
     */
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.getValue() + " ");
        preOrder(root.getLeft());
        preOrder(root.getRight());
    }

    /**
     * 中序
     *
     * @param root
     */
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.getLeft());
        System.out.print(root.getValue() + " ");
        inOrder(root.getRight());
    }

    /**
     * 后序
     *
     * @param root
     */
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.getLeft());
        postOrder(root.getRight());
        System.out.print(root.getValue() + " ");
    }
}

测试用例

    public static void main(String[] args) {
        TreeCreator creator = new TreeCreator();
        TreeTraversal traversal = new TreeTraversal();
        TreeNode sampleTree = creator.createSampleTree();

        System.out.print("前序遍历: ");
        traversal.preOrder(sampleTree);
        System.out.println();

        System.out.print("中序遍历: ");
        traversal.inOrder(sampleTree);
        System.out.println();

        System.out.print("后序遍历: ");
        traversal.postOrder(sampleTree);
    }

例一 根据前序和中序构造二叉树

分析

代码

    /**
     * 已知前序和中序遍历构造二叉树
     *
     * @param preOrder 前序
     * @param inOrder  中序
     * @return 后序
     */
    public TreeNode createTree(String preOrder, String inOrder) {
        if (preOrder.isEmpty()) {
            return null;
        }

        char rootValue = preOrder.charAt(0);
        int rootIndex = inOrder.indexOf(rootValue);
//        int leftLength = rootIndex;
        TreeNode root = new TreeNode(rootValue);
        root.setLeft(createTree(
                // substring 从1开始跳过根节点,到1+rootIndex为左子树
                preOrder.substring(1, 1 + rootIndex),
                // 根节点在中序遍历中的下标即为左子树长度
                inOrder.substring(0, rootIndex)));
        root.setRight(createTree(
                // 剩下的元素即为右子树
                preOrder.substring(1 + rootIndex),
                inOrder.substring(1 + rootIndex))
        );
        return root;
    }

这里需要说明的是:

测试用例

    public static void main(String[] args) {
        TreeCreator creator = new TreeCreator();
        TreeTraversal traversal = new TreeTraversal();

        TreeNode tree = creator.createTree("ABDEGCF", "DBGEACF");
        traversal.postOrder(tree);
        System.out.println();
        traversal.postOrder(creator.createTree("", ""));
        System.out.println();
        traversal.postOrder(creator.createTree("A", "A"));
        System.out.println();
        traversal.postOrder(creator.createTree("AB", "BA"));
    }

总结

例二 寻找中序遍历时的下一个节点

分析

遍历示意图如下:

代码

public class InOrder {

    public TreeNode getNext(TreeNode node) {
        if (node == null) {
            return null;
        }

        if (node.getRight() != null) {
            return first(node.getRight());
        } else {
            while (node.getParent() != null && node.getParent().getRight() == node) {
                node.getParent();
            }
            // node.getParent() == null || node is left child of its parent
            return node.getParent();
        }
    }

    public TreeNode first(TreeNode node) {
        if (node == null) {
            return null;
        }

        TreeNode curNode = node;
        while (curNode.getLeft() != null) {
            curNode = curNode.getLeft();
        }
        return curNode;
    }

    public void traverse(TreeNode root) {
        for (TreeNode node = first(root);
             node != null;
             node = getNext(node)) {
            System.out.print(node.getValue());
        }
        System.out.println();
    }
}

总结

  1. 膜拜大佬 orz

  2. 可以可以!

  3. 很不错!很有帮助!