![]() |
#2
楚川杉2020-11-03 17:12
|
请问哪位大佬可以看一看这个程序,希望大佬能够帮我指正


BThrTree creatBTree(BThrTree p)通过前序遍历创建二叉树
void inOrderThread(BThrTree p)用中序遍历创建线索二叉树
BThrTree findNext(BThrTree p)为查找某个节点的后继
void displayThrBTree(BThrTree p)遍历创建的中序线索结果
AB#C##DE##FG#H##I##为测试数据
按理应输出BCAEDGHFI
只有本站会员才能查看附件,请 登录
但输入数据后没有任何反应
只有本站会员才能查看附件,请 登录

#include<stdio.h>
#include<stdlib.h>
typedef char datatype;
typedef struct BNode {
datatype data;
int ltag;//1为前驱,0为左孩子
int rtag;//1为后继,0为右孩子
struct BNode *lchild;
struct BNode *rchild;
}BThrNode,*BThrTree;
BThrTree creatBTree(BThrTree p);
void inOrderThread(BThrTree p);
BThrTree findNext(BThrTree p);
void displayThrBTree(BThrTree p);
void main(){
BThrTree btree =creatBTree(btree);
inOrderThread(btree);
displayThrBTree(btree);
}
//不创建空指针的情况
//通过前序创建二叉树
BThrTree creatBTree(BThrTree p){
//AB#C##DE##FG#H##I##
datatype value;
scanf("%c",&value);
if(value=='#'){
p=NULL;
}
else{
p=(BThrTree)malloc(sizeof(BThrNode));
p->data=value;
p->ltag=0;
p->rtag=0;
p->lchild=creatBTree(p->lchild);
p->rchild=creatBTree(p->rchild);
}
return p;
}
//利用中序遍历线索化
void inOrderThread(BThrTree p){
static BThrTree pre=NULL;
if(p==NULL){
return ;
}
//左子树线索化
inOrderThread(p->lchild);
//线索化处理
if(p->lchild==NULL){
p->lchild=pre;
p->ltag=1;
}
if(pre->rchild==NULL&&pre!=NULL){
pre->rchild=p;
pre->rtag=1;
}
pre=p;
//右子树线索化
inOrderThread(p->rchild);
}
//查找节点的后继
BThrTree findNext(BThrTree p){
if(p->rtag==1){
return p->rchild;
}
else{
BThrTree temp=(BThrTree)malloc(sizeof(BThrNode));
temp=p->rchild;
while(temp->ltag==0){
temp=temp->lchild;
}
return temp;
}
}
//遍历输出线索树
void displayThrBTree(BThrTree p){
if(p==NULL){
return;
}
//找到遍历的开始节点
BThrTree root;
root=p;//获取根节点
while(root->ltag==0){//对于线索二叉树只有最左下角的节点的左孩子是空 ,其余左孩子都有前继或左孩子
root=root->lchild;
}
printf("%d",root->data); //访问第一个节点
while(root->rchild!=NULL){//线索树中的最后一节点的右孩子为空
root=findNext(root);//获取后继节点
printf("%d",root->data);
}
}
#include<stdlib.h>
typedef char datatype;
typedef struct BNode {
datatype data;
int ltag;//1为前驱,0为左孩子
int rtag;//1为后继,0为右孩子
struct BNode *lchild;
struct BNode *rchild;
}BThrNode,*BThrTree;
BThrTree creatBTree(BThrTree p);
void inOrderThread(BThrTree p);
BThrTree findNext(BThrTree p);
void displayThrBTree(BThrTree p);
void main(){
BThrTree btree =creatBTree(btree);
inOrderThread(btree);
displayThrBTree(btree);
}
//不创建空指针的情况
//通过前序创建二叉树
BThrTree creatBTree(BThrTree p){
//AB#C##DE##FG#H##I##
datatype value;
scanf("%c",&value);
if(value=='#'){
p=NULL;
}
else{
p=(BThrTree)malloc(sizeof(BThrNode));
p->data=value;
p->ltag=0;
p->rtag=0;
p->lchild=creatBTree(p->lchild);
p->rchild=creatBTree(p->rchild);
}
return p;
}
//利用中序遍历线索化
void inOrderThread(BThrTree p){
static BThrTree pre=NULL;
if(p==NULL){
return ;
}
//左子树线索化
inOrderThread(p->lchild);
//线索化处理
if(p->lchild==NULL){
p->lchild=pre;
p->ltag=1;
}
if(pre->rchild==NULL&&pre!=NULL){
pre->rchild=p;
pre->rtag=1;
}
pre=p;
//右子树线索化
inOrderThread(p->rchild);
}
//查找节点的后继
BThrTree findNext(BThrTree p){
if(p->rtag==1){
return p->rchild;
}
else{
BThrTree temp=(BThrTree)malloc(sizeof(BThrNode));
temp=p->rchild;
while(temp->ltag==0){
temp=temp->lchild;
}
return temp;
}
}
//遍历输出线索树
void displayThrBTree(BThrTree p){
if(p==NULL){
return;
}
//找到遍历的开始节点
BThrTree root;
root=p;//获取根节点
while(root->ltag==0){//对于线索二叉树只有最左下角的节点的左孩子是空 ,其余左孩子都有前继或左孩子
root=root->lchild;
}
printf("%d",root->data); //访问第一个节点
while(root->rchild!=NULL){//线索树中的最后一节点的右孩子为空
root=findNext(root);//获取后继节点
printf("%d",root->data);
}
}