线索二叉树C语言详解

㈠ c语言线索二叉树，编译通过，运行有错，求解！！！

有4行写错了，修改如下：
//#include "stdafx.h"
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef enum PointerTag {Link, Thread};//Link == 0, Thread == 1;
typedef struct BiThrNode
{
char data;
struct BiThrNode *lchild, *rchild;
PointerTag LTag, RTag;
}BiThrNode, *BiThrTree;

int CreateUnThreadingTree(BiThrTree *T)
{//建立一个未被线索化的二叉树
char ch;
ch = getchar();
if(ch == '\n')
ch = getchar();//吃掉了回车符

if(ch == '#')
return 0;//表示输入结束

if(!(*T = (BiThrNode*)malloc(sizeof(BiThrNode))))
puts("error!");
(*T)->data = ch;
(*T)->lchild = (*T)->rchild = NULL;
(*T)->LTag = Link;
(*T)->RTag = Link;

CreateUnThreadingTree(&(*T)->lchild);
CreateUnThreadingTree(&(*T)->rchild);
return 0;
}

BiThrTree pre;//用它始终指向p的前驱，好使lchild指向前驱是外部变量

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

int InOrderThreading(BiThrTree *Thrt, BiThrTree T)
{//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。

if(!(*Thrt = (BiThrTree)malloc(sizeof(BiThrNode))))
puts("error");
(*Thrt)->LTag = Link;
(*Thrt)->RTag = Thread;
(*Thrt)->rchild = *Thrt;//右指针回指 错(*Thrt)->lchild = *Thrt;
if(!T)
(*Thrt)->lchild = *Thrt;//错(*Thrt)->rchild = *Thrt;
else
{
(*Thrt)->lchild = T;
pre = *Thrt;
InThreading(T);
pre->rchild = *Thrt;
pre->RTag = Thread;//错pre->LTag = Thread;
(*Thrt)->rchild = pre;
}
return 0;
}

int InOrderTraverse_Th(BiThrTree T)
{//T指向头结点，头结点的左链lchild指向根结点
//中序遍历二叉线索树
BiThrTree p;
p = T->lchild;
while(p != T)//也就是不空
{
while(p->LTag == Link)
{
p = p->lchild;
}
printf("%c ",p->data);
while((p->RTag == Thread) && (p->rchild != T))
{
p = p->rchild;
printf("%c ",p->data);
}
p = p->rchild;
}
return 0;
}

//int _tmain(int argc, _TCHAR* argv[])
int main(int argc, char* argv[])
{
BiThrTree BTT, T;

CreateUnThreadingTree(&T);
InOrderThreading(&BTT, T);
InOrderTraverse_Th(BTT);

return 0;
}

㈡ C语言数据结构中的 线索二叉树问题

#include<iostream>
using namespace std;
#include<malloc.h>
#include<stdio.h>
#include<math.h>
#define maxsize 20 //最大结点个数
//#define N 14 //必须输入结点个数(包含虚结点)
#define M 10 //最大深度
typedef struct node{
char data;
int m; //结点的深度
struct node*lchild,*rchild;
}Bitree;
Bitree*Q[maxsize];
Bitree*creatree()
{
char ch;
int front,rear;
// int i=1;
Bitree *T,*s;
T=NULL;
front=1;
rear=0;
cout<<"请输入数据"<<endl;
cin>>ch;
while(ch!='#')
{
// cin>>ch;
s=NULL;
if(ch!='@')
{
s=(Bitree*)malloc(sizeof(Bitree));
s->data =ch;
s->lchild =s->rchild =NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
{
T=s;
T->m=1; //父结点深度为一
}
else{
if(s!=NULL&&Q[front]!=NULL)
if(rear%2==0)
{
Q[front]->lchild =s;
Q[front]->lchild ->m =Q[front]->m+1;
}
else
{
Q[front]->rchild =s;
Q[front]->rchild ->m =Q[front]->m+1;
}

if(rear%2==1)
front++;
}
//i++;
cin>>ch;
}
return T;
}
int countleaf(Bitree* T)
{
if(T==NULL)
return (0);
else if((T->lchild==NULL)&&(T->rchild==NULL))
return (1);
else
return (countleaf(T->lchild)+countleaf(T->rchild));
}
int treedepth(Bitree *T)
{
if(T==NULL)
return (0);
else
{
if(treedepth(T->lchild )>treedepth(T->rchild ))
return(treedepth(T->lchild )+1);
else
return (treedepth(T->rchild )+1);
}
}
void output(Bitree*T) //输出打印二叉数
{
int i;
if(T!=NULL)
{
output(T->rchild ); //右根左遍历二叉数，结果从上到下显示
for(i=1;i<=M;i++)
{
if(i!=T->m)
cout<<" ";
else
cout<<T->data ;
}
cout<<endl;
//cout<<T->data ;
output(T->lchild );
}
}

int menu_select( )
{
int sn;
printf(" 打印二叉树问题\n");
printf("==================\n");
printf(" 1 二叉树的建立\n");
printf(" 2 打印二叉树\n");
printf(" 3 求二叉树叶子结点个数\n");
printf(" 4 求二叉树的深度\n");
printf(" 0 退出系统\n");
printf("==================\n");
printf(" 请 选 择0－4：\n");
for( ; ; )
{
scanf( "%d", &sn);
if( sn <0||sn>4)
printf("\n\t输入错误，重选0－4：\n");
else
break;
}
return sn;
}

int main( )
{
Bitree*T;
for(; ;)
{
switch(menu_select())
{
case 1: T=creatree();
printf("\n");
break;
case 2: cout<<"打印结果："<<endl;
output(T);
printf("\n");
break;
case 3: int i;
i=countleaf(T);
cout<<"所求二叉树叶子结点为"<<i;
cout<<endl;
break;
case 4: int j;
j=treedepth(T);
cout<<"所求二叉树深度为"<<j;
cout<<endl;
break;
case 0:printf("再见");
exit(0);
break;
}
}
return 0;
}

/*void main()
{
Bitree*T;
T=creatree();
cout<<"打印结果："<<endl;
output(T);
}*/

㈢ 有谁可以告诉我，在C语言中二叉线索树是什么引入的目的又是什么

建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一颗二叉树。在遍历过程中，访问结点的草所是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现这一过程，设指针pre始终指向刚刚访问的结点，即若指针p指向当前结点，则pre指向它的前驱，以便设线索。

另外，在对一颗二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的跟结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。

下面是建立中序二叉树的递归算法，其中pre为全局变量。

BiThrNodeType *pre;

BiThrTree InOrderThr(BiThrTree T)

{ /*中序遍历二叉树T，并将其中序线索化，pre为全局变量*/
BiThrTree head;
head=(BitThrNodeType *)malloc（sizeof（BiThrType））;/*设申请头结点成功*/
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;
};
return head;

}
void InThreading(BiThrTree p)
{/*通过中序遍历进行中序线索化*/
if(p)
{InThreading(p->lchild);/*左子树线索化*/
if(p->lchild==NULL)/*前驱线索*/
{p->ltag=1;
p->lchild=pre;

}
if(p->lchild==NULL)/*后续线索*/
{p->rtag=1;
p->rchild=pre;
}
pre=p;
InThreading(p->rchild);/*右子树线索化*/
}
}

㈣ 用c语言描述线索二叉树数据类型

struct node
{
int data;

struct node *pleft;

struct node *pright;

}
如上，树是由很多个这样的节点构成的，每个节点两个指针，指向下面的左右子树
根节点,下左右2个子节点,然后下面2个子节点之下又是各自的两个子节点,这样就把树构建起来了,
当然并不是一定有2个子节点

㈤ c语言二叉树线索化的问题，求解！

/*中序遍厉二叉树T，并将其中序线索化，Thrt指向头结点*/ { if(!(*/*T指向头结点，头结点的左链lchild指向根结点，中序遍厉二叉树*/ {

㈥ c语言 线索二叉树中遍历二叉树

函数指针，可以自己搜“函数指针”的知识。
init (*visit)(BiThrTree e) 声明了一个函数指针类型，该指针指向的函数类型是：一个参数，类型是BiThrTree ，返回值int
然后将该函数指针类型作为traversal的第二个参数的类型。
比如前面有一个函数:
int myVisit( BiThrTree e )
{
e;//对e进行一些操作
}
那么可以这样来使用遍历函数：
traversal( myTree, myVisit );
就对myTree中的所有元素进行了myVisit中定义的操作。

㈦ C语言树和二叉树

非递归先序遍历：
void TraversalTree_DLR(BinTNode *t)
{ BinTNode *stack[M]; int top;
BinTNode *p;
if( t==NULL ) return;
top = 1; stack[top] = t;
while ( top > 0 )
{ p = stack[top--];
putchar( p->data );
if ( p->rchild != NULL ) stack[ ++top ] = p->rchild ;
if ( p->lchild != NULL ) stack[ ++top ] = p->lchild ;
}
中序：void TraversalTree_LDR(BinTNode *t)
{ BinTNode *stack[M]; int top;
BinTNode *p;
if( t==NULL ) return;
top = 0; p = t;
while ( p != NULL )
{ while ( p != NULL )
{ stack[++top] = p; p = p->lchild; }
do {
p = stack[top--]; putchar( p->data ); p = p->rchild;
} while ( top > 0 && p == NULL)；
}
}
后序：
void TraversalTree_LRD(BinTNode *t)
{ struct
{ BinTNode *ptr;
char tag;
} *stack[M];
int top;
BinTNode *p;
if( t==NULL ) return;
top = 0; p = t;
while ( p != NULL )
{ while ( p != NULL )
{ stack[++top].ptr = p; stack[top].tag =‘L’;p = p->lchild; }
while( top>0 && ( stack[top].tag ==‘R’||
stack[top].tag ==‘L’&& stack[top].ptr -> rchild == NULL ))
{ p = stack[top--].ptr; putchar( p->data );}
if(top>0)
{ stack[top].tag =‘R’; p = stack[top].ptr->rchild; }
else break; // p = NULL;
}
}

㈧ c语言怎么利用 顺序或链式结构实现中序线索化二叉树

线索化二叉树实质就是将二叉树中的空指针改成指向前驱后者后继的指针 从而确定二叉树的唯一性

而前驱后后继只能在遍历中才能确定 所以要对二叉树进行中序遍历的过程中进行线索化

中序线索化二叉树源码

#include "stdio.h"
#include "stdlib.h"
typedef enum piontertag{link,thread};
typedef struct bithrnode
{char data;
piontertag ltag,rtag;
struct bithrnode *lchild,*rchild;
}BithrNODE;
BithrNODE *BithrCreat();//先序递归建立二叉树
BithrNODE *InOrderThreading(BithrNODE *);//中序线索化二叉树
void InThreading(BithrNODE *);//中序遍历过程中线索化二叉树的具体过程
void InOrderTraverse(BithrNODE *);//中序线索化二叉树输出
BithrNODE *pre;
int main(void)
{
BithrNODE *a=BithrCreat();
a=InOrderThreading(a);
InOrderTraverse(a);
return 0;
}
BithrNODE *BithrCreat()
{
char x;
BithrNODE *p=NULL;
scanf("%c%*c",&x);
if(x=='#')
return NULL;
p=(BithrNODE *)malloc(sizeof(BithrNODE));
p->data=x;
p->ltag=p->rtag=link;
p->lchild=BithrCreat();
p->rchild=BithrCreat();
return p;
}
BithrNODE *InOrderThreading(BithrNODE *a)
{
BithrNODE *h=(BithrNODE *)malloc(sizeof(BithrNODE ));
if(!h)
exit(-1);
h->ltag=link;
h->rtag=thread;
h->rchild=h;
if(!a) h->lchild=h;
else
{
h->lchild=a;
pre=h;
InThreading(a);
pre->rtag=thread;
pre->rchild=h;
h->rchild=pre;
}
return h;
}
void InOrderTraverse(BithrNODE *a)
{
BithrNODE *p=a->lchild;
while(p!=a)
{
while(p->ltag==link)
p=p->lchild;
printf("%c ",p->data);
while(p->rtag==thread&&p->rchild!=a)
{
p=p->rchild;
printf("%c ",p->data);
}
p=p->rchild;
}
}
void InThreading(BithrNODE *a)
{
if(a)
{
InThreading(a->lchild);
if(!a->lchild)
{
a->ltag=thread;
a->lchild=pre;
}
if(!pre->rchild)
{
pre->rtag=thread;
pre->rchild=a;
}
pre=a;
InThreading(a->rchild);
}
}

㈨ 用C语言编程实现在线索二叉树上进行遍历

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>

using namespace std;
#define maxsize 30

typedef struct T
{
struct T *lchild,*rchild;
int data;
}BiTNode,*BiTree;

typedef struct
{
BiTree *base;
BiTree *top;
int stacksize;
}TNode;

int Init(TNode &s)
{
s.base=(BiTree*)malloc(maxsize*sizeof(BiTree));
if(!s.base) return 0;
s.top=s.base;
s.stacksize=maxsize;
return 1;
}

int push(TNode &s,BiTree e)
{
if(s.top-s.base>=s.stacksize)
{
s.base=(BiTree*)realloc(s.base,(s.stacksize+maxsize)*sizeof(BiTree));
if(!s.base) return 0;
s.top=s.base+s.stacksize;
s.stacksize+=maxsize;
}
*s.top++=e;
return 1;
}

int pop(TNode &s,BiTree &e)
{
if(s.top==s.base) return 0;
e=*--s.top;
return 1;
}

int Create(BiTree &T)//创建二叉树
{
int a;
scanf("%d",&a);
if(a==0) T=NULL;
else{
if(!(T=(BiTree)malloc(sizeof(BiTNode))))
return 0;
T->data=a;
Create(T->lchild);
Create(T->rchild);
}
return 1;
}

int StackEmpety(TNode &s)
{
if(s.top==s.base) return 1;
return 0;
}

void PreOrder(BiTree &T)//先序遍历二叉树
{
if(T){
printf("%d ",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}

void LaterOrder(BiTree &T)//后序遍历二叉树
{
if(T){
LaterOrder(T->lchild);
LaterOrder(T->rchild);
printf("%d ",T->data);
}
}

int MidOrder(BiTree &T)//中序遍历二叉树
{
BiTree p;
TNode S;
Init(S); p=T;
while(p||!StackEmpety(S))
{
if(p){
push(S,p);
p=p->lchild;
}
else{
pop(S,p);
if(!p->data) return 0;
printf("%d ",p->data);
p=p->rchild;
}
}
return 1;
}

int main()
{
BiTree T;
printf("创建一棵二叉树：\n");
Create(T);
printf("先序遍历：\n");
PreOrder(T);
printf("\n中序遍历：\n");
MidOrder(T);
printf("\n后序遍历：\n");
LaterOrder(T) ;\
printf("\n");
system("pause");
return 0;

}