本文共 1818 字，大约阅读时间需要 6 分钟。

顺序存储二叉树——线索化二叉树

问题引入

二叉树并不是每一个指针都能够都能完全被利用上，叶子节点的两个指针都没有被引用，为空。希望充分利用其所有指针，在二叉树的顺序存储结构中用其剩余指针分切指向某种遍历顺序下前驱节点和后继节点

• 在上图中所有橙色的引线即为没有指向任何对象的空指针
• 空引用数量 n + 1，n为所共有的节点数
• 总共的引用数量 2 * n，
• 非空的引用数量 n - 1，每两个之间都有一个。

问题解答

• 根据中序遍历的方式得到输出顺序，然后用空的引用，按照中序遍历的顺序将彼此之间相互连续起来。这就是顺序存储二叉树的线索化
• 每一个节点的引用有如下情况：
  • left指向左子结点，也可能指向其在对应次序下的前驱结点
  • right指向右子节点，也可能指向其在对应次序下的后继结点。

基本介绍

• 前驱指针：按照固定的遍历顺序，在某个节点的前一个结点，称之为前驱指针
• 后继指针：按照固定的遍历顺序，在某个节点的后一个节点，称之为后继指针。
• 线索:在n个结点的二叉链表中含有n+1个空指针域，利用二叉链表中的空指针域，存放指向该节点在某种遍历次序下的前驱和后继结点的指针称之为线索。
• 线索链表：加上了线索的二叉链表称之为线索链表，相应的二叉树称之为线索二叉树。根据线索的顺序不同，线索二叉树分为：前序线索二叉树，中序线索二叉树，后序线索二叉树。

代码实现

public HeroArrangement pre = null;public void threadedNotes(HeroArragement node){
           //为什么要传入对应的节点，线索化不应该是所有的结点都进行线索化吗        if (node == null){
               return;        }        //先线索化左子树        threadedNotes(node.getLeft());        //线索化当前节点        //先处理当前节点的前驱节点        if(node.getLeft() == null){
               //让当前节点的左指针指向前驱节点            node.setLeft(pre);            //修改左指针的数据类型            node.setLeftType(1);        }        //处理后继节点，在递归的时候由下一次处理        if(pre != null && pre.getRight() == null){
               //让前驱指针的右指针位当前指针，因为递归的单向性，            // 所以必须单向来改变他的值，不可以及改变左边的指针，又改变右边的指针            pre.setRight(node);            pre.setRightType(1);        }        //每处理一个节点，让当前节点是下一个节点的前驱节点        //迭代的条件        pre = node;        //再线索化右子树        threadedNotes(node.getRight());    }

class HeroArragement{
       private int heroNo;    private String heroName;    HeroArragement left;    HeroArragement right;    //因为指针有不同的情况，所以设置变量    //说明：    //LeftType == 0,表示指向左子树，如果是1，标志指向前驱节点    //RightType == 0，表示指向右子树，如果是1，表示指向后继节点    private int leftType;    private int RightType;    ...    }

分析与总结

1. 递归的顺序就是按照中序遍历，结束条件是是否已经到叶子节点，到了叶子节点再将前后空的指针连起来。
2. 遍历具有单向性，所以只能用当前指针的左指针链接上一个节点。故而设置一个辅助结点，pre，其总是先于当前节点。用pre的右指针链接当前结点。

转载地址：http://pqgpb.baihongyu.com/