本文目录一览：
线索二叉树的构建
建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现这一过程，设指针pre始终指向刚刚访问的结点，即若指针p指向当前结点，则pre指向它的前驱，以便设线索。
另外，在对一颗二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。
下面是建立中序二叉树的递归算法，其中pre为全局变量。 voidInThreading(BiThrTree*p);//预先声明BiThrNodeType*pre;BiThrTree*InOrderThr(BiThrTree*T){/*中序遍历二叉树T，并将其中序线索化，pre为全局变量*/BiThrTree*head;//线索二叉树的头结点，指向根结点head=(BitThrNodeType*)malloc（sizeof（BitThrNodeType））;/*设申请头结点成功*/head-ltag=0;head-rtag=1;/*建立头结点*/head-rchild=head;/*右指针回指*/if(!T)head-lchild=head;/*若二叉树为空，则左指针回指*/else{head-lchild=T;pre=head;InThreading(T);/*中序遍历进行中序线索化*/pre-rchild=head;pre-rtag=1;/*最后一个结点线索化*/head-rchild=pre;}returnhead;}voidInThreading(BiThrTree*p){/*通过中序遍历进行中序线索化*/if(p){InThreading(p-lchild);/*左子树线索化，递归*/if(p-lchild==NULL)/*前驱线索*/{ p-ltag=1;p-lchild=pre;}elsep-ltag=0;if(p-rchild==NULL)p-rtag=1;/*后驱线索*/elsep-rtag=0;if(pre!=NULLpre-rtag==1)pre-rchild=p;pre=p;InThreading(p-rchild);/*右子树线索化*/}}算法 （1）中序线索二叉树：若结点的ltag=1，lchild指向其前驱；否则，该结点的前驱是以该结点为根的左子树上按中序遍历的最后一个结点。若rtag=1，rchild指向其后继；否则，该结点的后继是以该结点为根的右子树上按中序遍历的第一个结点。
求后继的算法如下： bithptr*INORDERNEXT(bithptr*p){if(p-rtag==1)return(p-rchild);else{q=p-rchild;/*找右子树最先访问的结点*/while(q-ltag==0)q=q-lchild;return(q);}}求前驱的算法如下： bithptr*INORDERNEXT(bithptr*p){if(p-ltag==1)return(p-lchild);else{q=p-lchild;/*找左子树最后访问的结点*/while(q-rtag==0)q=q-rchild;return(q);}}(2) 后序线索二叉树：
在后序线索二叉树中查找结点*p的前驱：若结点*p无左子树，则p-lchild指向其前驱；否则，若结点*p有左子树，当其右子树为空时，其左子树的根（即p-lrchild）为其后序前驱。当其右子树非空时，其右子树的根（即p-rchild）为其后序前驱。
在后序线索二叉树中查找结点*p的后继：若结点*p为根，则无后继；若结点*p为其双亲的右孩子，则其后继为其双亲；若结点*p为其双亲的左孩子，且双亲无右子女，则其后继为其双亲；若结点*p为其双亲的左孩子，且双亲有右子女，则结点*p的后继是其双亲的右子树中按后序遍历的第一个结点。所以，求后序线索二叉树中结点的后继要知道其双亲的信息，要使用栈，所以说后序线索二叉树是不完善的。
（3）先序线索二叉树：
在先序线索二叉树中查找结点的后继较容易，而查找前驱要知道其双亲的信息，要使用栈，所以说先序线索二叉树也是不完善的。
求帮忙改错——数据结构 树的遍历 线索二叉树
Status InorderTraverse(BiTree T,Status(*Visit)(TElemType)){
BiTree p;
p=T-lchild;
while(p!=T){
while(p-LTag==Link) 这一行出现了错误P是定义为BiTree,它没有LTag
p=p-lchild;
if(!Visit(p-data))
return ERROR;//访问其左子树为空的结点
while(p-RTag==Threadp-rchild!=T){
p=p-rchild;
Visit(p-data);//访问后继结点
}
p=p-rchild;
}
return OK;
}
如何实现二叉树的线索化
自己理解得方法：
先把二叉树给标记化：既设置两个标记Ltag，Rtag，如果左孩子指针为空，Ltag=1，如果右孩子指针为空，Rtag=1。
先序遍历线索二叉树：
首先进行先序遍历，然后把得到的节点依次入队
然后把队列里除了根节点以外的节点依次根据标记，队里首节点Ltag=0，如果Ltag=1，左指针指向队里前一个元素，如果Rtag=1，右指针指向队里后一个元素。
中序遍历线索二叉树：
首先进行中序遍历，然后把得到的节点依次入队
然后把队列里除了根节点以外的节点依次根据标记，队列里首节点Ltag=0，如果Ltag=1，左指针指向队里前一个元素，如果Rtag=1，右指针指向队里后一个元素。
后序遍历线索二叉树：
首先进行后序遍历，然后把得到的节点依次入队
然后把队列里除了根节点以外的节点依次根据标记，队列里首节点Ltag=0，如果Ltag=1，左指针指向队里前一个元素，如果Rtag=1，
java 二叉树前序遍历
//类Node定义二叉树结点的数据结构;
//一个结点应包含结点值，左子结点的引用和右子结点的引用
class Node{
public Node left; //左子结点
public Node right; //右子结点
public int value; //结点值
public Node(int val){
value = val;
}
}
public class Traversal
{
//read()方法将按照前序遍历的方式遍历输出二叉树的结点值
//此处采用递归算法会比较简单，也容易理解，当然也可以用
//循环的方法遍历，但会比较复杂，也比较难懂。二叉树遍历
//用递归算法最为简单，因为每个结点的遍历方式都是，根，
//左，右，递归的调用可以让每个结点以这种方式遍历
public static void read(Node node){
if(node != null){
System.out.println(node.value);//输出当前结点的值
if(node.left != null)
read(node.left); //递归调用 先读左结点
if(node.right != null)
read(node.right); //递归调用 后读右结点
}
}
public static void main(String[] args){
//初始化5个结点，分别初始值为1，2，3，4，5
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
//构建二叉树，以n1为根结点
n1.left = n2;
n1.right = n5;
n2.left = n3;
n2.right = n4;
read(n1);
}
}
注释和代码都是我自己写的，如果楼主觉得有的注释多余可以自己删除一些！代码我都编译通过，并且运行结果如你提的要求一样！你只要把代码复制编译就可以了，注意要以文件名Traversal.java来保存，否则编译不通过，因为main函数所在的类是public类型的！
怎么线索二叉树？
用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左右孩子结点的指针域，所以从任一结点出发只能直接找到该结点的左右孩子结点，而无法直接找到该结点在某种遍历序列中的前驱和后继结点。为了保存遍历后结点的前驱和后继信息，可采用增加向前和向后的指针，但这种方法增加了存储开销，不可取。对于具有n个结点的二叉树，采用二叉链表存储结构时，每个结点有两个指针域，总共有2n个指针域，其中有n＋1个空指针域。由此，利用这些空链域来存放遍历后结点的前驱和后继信息，这就是线索二叉树构成的思想。由于遍历方法不同，所获得的线性序列中，结点的前驱和后继也不同，因此线索二叉树又分为前序线索二叉树、中序线索二叉树和后序线索二叉树。
1.线索二叉树的基本概念（1）线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针称为线索。
（2）线索链表：把加上了线索的二叉链表称为线索链表。
（2）线索化：使二叉链表中结点的空链域存放以某种次序遍历得到的前驱或后继信息的过程称为线索化。
（4）线索二叉树：加上线索的二叉树称为线索二叉树。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/295946.html
微信扫一扫 
支付宝扫一扫 