二叉樹中序遍歷線索化遞歸演算法

A. 跪求中序遍歷二叉樹遞歸演算法

比較好記：
void DFS(int x){
if(Tree[x].lson)DFS(Tree[x].lson);

printf("%d\n",x);

if(Tree[x].rson)DFS(Tree[x].rson);

}
其實就是在你的遞歸程序裡面，先遍歷左兒子（子樹），然後記錄這個節點，然後遍歷右兒子（子樹）。
前序遍歷就是把「記錄這個節點」放在最前面，後序遍歷就是把「記錄這個節點」放在最後面

B. 用遞歸演算法先序中序後序遍歷二叉樹

1、先序

void PreOrderTraversal(BinTree BT)

{

if( BT )

{

printf(「%d 」, BT->Data); //對節點做些訪問比如列印

PreOrderTraversal(BT->Left); //訪問左兒子

PreOrderTraversal(BT->Right); //訪問右兒子

}

}

2、中序

void InOrderTraversal(BinTree BT)

{

if(BT)

{

InOrderTraversal(BT->Left);

printf("%d ", BT->Data);

InOrderTraversal(BT->Right);

}

}

3、後序

void PostOrderTraversal(BinTree BT)

{

if (BT)

{

PostOrderTraversal(BT->Left);

PostOrderTraversal(BT->Right);

printf("%d ", BT->Data);

}

}

(2)二叉樹中序遍歷線索化遞歸演算法擴展閱讀：

注意事項

1、前序遍歷

從整棵二叉樹的根結點開始，對於任意結點VV，訪問結點VV並將結點VV入棧，並判斷結點VV的左子結點LL是否為空。若LL不為空，則將LL置為當前結點VV；若LL為空，則取出棧頂結點，並將棧頂結點的右子結點置為當前結點VV。

2、中序遍歷

從整棵二叉樹的根結點開始，對於任一結點VV，判斷其左子結點LL是否為空。若LL不為空，則將VV入棧並將L置為當前結點VV；若LL為空，則取出棧頂結點並訪問該棧頂結點，然後將其右子結點置為當前結點VV。重復上述操作，直到當前結點V為空結點且棧為空，遍歷結束。

3、後序遍歷

將整棵二叉樹的根結點入棧，取棧頂結點VV，若VV不存在左子結點和右子結點，或VV存在左子結點或右子結點，但其左子結點和右子結點都被訪問過了，則訪問結點VV，並將VV從棧中彈出。若非上述兩種情況，則將VV的右子結點和左子結點依次入棧。重復上述操作，直到棧為空，遍歷結束。

C. 用遞歸的方式中序遍歷二叉樹演算法描述

voidtravser(Node*node)
{
if(node==NULL)
return;
travser(node->left);
cout<<node->data;
travser(node->right);

}

D. 程序題--二叉樹遍歷的遞歸演算法實現 實現二叉樹前序、中序和後序遍歷的遞歸演算法重要結構處要加註釋

我給你一個前序輸出的，中序和後序你可以改子函數Status PreOrderTraverse(BiTree T)中的左右子樹的輸出順序，比如中序改為：
PreOrderTraverse(T->lchild);
printf("%c",T->date);
PreOrderTraverse(T->rchild);
後續改為：
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
printf("%c",T->date);
這樣就OK了，同學你就活學活用吧
程序如下：
#include<stdio.h>
#include<stdlib.h>

#define OVERFLOW -2
#define OK 1

typedef char TElemType;
typedef char Status;

typedef struct BiTNode
{
TElemType date;
struct BiTNode *lchild,*rchild;//左右孩子指針
}BiTNode,*BiTree;

Status CreateBiTree(BiTree &T)
{ //按先序次序輸入二叉樹中結點的值（一個字元），#表示空結點
//構造二叉鏈表表示的二叉樹T
char ch;

scanf("%c",&ch);
if(ch==' #') //如果ch為#
T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->date=ch; //生成根結點

CreateBiTree(T->lchild);//構建左子樹

CreateBiTree(T->rchild);//構建右子數
}
return OK;
}

Status PreOrderTraverse(BiTree T)
{ //遞歸先序遍歷二叉樹
if(T)
{
printf("%c",T->date);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
return OK;
}
void main()
{
BiTree T;
int count=0;

printf("請按次序輸入二叉樹的字元：");
CreateBiTree(T);

printf("二叉樹先序遍歷輸出結果為：");
PreOrderTraverse(T);
printf("\n");
}
結果為：
請按次序輸入二叉樹的字元：ABC##DE#G##F###
二叉樹先序遍歷輸出結果為：ABCDEGF

E. (1)設定一個序列，用遞歸的方法先序構造二叉樹 (2)建立中序線索二叉樹，並中序遍歷該

#include<stdio.h>

#include<malloc.h>

typedefenum{Link,Thread}PointerTag; /*指針標志*/

typedefcharDataType;

typedefstructBiThreTree{ /*定義結點元素*/

PointerTagLTag,RTag;

DataTypedata;

structBiThreTree*lchild,*rchild;

}BiThreTree;

BiThreTree*pre; /*全局變數，用於二叉樹的線索化*/

BiThreTree*CreateTree() /*按前序輸入建立二叉樹*/

{

BiThreTree*T;

DataTypech;

scanf("%c",&ch);

if(ch=='#')

T=NULL;

else

{T=(BiThreTree*)malloc(sizeof(BiThreTree));

T->data=ch;

T->LTag=Link; /*初始化時指針標志均為Link*/

T->RTag=Link;

T->lchild=CreateTree();

T->rchild=CreateTree();

}

returnT;

}

voidInThread(BiThreTree*T)

{

BiThreTree*p;

p=T;

if(p)

{

InThread(p->lchild);

if(!p->lchild)

{p->LTag=Thread;

p->lchild=pre;

}

if(!pre->rchild)

{pre->RTag=Thread;

pre->rchild=p;

}

pre=p;

InThread(p->rchild);

}

}

BiThreTree*InOrderThrTree(BiThreTree*T)/*中序線索化二叉樹*/

{

BiThreTree*Thre; /*Thre為頭結點的指針*/

Thre=(BiThreTree*)malloc(sizeof(BiThreTree));

Thre->lchild=T;

Thre->rchild=Thre;

pre=Thre;

InThread(T);

pre->RTag=Thread;

pre->rchild=Thre;

Thre->rchild=pre;

returnThre;

}

voidInThrTravel(BiThreTree*Thre) /*中序遍歷二叉樹*/

{

BiThreTree*p;

p=Thre->lchild;

while(p!=Thre) /*指針回指向頭結點時結束*/

{

while(p->LTag==Link)

p=p->lchild;

printf("%4c",p->data);

while(p->RTag==Thread&&p->rchild!=Thre)

{p=p->rchild;

printf("%4c",p->data);

}

p=p->rchild;

}

}

void main()

{

BiThreTree*T,*Thre;

printf("先序創建二叉樹: ");

T=CreateTree();

Thre=InOrderThrTree(T);

printf(" 中序線索化二叉樹並中序遍歷: ");

InThrTravel(Thre);

}

F. 二叉樹中序遍歷遞歸演算法

if(T){
if(InOrderTraverse(T->l,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->r,Visit)) return OK;
return ERROR;
}else return OK;
以上就是中序遍歷二叉樹
這段程序我全有，具體如下：
#include <alloc.h>

#define ERROR 0;
#define FALSE 0;
#define TRUE 1;
#define OK 1;

typedef int ElemType;
typedef int Status;
typedef int KeyType;

#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))

typedef struct BinaryTree //定義二叉樹
{
ElemType data;
struct BinaryTree *l;
struct BinaryTree *r;
}*BiTree,BiNode;//

BiNode * new()//為新結點開辟空間
{
return( (BiNode *)malloc(sizeof(BiNode)) );
}

CreateSubTree(BiTree *T,ElemType *all,int i)//創建新有子樹
{
if ((all[i]==0)||i>16)
{
*T=NULL;
return OK;
}
*T=new();
if(*T==NULL) return ERROR;
(*T)->data=all[i];
CreateSubTree(&((*T)->l),all,2*i);
CreateSubTree(&((*T)->r),all,2*i+1);
}

CreateBiTree(BiTree *T)//創建新結點
{
ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};
CreateSubTree(T,all,1);
}

printelem(ElemType d)//輸出
{
printf("%d\n",d);
}

PreOrderTraverse(BiTree T,int (*Visit)(ElemType d))//前序遍歷
{
if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->l,Visit))
if(PreOrderTraverse(T->r,Visit)) return OK;
return ERROR;
} else return OK;
}

InOrderTraverse(BiTree T,int (*Visit)(ElemType d))//中序遍歷
{
if(T){
if(InOrderTraverse(T->l,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->r,Visit)) return OK;
return ERROR;
}else return OK;
}

Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){

if(!T) {*p=f;return FALSE;}
else if EQ(key,T->data){ *p=T;return TRUE;}
else if LT(key,T->data) SearchBST(T->l,key,T,p);
else SearchBST(T->r,key,T,p);
}

Status InsertBST(BiTree *T,ElemType e){
BiTree p;
BiTree s;
if(!SearchBST(*T,e,NULL,&p)){
s=(BiTree)malloc(sizeof(BiNode));
s->data=e;s->l=s->r=NULL;
if(!p) *T=s;
else if (LT(e,p->data)) p->l=s;
else p->r=s;
return TRUE;
}
else return FALSE;
}

void Delete(BiTree *p){
BiTree q,s;
if(!(*p)->r){
q=(*p);
(*p)=(*p)->l;
free(q);
}
else if(!(*p)->l){
q=(*p);
(*p)=(*p)->r;
free(q);
}
else {

/* q=(*p);
s=(*p)->l;
while(s->r) {q=s; s=s->r;}
(*p)->data=s->data;
if(q!=(*p) ) q->r=s->l;
else q->l=s->l;
free(s);
*/

q=s=(*p)->l;
while(s->r) s=s->r;
s->r=(*p)->r;
free(*p);
(*p)=q;

}
}

Status DeleteBST(BiTree *T,KeyType key){
if (!(*T) )
{return FALSE;}
else{
if ( EQ(key,(*T)->data)) Delete(T);
else if ( LT(key,(*T)->data)) DeleteBST( &((*T)->l), key);
else DeleteBST( &((*T)->r),key);
return TRUE;
}
}

main()
{
BiTree root;
BiTree sroot=NULL;
int i;
int a[10]={45,23,12,3,33, 27,56,90,120,62};
system("cls");
CreateBiTree(&root);
printf("PreOrderTraverse:\n");
PreOrderTraverse(root,printelem);
printf("InOrderTraverse:\n");
InOrderTraverse(root,printelem);
for(i=0;i<10;i++)
InsertBST(&sroot,a[i]);
printf("InOrderTraverse:\n");
InOrderTraverse(sroot,printelem);
for(i=0;i<3;i++)
DeleteBST(&sroot,a[i]);
printf("Now sroot has nodes:\n");
InOrderTraverse(sroot,printelem);
}

G. 求數據結構作業：寫一中序遍歷二叉樹T的遞歸演算法 ！ 為謝~

//***********************************************************
//頭文件
#include<stdio.h>
#include<stdlib.h>
//***********************************************************
//宏定義
#define OK 1
#define ERROR 0
#define OVERFLOW 0

//***********************************************************

typedef struct BiTNode{
//二叉樹二叉鏈表存儲結構
char data;
struct BiTNode *lChild,*rChild;
}BiTNode,*BiTree;
//***********************************************************
int CreateBiTree(BiTree &T){
//按先序次序輸入二叉中樹結點的值，空格表示空樹
//構造二叉鏈表表示的二叉樹T
char ch;
fflush(stdin);
scanf("%c",&ch);
if(ch==' ')T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
return(OVERFLOW);
T->data=ch;
CreateBiTree(T->lChild);
CreateBiTree(T->rChild);
}
return(OK);
}
//*********************************************************
void PreOrderTraverse(BiTree T){
//採用二叉鏈表存儲結構，先序遍歷二叉樹的遞歸演算法
if(T){
printf("%c",T->data);
PreOrderTraverse(T->lChild);
PreOrderTraverse(T->rChild);
}
}
/***********************************************************
void InOrderTraverse(BiTree T){
//採用二叉鏈表存儲結構，中序遍歷二叉樹的遞歸演算法
if(T){
InOrderTraverse(T->lChild);
printf("%c",T->data);
InOrderTraverse(T->rChild);
}
}*/
//***********************************************************
void PostOrderTraverse(BiTree T){
//採用二叉鏈表存儲結構，後序遍歷二叉樹的遞歸演算法
if(T){
PostOrderTraverse(T->lChild);
PostOrderTraverse(T->rChild);
printf("%c",T->data);
}
}

//***********************************************************
void main(){
//主函數分別實現建立並輸出先、中、後序遍歷二叉樹
BiTNode *Tree;
CreateBiTree(Tree);
printf("\n先序遍歷二叉樹:");
PreOrderTraverse(Tree);
printf("\n中序遍歷二叉樹:");
InOrderTraverse(Tree);
printf("\n後序遍歷二叉樹:");
PostOrderTraverse(Tree);
printf("\n該二叉樹的節點個數：%d",BiTreeCount(Tree));
}

H. 建立二叉樹，層序、先序、中序、後序遍歷（ 用遞歸或非遞歸的方法都需要）以及中序線索化

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define Max 20 //結點的最大個數typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定義二叉樹的結點類型typedef BinTNode *BinTree; //定義二叉樹的指針int NodeNum,leaf; //NodeNum為結點數，leaf為葉子數
//==========基於先序遍歷演算法創建二叉樹==============
//=====要求輸入先序序列，其中加入虛結點"#"以示空指針的位置==========
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //讀入#，返回空指針
else{
T=(BinTNode *)malloc(sizeof(BinTNode)); //生成結點
T->data=ch;
T->lchild=CreatBinTree(); //構造左子樹
T->rchild=CreatBinTree(); //構造右子樹
return(T);
}
}
//========NLR 先序遍歷=============
void Preorder(BinTree T)
{
if(T) {
printf("%c",T->data); //訪問結點
Preorder(T->lchild); //先序遍歷左子樹
Preorder(T->rchild); //先序遍歷右子樹
}
}
//========LNR 中序遍歷===============
void Inorder(BinTree T)
{
if(T) {
Inorder(T->lchild); //中序遍歷左子樹
printf("%c",T->data); //訪問結點
Inorder(T->rchild); //中序遍歷右子樹
}
}
//==========LRN 後序遍歷============
void Postorder(BinTree T)
{
if(T) {
Postorder(T->lchild); //後序遍歷左子樹
Postorder(T->rchild); //後序遍歷右子樹
printf("%c",T->data); //訪問結點
}
}
//=====採用後序遍歷求二叉樹的深度、結點數及葉子數的遞歸演算法========
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求結點數
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度為0，即為葉子。
return(max+1);
}
else return(0);
}
//====利用"先進先出"（FIFO）隊列，按層次遍歷二叉樹==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定義結點的指針數組cq
cq[1]=T; //根入隊
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出隊
printf("%c",p->data); //出隊，輸出結點的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子樹入隊
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子樹入隊
}
}
}
//==========主函數=================
void main()
{
BinTree root;
int i,depth;
printf("\n");
printf("Creat Bin_Tree;Input preorder:"); //輸入完全二叉樹的先序序列，
// 用#代表虛結點，如ABD###CE##F##
root=CreatBinTree(); //創建二叉樹，返回根結點
//do { //從菜單中選擇遍歷方式，輸入序號。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t5: Level Depth\n"); //按層次遍歷之前，先選擇4，求出該樹的結點數。
printf("\t0: Exit\n");
printf("\t*******************************\n");
do { //從菜單中選擇遍歷方式，輸入序號。
scanf("%d",&i); //輸入菜單序號（0-5）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍歷
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍歷
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //後序遍歷
break;
case 4: depth=TreeDepth(root); //求樹的深度及葉子數
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5: printf("LevePrint Bin_Tree: ");
Levelorder(root); //按層次遍歷
break;
default: exit(1);
}
printf("\n");
} while(i!=0);
}

I. 中序遞歸遍歷二叉樹的演算法（數據結構）

有哪位高手幫忙分析下以下程序：#include"iostream.h"
#define
maxnode
100
typedef
char
datatype;
typedef
struct
bitnode{
datatype
data;//存儲數據信息的信息域
struct
bitnode
*lchild,*rchild;//左右孩子指針
}bitnode,*bitree;void
createbitree(bitree
*t){//創建一棵已生成左右子樹的二叉樹的演算法char
ch;cin>>ch;if(ch=='0')(*t)=null;else{(*t)=new
bitnode;
(*t)->data=ch;
createbitree(&(*t)->lchild);
createbitree(&(*t)->rchild);}}int
inorderout(bitree
bt)
{//非遞歸中序遍歷二叉樹
bitree
stack[maxnode],p;int
top;if(bt==null)
return
1;//空樹
top=-1;//棧頂指針初始化p=bt;while(!(p==null&&top==-1))
{
while(p!=null)
{
if(top
lchild;//指針指向p的左孩子結點}if(top==-1)
return
1;//棧空時結束else{p=stack[top];//從棧中彈出棧頂元素
cout<
data;top--;p=p->rchild;//指針指向p的右孩子結點}}}void
main()
//主函數{bitree
bt;int
n;cout<<"
***************二叉樹***************"<
>n;switch(n){case
0:break;
case
1:createbitree(&bt);break;case
2:cout<<"中序遍歷輸出二叉樹為：";

J. 怎樣用遞歸演算法實現先序線索二叉樹，並遍歷這個樹啊

基本演算法很簡單的。
void ProSearch(TREE T)//TREE是指針
{
if(T->left)//遍歷左邊
ProSearch(T->left);
print(T);//列印本節點的元素
if(T->right)//遍歷右邊
ProSearch(T->right);
}