【数据结构08】二叉树、顺序存储二叉树、线索二叉树详解及Java实现

二叉树

树

数组的优点是通过下标访问元素效率比较高、对于有序数组，还可以通过二分法提高检索效率，而缺点是，插入、删除时，会整体移动一部分数据，效率较低

链式存储优点则是插入删除时，效率很高，而检索效率比较低

这时，树应运而生。树，能够提高数据存储、检索的效率。二叉树既可以保证数据的检索效率，也保证了插入删除的效率

一些概念

满二叉树：所有叶子节点都在最后一层，且节点数=2^n-1,n为层数。

完全二叉树：所有叶子节点都在最后一层或者倒数第二层。且最后一层在左边连续，倒数第二层叶子在右边连续。

遍历

遍历顺序：

前序：根节点、左子节点、右子节点

中序：左子节点、根节点、右子节点

后序：左子节点、右子节点、根节点

如图所示二叉树，前序遍历结果：ABDECF

如图所示二叉树，中序遍历结果：DBEAFC

如图所示二叉树，后序遍历结果：DEBFCA

实现思路

二叉树的每个节点，除了存储数据之外，还需要有两个域指向它的左右节点。

而二叉树的遍历，可以用递归的方法来实现。

以前序遍历举例，开始，需要先将父节点（一开始的父节点是根节点）输出，然后向左递归【输出父节点、向左递归、向右递归】，完成后向右递归输出父节点即可。

代码实现

package tree;

public class TreeNode {

    private int id;
    private TreeNode left;
    private TreeNode right;

    @Override
    public String toString() {
        return "TreeNode{" +
                "id=" + id +
                '}';
    }

    public TreeNode(int id) {
        this.id = id;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    //前序遍历
    public void preOrder(){
        //输出父节点
        System.out.println(this);
        //遍历左子树
        if (this.left != null){
            this.left.preOrder();
        }
        //遍历右子树
        if (this.right != null) {
            this.right.preOrder();
        }
    }
    //中序遍历
    public void midOrder(){
        //遍历左子树
        if (this.left != null){
            this.left.midOrder();
        }
        //输出父节点
        System.out.println(this);
        //遍历右子树
        if (this.right != null) {
            this.right.midOrder();
        }
    }
    //后序遍历
    public void postOrder(){

        //遍历左子树
        if (this.left != null){
            this.left.postOrder();
        }
        //遍历右子树
        if (this.right != null) {
            this.right.postOrder();
        }
        //输出父节点
        System.out.println(this);
    }
    //前序查找
    public TreeNode preOrderSearch(int id){
        if (this.id == id){
            return this;
        }
        TreeNode resultNode = null;
        if (this.left != null){
            resultNode = this.left.preOrderSearch(id);
        }
        if (resultNode!=null){
            return resultNode;
        }
        //遍历右子树
        if (this.right != null) {
            resultNode = this.right.preOrderSearch(id);
        }
        return resultNode;
    }
    //中序查找
    public TreeNode midOrderSearch(int id){
        TreeNode resultNode = null;
        if (this.left != null){
            resultNode = this.left.preOrderSearch(id);
        }
        if (resultNode!=null){
            return resultNode;
        }
        if (this.id == id){
            return this;
        }
        //遍历右子树
        if (this.right != null) {
            resultNode = this.right.preOrderSearch(id);
        }
        return resultNode;
    }
    //后序查找
    public TreeNode postOrderSearch(int id){
        TreeNode resultNode = null;
        if (this.left != null){
            resultNode = this.left.preOrderSearch(id);
        }
        if (resultNode!=null){
            return resultNode;
        }
        //遍历右子树
        if (this.right != null) {
            resultNode = this.right.preOrderSearch(id);
        }
        if (this.id == id){
            return this;
        }
        return resultNode;
    }
    //删除节点
    public void deleteNode(int id){
        if ( this.left != null && this.left.id == id ){
            this.left = null;
            return;
        }
        if ( this.right != null && this.right.id == id ){
            this.right = null;
            return;
        }
        if (this.left != null){
            this.left.deleteNode(id);
        }
        if (this.right != null){
            this.right.deleteNode(id);
        }
    }
}

package tree;


import sun.reflect.generics.tree.Tree;

public class BinaryTree {
    private TreeNode root;

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

    //前序遍历
    public void preOrder(){
        if (root != null){
            root.preOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }
    //中序遍历
    public void midOrder(){
        if (root != null){
            root.midOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }
    //后序遍历
    public void postOrder(){
        if (root != null){
            root.postOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }
    //前序查找
    public TreeNode preOrderSearch(int id){
        return root.preOrderSearch(id);
    }
    //中序查找
    public TreeNode midOrderSearch(int id){
        return root.midOrderSearch(id);
    }
    //后序查找
    public TreeNode postOrderSearch(int id){
        return root.postOrderSearch(id);
    }
    public void deleteNode(int id){
        root.deleteNode(id);
    }
}

package tree;

public class BinaryTreeTest {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        BinaryTree binaryTree = new BinaryTree(root);
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        node4.setLeft(node6);

        System.out.println("前序遍历");
        binaryTree.preOrder();
        System.out.println("中序遍历");
        binaryTree.midOrder();
        System.out.println("后序遍历");
        binaryTree.postOrder();
        System.out.println("前序查找");
        TreeNode result1 = binaryTree.preOrderSearch(3);
        System.out.println(result1);
        System.out.println("中序查找");
        TreeNode result2 = binaryTree.midOrderSearch(4);
        System.out.println(result2);
        System.out.println("后序查找");
        TreeNode result3 = binaryTree.postOrderSearch(4);
        System.out.println(result3);
        System.out.println("前序遍历");
        binaryTree.preOrder();
        System.out.println("删除5");
        binaryTree.deleteNode(5);
        binaryTree.preOrder();
        System.out.println("删除4");
        binaryTree.deleteNode(4);
        binaryTree.preOrder();

    }
}

顺序存储二叉树

概述

将二叉树存储在一个数组中，通过存储元素的下标反映元素之间的父子关系。

下标为 i 的元素的左子节点是：2i + 1；
下标为 i 的元素的右子节点是：2i + 2；
下标为 i 的元素的父节点是：（i - 1）/ 2；

如图这样一个二叉树顺序存储就是这样的： [1, 2, 3, 4, 5, 6, 7 ]

其中1为根节点，下标为0，所以的左子节点下标为 2 * 0 + 1 = 1，也就是2为它的左子节点

5的下标为4，所以他的父节点的下标为(4 - 1) / 2 = 1，也就是2是它的父节点。

代码实现

package tree;

public class ArrayBinaryTree {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7};
        ArrayBinaryTree tree = new ArrayBinaryTree(array);
        tree.preOrder(0);
    }

    private int [] binaryTree;

    public ArrayBinaryTree(int[] binaryTree) {
        this.binaryTree = binaryTree;
    }

    //前序遍历
    public void preOrder(int i){
        if (binaryTree == null) {
            System.out.println("二叉树为空");
        }
        //输出父节点
        System.out.println(binaryTree[i]);
        //遍历左子树
        if (2*i+1 < binaryTree.length){
            preOrder(2*i+1);
        }
        //遍历右子树
        if (2*i+2 < binaryTree.length){
            preOrder(2*i+2);
        }
    }
}

线索二叉树

概述

在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。

对于二叉树来说，它的叶子节点的左右指针域得不到利用，造成了浪费。而线索就是，将这些空指针域左指针指向它遍历的前趋节点，右指针指向它的后继节点。

对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

注意：线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解决了二叉链表找左、右孩子困难的问题。

如上图所示，以前序遍历举例，此二叉树前序遍历为 A B D C E F，其中，B的左指针为空 而B的前趋节点为A，则可以让B的左指针指向A，D的左右指针都为空，它的前趋节点为B后继节点为C，则可以让其左右指针分别指向BC，其余有左右指针域为空的节点同理。