線索二叉樹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;

}