二叉树与线索二叉树

树的概述

树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。形同下图。

树有如下基本概念：

• 根结点

  根结点是树的一个组成部分，也叫树根。每一颗树都有且仅有一个根结点。它是同一棵树中除本身外所有结点的祖先，没有父结点。按上图的树结构来看，根节点就是 1。

• 父结点

  也叫双亲结点，一个结点如果有上一级，则称这个上一级是它的父结点，如果没有上一级，则该结点无父结点。按上图的树结构来看，可以说是父节点有 1、2、3、5、6、22。

• 子结点

  一个结点如果有下一级，则称这个下一级是它的子结点，如果没有下一级，则该结点无子结点。按上图的树结构来看，其实除了根结点以外，各个结点都是它们对应父结点的子结点。

• 路径

  从根结点访问其他结点所需要经过的结点。比如从 1 要走到 31，则路径是 1、3、31。

• 结点的度

  一个结点拥有多少个子结点，就认为它的度是多少。比如根结点 1，它的度就是 5。

• 结点的权

  结点的权值，图中每个结点都有对应的数字，这些数字就是对应结点的权。

• 叶子结点

  没有子结点的结点，按上图的树结构来看，叶子结点有 21、221、222、223、31、51、52、61。

• 子树

  还是上图，试着把结点 2 单独拿出来看，会发现它和它的子结点也能构成树结构。这颗树在整颗大的树里边，所以称为子树。

• 层

  结点的层次从根开始定义起，根为第一层，根的孩子是二层，依次累计。上图的树结构层次就是 4。

• 树的高度

  树的最大层数，上图的树结构最大层数就是从根结点开始，到最底层的叶子结点，高度是 4。

• 森林

  多个树组成的集合，想象现在有好多颗树，每一颗树结构不一，它们共同构成森林。

二叉树的概述

任何子结点的数量都不超过 2，就是一颗二叉树。比如之前举例的图，明显就不是二叉树。二叉树的子结点分左结点和右结点，不能随意颠倒位置。

二叉树也有分类：

• 满二叉树

  所有叶子结点都在最后一层，而且结点总数为 2^n - 1，n 是树的高度。

  

• 完全二叉树

  所有叶子结点都在最后一层或倒数第二层，且最后一层叶子结点在左边延续，倒数第二层的叶子结点在右边连续。即最后一层的叶子结点总是从左往右，倒数第二层总是从右到左。满二叉树也是一颗完全二叉树。

  

链式存储的二叉树

顾名思义，用链表的方式去实现二叉树结构。用代码去实现，首先我们要创建一个结点类。

public class TreeNode {
    // 节点的权
    private int value;
    // 左子结点
    private TreeNode leftNode;
    // 右子结点
    private TreeNode rightNode;

    public TreeNode(int value) {
        this.value = value;
    }
	// 剩下的都是 set/get 方法了
    ...
}

其次，和链表有头结点一样，二叉树也需要有根结点辅助操作，作为创建二叉树的基础。

public class BinaryTree {

    private TreeNode root;

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }
}

万事具备，向根结点添加左右子结点即可。

public class TestBinaryTree {

    public static void main(String[] args) {
        // 创建二叉树
        BinaryTree binaryTree = new BinaryTree();
        // 创建根结点
        TreeNode root = new TreeNode(1);
        // 设置根结点
        binaryTree.setRoot(root);
        // 创建一个左结点
        TreeNode rootL = new TreeNode(2);
        // 把新创建的结点设置为根结点的左子结点
        root.setLeftNode(rootL);
        // 创建一个右结点
        TreeNode rootR = new TreeNode(3);
        // 把新创建的结点设置为根结点的右子结点
        root.setRightNode(rootR);
        // 为第二层的左结点创建两个子结点
        rootL.setLeftNode(new TreeNode(4));
        rootL.setRightNode(new TreeNode(5));
        // 为第二层的右结点创建两个子结点
        rootR.setLeftNode(new TreeNode(6));
        rootR.setRightNode(new TreeNode(7));
    }
}

遍历二叉树

二叉树的遍历方式有三种，分别是：前序遍历、中序遍历、后序遍历。

以上图为例，记住一点，所谓的前序、中序、后序都是参考当前结点的位置。前序遍历，即是先取当前结点的权，然后是它的左子结点，最后是右子结点。从根结点开始，遍历过程中每一个结点都要遵守这个规矩。

因此上图前序遍历得到的结果是：1、2、4、5、3、6、7；中序遍历得到的结果是：4、2、5、1、6、3、7；后序遍历得到的结果是：4、5、2、6、3、7、1。代码实现用到递归的思想。

public class TestBinaryTree {

    public static void main(String[] args) {
        // 之前创建二叉树的代码，这里就省略不写了
        ...
        // 前序遍历树
        binaryTree.frontShow();
        System.out.println("-----------------");
        // 中序遍历树
        binaryTree.midShow();
        System.out.println("-----------------");
        // 后序遍历树
        binaryTree.afterShow();
    }
}

public class BinaryTree {

    private TreeNode root;

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    // 前序遍历
    public void frontShow() {
        if (root != null) {
        	root.frontShow();
        }
    }

    // 中序遍历
    public void midShow() {
        if (root != null) {
        	root.midShow();
        }
    }

    // 后序遍历
    public void afterShow() {
        if (root != null) {
        	root.afterShow();
        }
    }
}

public class TreeNode {

    // 节点的权
    private int value;
    // 左子结点
    private TreeNode leftNode;
    // 右子结点
    private TreeNode rightNode;

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

    // set/get 方法
	...

    // 前序遍历
    public void frontShow() {
        // 先输出当前结点内容
        System.out.println(value);
        // 输出左结点内容
        if (leftNode != null) {
            leftNode.frontShow();
        }
        // 输出右结点内容
        if (rightNode != null) {
            rightNode.frontShow();
        }
    }

    // 中序遍历
    public void midShow() {
        // 输出左结点内容
        if (leftNode != null) {
            leftNode.midShow();
        }
        // 输出当前结点内容
        System.out.println(value);
        // 输出右结点内容
        if (rightNode != null) {
            rightNode.midShow();
        }
    }

    // 后序遍历
    public void afterShow() {
        // 输出左结点内容
        if (leftNode != null) {
            leftNode.afterShow();
        }
        // 输出右结点内容
        if (rightNode != null) {
            rightNode.afterShow();
        }
        // 输出当前结点内容
        System.out.println(value);
    }
}

二叉树中结点的查找

查找结点，实际就是把整颗二叉树遍历一次，依次比对，找出结果并返回。这里以前序查找为例，其余的大同小异。

public class TestBinaryTree {

    public static void main(String[] args) {
		// 创建二叉树
        ...
        // 前序查找
        TreeNode result = binaryTree.frontSearch(5);
        System.out.println(result);
    }
}

public class BinaryTree {

    private TreeNode root;

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    /**
     * 前序查找
     * @return 目标结点
     */
    public TreeNode frontSearch(int value) {

        return root.frontSearch(value);
    }
}

public class TreeNode {

    // 节点的权
    private int value;
    // 左子结点
    private TreeNode leftNode;
    // 右子结点
    private TreeNode rightNode;

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

    /**
     * 前序查找
     * @return 目标结点
     */
    public TreeNode frontSearch(int value) {
        TreeNode target = null;
        // 返回本结点
        if (this.value == value) {
            return this;
        }
        // 向左子结点方向查找
        if (leftNode != null) {
            target = leftNode.frontSearch(value);
        }
        // 如果不为空，证明找到结点，返回
        if (target != null) {
            return target;
        }
        // 向右子结点方向查找
        if (rightNode != null) {
            target = rightNode.frontSearch(value);
        }
        return target;
    }
}

删除二叉树的结点

对于一颗普通的二叉树而言，删除一个结点就等同于把对应的整颗子树一并删掉。之后讲到二叉排序树时，就不是这样操作了。

删除时要区分是根结点还是其他结点。如果是根结点的话，直接置为 null 就好了。但如果不是，则依次比较左右两个子结点，符合就直接置为 null。如果都不符合，那就递归调用左右结点的 delete 方法。

public class TestBinaryTree {

    public static void main(String[] args) {
		// 创建一颗子树
        ...
        // 删除一个结点
        binaryTree.delete(5);
        binaryTree.frontShow();
    }
}

public class BinaryTree {

    private TreeNode root;

	...

    /**
     * 根据权值删除结点
     * @param value 依据权值
     */
    public void delete(int value) {
        // 要删除的是根结点
        if (root.getValue() == value) {
            root = null;
        } else {
            // 要删除的是其他结点
            root.delete(value);
        }
    }
}

public class TreeNode {

    // 节点的权
    private int value;
    // 左子结点
    private TreeNode leftNode;
    // 右子结点
    private TreeNode rightNode;

	...

    /**
     * 根据权值删除结点
     * @param value 依据权值
     */
    public void delete(int value) {
        TreeNode parent = this;
        // 判断左子结点
        if (parent.leftNode != null && parent.leftNode.value == value) {
            parent.leftNode = null;
            return;
        }
        // 判断右子结点
        if (parent.rightNode != null && parent.rightNode.value == value) {
            parent.rightNode = null;
            return;
        }
        parent = leftNode;
        if (parent != null) {
            parent.delete(value);
        }
        parent = rightNode;
        if (parent != null) {
            parent.delete(value);
        }
    }
}

顺序存储的二叉树

二叉树还可以用数组实现，或者说，任意一个数组都可以转化为二叉树。就上图二叉树而言，它对应的数组实现就是 [1,2,3,4,5,6,7]。

并不是每颗二叉树都长得这么规矩，有可能会出现缺胳膊少腿的情况。通常情况下，顺序存储的二叉树只考虑完全二叉树（满二叉树也是完全二叉树），否则没有意义。

顺序存储的二叉树还有其对应的性质公式，常用的有如下三个：

• 数组中第 n 个元素的左子结点下标为：2*n + 1
• 数组中第 n 个元素的左子结点下标为：2*n + 2
• 数组中第 n 个元素的父节点下标为：(n-1)/ 2

顺序存储的二叉树的遍历

我们把一个数组当成二叉树作前序遍历，剩下的中序和后序遍历也大同小异了。

public class TestBinaryTree {

    public static void main(String[] args) {
		
        int[] data = new int[]{1, 2, 3, 4, 5, 6, 7};
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(data);
        // 前序遍历
        arrayBinaryTree.frontShow();

    }
}

public class ArrayBinaryTree {

    private int[] data;

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

    public int[] getData() {
        return data;
    }

    public void setData(int[] data) {
        this.data = data;
    }

    public void frontShow() {
        frontShow(0);
    }

    public void frontShow(int index) {
        if (data == null || data.length == 0) {
            return;
        }
        // 先遍历当前结点的内容
        System.out.println(data[index]);
        // 遍历左子结点
        if (2 * index + 1 < data.length) {
            frontShow(2 * index + 1);
        }
        // 遍历右子结点
        if (2 * index + 2 < data.length) {
            frontShow(2 * index + 2);
        }
    }
}

线索二叉树

可以发现，无论二叉树的形态如何，总会有一些结点（尤其是叶子结点）的域是没有被使用的（左右子树为空）。为了提高利用率，让原来的空域存放指针，指向树中其他结点，这种指针称为线索。

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

以中序遍历为例，经过中序线索化的二叉树应该具有如下结构：对于非子结点的域，左域指向自身的前一个结点，右域指向自身的后一个结点

使用 Java 实现的线索二叉树如下：

/**
 * 结点类
 */
public class ThreadedNode {

    int value;
    // 左子结点
    ThreadedNode left;
    // 右子结点
    ThreadedNode right;
    // 标识指针类型，为 0 表示指向左/右子结点，为 1 表示指向前驱/后继结点
    int leftType;
    int rightType;

    public ThreadedNode(int value) {
        this.value = value;
    }

	...
}

public class ThreadedBinaryTree {

    private ThreadedNode root;

    // 用于临时存储前驱结点
    private ThreadedNode pre;

    public ThreadedNode getRoot() {
        return root;
    }

    /**
     * 设置根结点
     */
    public void setRoot(ThreadedNode root) {
        this.root = root;
    }

    /**
     * 线索化二叉树
     */
    public void threadNodes() {
        threadNodes(root);
    }

    public void threadNodes(ThreadedNode node) {
        // 当前结点为 null，直接返回
        if (node == null) {
            return;
        }
        // 处理左子树
        threadNodes(node.left);
        // 处理前驱结点
        if (node.left == null) {
            // 让当前结点的左指针指向前驱结点
            node.left = pre;
            // 改变当前结点左指针的类型
            node.leftType = 1;
        }
        // 处理前驱结点的右指针，如果前驱结点的右指针是 null（没有指向右子树）
        if (pre != null && pre.right == null) {
            // 让前驱结点的右指针指向当前结点
            pre.right = node;
            // 改变前驱结点的右指针类型
            pre.rightType = 1;
        }
        // 每处理一个结点，当前结点就是下一个结点的前驱结点
        pre = node;
        // 处理右子树
        threadNodes(node.right);
    }

    /**
     * 遍历线索二叉树
     */
    public void threadIterate() {
        // 用于临时存储当前遍历结点
        ThreadedNode node = root;
        while (node != null) {
            // 循环找到最开始的结点
            while (node.leftType == 0) {
                node = node.left;
            }
            // 打印当前结点的值
            System.out.println(node.value);
            // 如果当前结点的右指针指向的是后继结点，可能后继结点之后还有后继结点
            while (node.rightType == 1) {
                node = node.right;
                System.out.println(node.value);
            }
            node = node.right;
        }
    }

    /**
     * 中序遍历
     */
    public void midShow() {
        if (root != null) {
            root.midShow();
        }
    }
}