二叉树中序遍历线索化递归算法

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);
}