二叉树的线索化,该如何解决

二叉树的线索化

C/C++ code

void InThreading(BiThrTree p){    if(p)    {        InThreading(p -> lchild); //左子数线索化        if(!p -> lchild) { p->LTag = Thread; p->lchild = pre; } //前驱线索        if(!pre -> rchild) { pre->RTag = Thread; pre->rchild = p; } // 后继线索        pre = p;  //保持pre指向p的前驱        InThreading(p -> lchild); //右子树线索化    }}

按照中序遍历线索化二叉树。
摘自数据结构与算法，严蔚敏。左子树线索化和右子树线索化能不能调换位置？

[解决办法]
为什么要调换位置？
中序遍历本来就那样
先左，后中，最后右
[解决办法]
我刚做的哈。
测试数是421##3##65##7##

#include<conio.h>
#include<stdio.h>
#include<stdlib.h>

typedef struct tree
{
char info;
int leftThread;
int rightThread;
struct tree *lchild;
struct tree *rchild;
}BinTNode,*BinTree;

BinTree prior;

void InThread(BinTree T)
{
if(T!=NULL)
{
InThread(T->lchild);
if(T->rchild==NULL)
T->rightThread=0;
if(T->lchild==NULL)
{
T->lchild=prior;
T->leftThread=0;
}
if(T->rightThread==1)
prior->rchild=T;
prior=T;
InThread(T->rchild);
}
}

BinTree ThreadTree(BinTree T)
{
BinTree q;
q=(BinTree)malloc(sizeof(BinTNode));
if(q==NULL)
printf("out of space.\n");
q->info='@';
q->leftThread=1;
q->rightThread=1;
q->rchild=q;
if(T==NULL)
q->lchild=q;
else
{
q->lchild=T;
prior=q;
InThread(T);
prior->rchild=q;
prior->rightThread=0;
}
return q;
}

BinTree CreatBinTree()
{
BinTree T;
char ch;
if((ch=getchar())=='#')
return NULL;
else
{
T=(BinTree)malloc(sizeof(BinTNode));
T->info=ch;
T->leftThread=1;
T->rightThread=1;
T->lchild=CreatBinTree();
T->rchild=CreatBinTree();
return T;
}
}

BinTree FinInPrior(BinTree T)
{
BinTree S;
S=T->lchild;
if(T->leftThread==1)
{
printf("\nLeftchild is pointer\n");
while(S->rightThread==1)
{
S=S->rchild;
}
printf("\nIts prior is %c\n",S->info);
}
else if(T->leftThread==0)
{
printf("\nLeftChild is thread:its prior is %c\n",S->info);
}
return S;
}

BinTree FinInSucc(BinTree T)
{
BinTree S;
S=T->rchild;
if(T->rightThread==1)
{
printf("\nRightChild is pointer\n");
while(S->leftThread==1)
{
S=S->lchild;
}
printf("\nIts successor is %c\n",S->info);
}
else if(T->leftThread==0)
{
printf("\nRightChild is thread: its successor is %c\n",S->info);

}
return S;
}

void TreeSearch(BinTree T)
{
char ch;
ch=getchar();
if(ch=='$')
{
printf("\nThe data your want is :%c\n",T->info);
FinInPrior(T);
FinInSucc(T);
}
else
{
if(ch=='l')
TreeSearch(T->lchild);
else if(ch=='r')
TreeSearch(T->rchild);
}

return;
}

void PrintTree(BinTree T)
{
if(T!=NULL)
{
PrintTree(T->lchild);
printf("%c",T->info);
PrintTree(T->rchild);
}
}

void main()
{
char answer='y';
BinTree H,T1;
BinTree T=CreatBinTree();
printf("\nThe original Tree is :\n\n");
PrintTree(T);
H=ThreadTree(T);
do
{
printf("\n\nSearch beginning:\n");
printf("\nInput instrution*like rl$ rl$* : ");
flushall();
T1=H->lchild;
TreeSearch(T1);
printf("\n\nWould you want to try again?(y/n):");
answer=getch();
}while(answer=='y');
getch();
return;
}
[解决办法]
希望对你有帮助哈。
[解决办法]
肯定不能互换了，中序是先左再中最后右
pre = p;
这句是设置右子树调用的前驱节点
互换的话肯定就不对了
[解决办法]
左右子树是同等地位，你高兴的话直接把left当右子树；调换位置根本没有任何意义
实现也十分简单；楼上说不能调换的数据结构好好重新看看吧，先序后序中序是针对根节点什么时候遍历到而言的。

查看更多 下一篇