线索二叉树

浅谈线索二叉树的诞生

　　二叉树的存储结构的类型有：顺序存储、二叉链表存储、三叉链表存储、线索链表存储(树结构如图所示)。

　　

1、顺序结构

　　假设是顺序结构，它将为上述节点按照层序编号。

　　在二叉树中，设I为结点的层序编号存在如下性质。

　　若I>1，则它的双亲的编号为I/2，否则它就是根结点。

　　若2I<=n，则I的左孩子的编号为2I；否则结点I没有左孩子。

　　若(2I+1)<=n,则I的右孩子的编号为2I+1；否则结点I没有右孩子。

　　

　　缺陷：一眼看过去，感觉内存空间还不是很浪费，但是当树的结构为一颗右斜树的时候，本来只需要k个内存空间，却要分配2k-1个空间。当我们的二叉树接近为满树的时候，这种存储结构还是不错的。

　　注:右斜树为所有节点只有右孩子。

2、二叉链表

public class BinaryTreeNode {
    private int data;//数据
    private BinaryTreeNode left;//左孩子
    private BinaryTreeNode right;//右孩子
}

　　缺陷：寻找孩子节点很简单，但是如果我们需要去获得某个节点的双亲结点，将可能遍历整棵树节点，极大的影响效率。

3、三叉链表

public class TridentLinkedListNode {
    private int data;
    private TridentLinkedListNode left;//三叉链表左孩子
    private TridentLinkedListNode right;//三叉链表右孩子
    private TridentLinkedListNode parent;////三叉链表双亲结点
}

4、线索链表

public class ThreadedBinaryTreeNode {
    public String data;
    //0代表指向左孩子，1代表指向前驱
    public int leftTag;
    //0代表指向右有孩子,1代表指向后继
    public int rightTag;
    public ThreadedBinaryTreeNode leftChild;//左孩子
    public ThreadedBinaryTreeNode rightChild;//右孩子
}

 　　问题解决：三叉链表与线索链表诞生的初衷是，节约内存空间和减少运行遍历的次数，提高性能。三叉链表解决寻找双亲结点的效率问题，线索链表则为了解决寻找前驱和后继结点的效率问题，顺便利用二叉链表的残留空指针。

利用二叉链表解决的问题

1、线索链表的存储结构(以中序线索化链表为例)

2、构建线索二叉链表

  1. 建立二叉链表，将每个结点的左右标记置为0。
  2. 遍历二叉链表建立线索

　　　　2.1 如果bt为空，则空操作返回；

　　　　2.2 对bt的左子树建立线索

　　　　2.3 对根节点bt建立线索

　　　　　　2.3.1 如果bt没有左孩子，则为bt建立前驱。

　　　　　　2.3.2 如果bt没有右孩子，则为bt加上后继线索。

　　　　　　2.3.3 如果pre节点的右标记为1，则为其加上后继线索

　　　　2.4 对bt的右子树建立线索

public class InThreadedBinaryTree {
    //头节点
    ThreadedBinaryTreeNode root;
    //用于初始化，标记后继节点
    ThreadedBinaryTreeNode pre;
    public InThreadedBinaryTree() {
        root=create(root);
        pre=new ThreadedBinaryTreeNode();
        init(root);
    }

</span><span style="color: #008000;">//</span><span style="color: #008000;">建立二叉链表,结点标记置0,上述二叉线索链表构建参考：ABD#G###CE##F##  </span>
Scanner scanner=<span style="color: #0000ff;">new</span><span style="color: #000000;"> Scanner(System.in);
</span><span style="color: #0000ff;">private</span><span style="color: #000000;"> ThreadedBinaryTreeNode create(ThreadedBinaryTreeNode bt){
    String str</span>=<span style="color: #000000;">scanner.next();
    </span><span style="color: #0000ff;">if</span>(<span style="color: #0000ff;">null</span>==str||str.equals("#")) bt=<span style="color: #0000ff;">null</span><span style="color: #000000;">;
    </span><span style="color: #0000ff;">else</span><span style="color: #000000;">{
        bt</span>=<span style="color: #0000ff;">new</span><span style="color: #000000;"> ThreadedBinaryTreeNode();
        bt.data</span>=<span style="color: #000000;">str;
        bt.leftTag</span>=0<span style="color: #000000;">;
        bt.rightTag</span>=0<span style="color: #000000;">;
        bt.leftChild</span>=<span style="color: #000000;">create(bt.leftChild);
        bt.rightChild</span>=<span style="color: #000000;">create(bt.rightChild);
    }
    </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> bt;
}
<br />　　//为链表添加线索
</span><span style="color: #0000ff;">public</span> <span style="color: #0000ff;">void</span><span style="color: #000000;"> init(ThreadedBinaryTreeNode bt){
    </span><span style="color: #0000ff;">if</span>(<span style="color: #0000ff;">null</span>==bt)  <span style="color: #0000ff;">return</span><span style="color: #000000;">;
    init(bt.leftChild);
    </span><span style="color: #0000ff;">if</span>(bt.leftChild==<span style="color: #0000ff;">null</span><span style="color: #000000;">){
        bt.leftTag</span>=1<span style="color: #000000;">;
        bt.leftChild</span>=<span style="color: #000000;">pre;
    }
    </span><span style="color: #0000ff;">if</span>(bt.rightChild==<span style="color: #0000ff;">null</span>)bt.rightTag=1<span style="color: #000000;">;
    </span><span style="color: #0000ff;">if</span>(pre.rightTag==1)pre.rightChild=<span style="color: #000000;">bt;
    pre</span>=<span style="color: #000000;">bt;
    init(bt.rightChild);
}



}

3、查找后继结点

　　1.如果该节点没有右孩子，则直接获取该节点的后继。

　　2.如果该节点存在右孩子，则不断向左遍历右孩子。

public ThreadedBinaryTreeNode next(ThreadedBinaryTreeNode node){
    if(node.rightTag==1)return node.rightChild;
    else{
        ThreadedBinaryTreeNode temp=node.rightChild;
        while(temp.leftTag==0)
            temp=temp.leftChild;
        return temp;
    }
}

4、中序遍历二叉线索链表 

　　1.获得根节点的最左孩子节点。

　　2.不断获取后继节点。

public void inOrder(){
    if(root==null) return;
    ThreadedBinaryTreeNode temp=root;
    while(temp.leftTag==0){
        temp=temp.leftChild;
    }
    System.out.println(temp.data);
    while(temp.rightChild!=null){
        temp=next(temp);
        System.out.println(temp.data);
    }
}

 5、二叉线索链表-整体代码

package com.ccut.aaron.tree;

import java.util.Scanner;


/**


    

  • 

    中序索引树
    

    • 

  • 

    @author qiuyong
    

    • 

  • 

    算法思想
    
*/
    
public class InThreadedBinaryTree {
    
    //头节点
    
    ThreadedBinaryTreeNode root;
    
    //用于初始化，标记后继节点
    
    ThreadedBinaryTreeNode pre;
    
    public InThreadedBinaryTree() {
    
root    =create(root);
    
pre    =new ThreadedBinaryTreeNode();
    
init(root);
    
}
    

    Scanner scanner=new Scanner(System.in);
    
    private ThreadedBinaryTreeNode create(ThreadedBinaryTreeNode bt){
    
String str    =scanner.next();
    
    if(null==str||str.equals("#")) bt=null;
    
    else{
    
bt    =new ThreadedBinaryTreeNode();
    
bt.data    =str;
    
bt.leftTag    =0;
    
bt.rightTag    =0;
    
bt.leftChild    =create(bt.leftChild);
    
bt.rightChild    =create(bt.rightChild);
    
}
    
    return bt;
    
}
    

    public void init(ThreadedBinaryTreeNode bt){
    
    if(nullbt)  return;
    
init(bt.leftChild);
    
    if(bt.leftChild    null){
    
bt.leftTag    =1;
    
bt.leftChild    =pre;
    
}
    
    if(bt.rightChildnull)bt.rightTag=1;
    
    if(pre.rightTag    1)pre.rightChild=bt;
    
pre    =bt;
    
init(bt.rightChild);
    
}
    

    /**
    

      

    • 查找中序遍历的某一节点的后继
      • 

    • @return
      
*/
      
public ThreadedBinaryTreeNode next(ThreadedBinaryTreeNode node){
      
      if(node.rightTag1)return node.rightChild;
      
      else{
      
ThreadedBinaryTreeNode temp      =node.rightChild;
      
      while(temp.leftTag      0)
      
temp      =temp.leftChild;
      
      return temp;
      
}
      
}
      • 

    

    /**
    

      

    • 中序遍历
      
*/
      
public void inOrder(){
      
      if(rootnull) return;
      
ThreadedBinaryTreeNode temp      =root;
      
      while(temp.leftTag      0){
      
temp      =temp.leftChild;
      
}
      
System.out.println(temp.data);
      
      while(temp.rightChild!=null){
      
temp      =next(temp);
      
System.out.println(temp.data);
      
}
      
}
      • 

    

    public static void main(String[] args) {
    
InThreadedBinaryTree tree    =new InThreadedBinaryTree();
    
tree.inOrder();
    
}
    

    • 



}

二叉链表整体代码

发散思考-更进一步 

1、思考前序二叉链表、后序二叉链表怎么构建？

　　由上图可知，是否跟递归遍历十分相似呢？没错，就是根据递归遍历衍生出来的。自然而然，前序二叉链表构建、后序链表构建按上述红圈按照递归遍历顺序摆放即可。

　　那前序遍历呢？后序遍历呢？照旧，先寻找第一个节点，然后不断遍历获取节点的后继即可。

2、二叉中序链表能够前序遍历？后序遍历吗？

　　答案是当然可以，只不过需要按照中序遍历改造一下即可，那么我们一起来探索一下如何实现前序遍历、后序遍历自己思考解决。

　　1.如果该节点存在左孩子，那么该节点的后继则为它的左孩子。

　　2.如果该节点没有左孩子，那么返回右子树包含P的最近节点的右孩子结点。

public ThreadedBinaryTreeNode preOrderNext(ThreadedBinaryTreeNode p){
    ThreadedBinaryTreeNode position;
    //存在左孩子
    if(p.getLeftTag()==0)return p.getLeftChild();
    //不存在左孩子
    else{
        position=p;
        //理解难点：直到后继节点存在右孩子
        while(position.getRightTag()==1){
            position=position.getRightChild();
        }
        return position.getRightChild();
    }
}

 理解难点(若无左孩子，直到中序遍历后继到存在右孩子)：参考上述图，假设要返回G的后继。G无左孩子-->G无右孩子-->获得G的后继B-->B无右孩子-->获得B的后继A-->A有右孩子C--返回C。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/qiuyong/p/6789987.html