设二叉树的存储结构为二叉链表，编写有关二叉树的递归算法：

若二叉树采用二叉链表存储结构，试编写中序遍历二叉树的递归算法~

非递归，就是采用前序/中序/后序遍历所有节点，并统计。下面就给你提供//二叉树结构体 struct BTNode { int data; BTNode *rchild; BTNode *

#include
#include
#include

#define STACK_INT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2

typedef char TElemType;
typedef int Status;
typedef char SElemType;

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

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

typedef struct QNode
{
BiTree Queuedata;
struct QNode * next;
}QNode,* QueuePtr;

typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;

Status InitStack(SqStack &S)
{
S.base = (BiTree *) malloc(sizeof(BiTree));
if(!S.base) exit(OVERFLOW);
S.top = S.base;
S.stacksize = STACK_INT_SIZE;
return OK;
}

Status GetTop(SqStack &S, BiTree &e)
{
if(S.top == S.base) return ERROR;
e = *(S.top-1);
return OK;
}

Status Push(SqStack &S, BiTree e)
{
if(S.top - S.base >= S.stacksize)
{
S.base = (BiTree *) realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(BiTree));
if(!S.base) return ERROR;
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top = e;
S.top++;
return OK;
}

Status Pop(SqStack &S,BiTree &e)
{
if(S.base == S.top) return ERROR;
S.top--;
e = *S.top;
return OK;
}

Status StackEmpty(SqStack S)
{
if(S.top == S.base) return TRUE;
else return FALSE;
}

Status PreOrderCreateBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch);
if(ch == '0') T = NULL;
else
{
if(!(T = (BiTNode* ) malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data = ch;
PreOrderCreateBiTree(T->lchild);
PreOrderCreateBiTree(T->rchild);
}
return OK;
}

void PreOrder ( BiTree bt )
{
if ( bt )
{
printf("%c",bt->data);
PreOrder ( bt->lchild );
PreOrder ( bt->rchild );
}
}

void Inorder ( BiTree bt )
{
if ( bt )
{
Inorder ( bt->lchild );
printf("%c",bt->data);
Inorder ( bt->rchild );
}
}

void LastOrder ( BiTree bt )
{
if ( bt )
{
LastOrder( bt->lchild );
LastOrder( bt->rchild );
printf("%c",bt->data);
}
}

Status PreOrderTraverse(BiTree T)
{
SqStack s;
BiTree P=T;
InitStack(s);
while ( P!=NULL || !StackEmpty(s))
{
if (P!=NULL)
{
printf("%c",P->data);
Push(s,P);
P=P->lchild;
}
else
{
Pop(s,P);
P=P->rchild;
}
}
return OK;
}

Status InOrderTraverse(BiTree T)
{
SqStack S;
InitStack(S);
BiTree p;
p = T;
while(p || !StackEmpty(S))
{
if(p)
{
Push(S,p);
p = p->lchild;
}
else
{
Pop(S,p);
printf("%c",p->data);
p = p->rchild;
}
}
return OK;
}

Status LastOrderTraverse(BiTree T)
{
SqStack s,tag;
BiTree f,m,n,P=T;
m=(BiTNode*)malloc(sizeof(BiTNode));
m->data=1;
m->lchild=NULL;
m->rchild=NULL;
n=(BiTNode*)malloc(sizeof(BiTNode));
n->data=2;
n->lchild=NULL;
n->rchild=NULL;
InitStack(s);
InitStack(tag);
while (P ||!StackEmpty(s))
{
if (P)
{
Push(s,P);
Push(tag,m);
P=P->lchild;
}
else
{
Pop(s,P);
Pop(tag,f);
if (f==m)
{
Push(s,P);
Push( tag, n);
P=P->rchild;
}
else
{
printf("%c",P->data);
P=NULL;

}
}
}
return OK;
}

Status InitQueue(LinkQueue &Q)
{
Q.front=(QNode*)malloc(sizeof(QNode));
if (!Q.front)
exit(OVERFLOW);
Q.rear=Q.front;
Q.front->next=NULL;
return OK;
}

Status EnQueue(LinkQueue &Q,BiTree e)
{
QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
if (!s)
exit(OVERFLOW);
s->Queuedata=e;
s->next=NULL;
Q.rear->next=s;
Q.rear=s;
return OK;
}

int DelQueue(LinkQueue &Q, BiTree &e)
{
char data1;
QueuePtr s;
s=Q.front->next;
e=s->Queuedata;
data1=e->data;
Q.front->next=s->next;
if(Q.rear==s)
Q.rear=Q.front;
free(s);
return TRUE;
}

Status QueueEmpty(LinkQueue Q)
{
if (Q.front->next==NULL)
return OK;
else return ERROR;
}

Status HierarchyBiTree(BiTree bt)
{
LinkQueue Q;
InitQueue(Q);
BiTree p = bt;
if (bt == NULL) return ERROR;
EnQueue(Q,p);
while (!QueueEmpty(Q))
{
DelQueue(Q, p);
printf("%C",p->data);
if (p->lchild)
EnQueue(Q, p->lchild);
if (p->rchild)
EnQueue(Q, p->rchild);
}
return OK;
}

int sum=0;
int SumLefts(BiTree bt)
{
if (bt!=NULL)
{
if (bt->lchild==NULL && bt->rchild==NULL)
{
sum++;
}
sum=SumLefts(bt->lchild);
sum=SumLefts(bt->rchild);
}
return(sum);
}


void main()
{
printf("请输入先序建立二叉树所需要的数据(空树用0表示)：

");
BiTree t;
PreOrderCreateBiTree(t);
printf("

");
printf("递归遍历输出为：
");
printf("先序输出： ");
PreOrder(t);
printf("
");
printf("中序输出： ");
Inorder(t);
printf("
");
printf("后序输出： ");
LastOrder(t);
printf("


");
printf("非递归遍历输出为：
");
printf("先序输出： ");
PreOrderTraverse(t);
printf("
");
printf("中序输出： ");
InOrderTraverse(t);
printf("
");
printf("后序输出： ");
LastOrderTraverse(t);
printf("


");
printf("按层次遍历输出为： ");
HierarchyBiTree(t);
printf("



");
printf("二叉树中叶子节点个数为：");
int leaves=SumLefts(t);
printf("%d",leaves);
printf("
");
}

给了一个程序给你参考，有前中后序遍历，实现了前5个功能。
提示：8功能可以用任意一种遍历方法，在程序中，将打印字符的部分换成自己的判断程序即可。
6功能用后续遍历，当遍历到任意一节点时，判断其孩子是不是叶子，是就删除。
7功能参考求广度的实现】
9功能参考6功能，用前序遍历也可以
10功能也参考求广度的方法
程序：
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

#define NUM_NODE 12
#define MOST_DEPTH 10

typedef struct BiTree{
int data;
BiTree *lchild;
BiTree *rchild;
}BiTree;

typedef struct Answear{
int Degree0;
int Degree1;
int Degree2;
int Depth;
} Answear;

BiTree* CreateTree(int n)
{
BiTree *t;
if (n <= 0 || n> NUM_NODE) return NULL;
if (!(t = (BiTree*)malloc(sizeof(BiTree))))
return NULL;
t->data = n;
printf("%d ", t->data);
t->lchild = CreateTree(2*n);
t->rchild = CreateTree(2*n+1);
return t;
}

void FreeTree(BiTree *t)
{
if (t)
{
if (t->lchild)
FreeTree(t->lchild);
if (t->rchild)
FreeTree(t->rchild);
printf("%d ", t->data);
free(t);
}
}
//中序遍历
void InOrder(BiTree *t)
{
BiTree **stack, **top, *p;
//创建堆栈
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
//初始化堆栈
top = stack;
p = t;
while (p || top>stack)//p不为NULL，堆栈不空
if (p)
{
*top++ = p;//p入堆栈
p = p->lchild;
}
else
{
p = *--top;//p出栈
if (p) printf("%d ", p->data);
p = p->rchild;
}
}

//前序遍历
void PreOrder(BiTree *t)
{
BiTree **stack, **top, *p;

if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}

top = stack;
p = t;
while (p || top>stack)
if (p)
{
*top++ = p;
if (p) printf("%d ", p->data);
p = p->lchild;
}
else
{
p = *--top;
p = p->rchild;
}
}

//后序遍历
void PostOrder(BiTree *t)
{
BiTree **stack, **top, *p, *p_old, *p_new;
int Flag;

if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}

top = stack;
Flag = 0;
*top++ = t;
while (top > stack)
{
p = *(top-1);
if (p->lchild && !Flag)
*top++ = p->lchild;
else
{
if (p->rchild)
{
*top++ = p->rchild;
Flag = 0;
}
else
{
p_old = *--top;
printf("%d ", p_old->data);
while (top > stack)
{
p_new = *(top-1);
if (p_old == p_new->lchild)
{
Flag = 1;
break;
}
else
{
p_new = *--top;
printf("%d ", p_new->data);
p_old = p_new;
Flag = 0;
}
}
}
}
}
}

//中序遍历求结点的深度和度为0，1,2的结点数，结果保存在pAns指的。。。
void InOrderDO(BiTree *t , Answear * pAns)
{
//遍历用的数据
BiTree **stack, **top, *p;
//求深度的数据
int curDeep, MostDeep;
//创建堆栈
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
//初始化堆栈
top = stack;
p = t;
//初始化数据
curDeep = MostDeep = 0;
pAns->Degree0 = pAns->Degree1 = pAns->Degree2 = 0;

//遍历循环
while (p || top>stack)//p不为NULL，堆栈不空
if (p)
{
*top++ = p;//p入堆栈
p = p->lchild;
curDeep++;
if (MostDeep < curDeep) MostDeep = curDeep; //保存最深度
}
else
{
p = *--top;//p出栈
curDeep--;
//if (p) printf("%d ", p->data); //Visit结点
//计算个结点的度
if (p->lchild && p->rchild) pAns->Degree2++;
else if (p->lchild || p->rchild) pAns->Degree1++;
else pAns->Degree0++;

p = p->rchild;
}
//得到深度
pAns->Depth = MostDeep;

return ;
}

//前序递归求广度
void Pre(BiTree *T, int* woed, int depth)
{
woed[depth]++;
if (T->lchild) Pre(T->lchild, woed, depth+1);
if (T->rchild) Pre(T->rchild, woed, depth+1);
}

//求广度的程序，返回值为广度
int GetTreeWidth(BiTree *root)
{
int i, WidthOfEachDepth[MOST_DEPTH]={0};

Pre(root, WidthOfEachDepth, 0);

for (i=1; i<MOST_DEPTH; i++)
if (WidthOfEachDepth[0] < WidthOfEachDepth[i])
WidthOfEachDepth[0] = WidthOfEachDepth[i];
return WidthOfEachDepth[0];
}

int main()
{
BiTree *root;
Answear ans;

printf("Create Tree\n");
root = CreateTree(1);
printf("\nInOrder\n");
InOrder(root);
printf("\nPreOrder\n");
PreOrder(root);
printf("\nPostOrder\n");
PostOrder(root);

InOrderDO(root, &ans);
printf("\nTheMostDepth is : %d\n", ans.Depth);
printf("TheMostWidth is : %d\n", GetTreeWidth(root));
printf("Each Degree (0,1,2)is: (%d, %d, %d)\n",
ans.Degree0, ans.Degree1, ans.Degree2);

printf("\nFree Tree\n");
FreeTree(root);
return 0;
}

---

龙子湖区18999539790： 设二叉树的存储结构为二叉链表,编写有关二叉树的递归算法:(1)统计二叉树中度为1的结点个数.(2)统计二叉树中度为2的结点个数.(3)统计二叉树中度... - ？
骑畏重组：[答案] 给了一个程序给你参考,有前中后序遍历,实现了前5个功能.提示:8功能可以用任意一种遍历方法,在程序中,将打印字符的部分换成自己的判断程序即可.6功能用后续遍历,当遍历到任意一节点时,判断其孩子是不是叶子...

龙子湖区18999539790： 假设二叉树采用二叉链表作为存储结构,试编写一个算法:求任意一个指定结点所在的层次. - ？
骑畏重组： 非递归中序遍历 构造变量count记录当前层访问到的节点数,nextcount记录当前层的总个数; 每当访问过一层层数depth++; 此种方法同时可以求最大宽度,访问第几层的第几个节点,求带权路径长度WPL,是一种通用方法! int TreeDepth(...

龙子湖区18999539790： 假设二叉树用二叉链表存储结构.编写一个算法统计二叉树的结点个数. - ？
骑畏重组： int BiTreeCount(BiTree T) { int rNum,lNum; if(!T) return 0; else { lNum = BiTreeCount(T->lchild); rNum = BiTreeCount(T->rchild); return rNum + lNum + 1; }}

龙子湖区18999539790： 设一棵二叉树以二叉链表为存储结构 - ？
骑畏重组： void Leaf(BiTree T) {if(T=null){ return 0; } elseif(T->lchild==null&&T->rchild==null){ return 1; } else return leaves(T->lchild)+leaves(T->rchild); }

龙子湖区18999539790： 设一棵二叉树以二叉链表为存储结构,试写出求该二叉树中所有叶子结点数的算法. - ？
骑畏重组： //我做了一个程序,可以实现二叉树的左右子树的交换功能,#include<iostream.h>/* 二叉树类型的定义(二叉链表形式储存) */ typedef char datatype; // 树的结点数据类型为字符型,可以根据需要修改 typedef struct node *pointer; // 定义二叉...

龙子湖区18999539790： 假设以二叉链表作为二叉树的存储结构,试编写一个求树的高度的算法 - ？
骑畏重组： int length(BiTree T) { int h1,h2; if(T==NULL) return 0; if(T->lchild==NULL && T->rchild==NULL) return 1; h1=length(T->lchild); h2=length(T->rchild); return h1>=h2?h1:h2; } BiTree Find(BiTree T,ElemType x) //该函数2113返回5261给4102定值的1653结...

龙子湖区18999539790： 若用二叉链表作为二叉树的存储表示,试编写算法交换二叉树中各结点的左右子数. - ？
骑畏重组： 递归:void exchange(BTree *rt){ BTree *temp = NULL; if(rt->lchild == NULL && rt->rchild == NULL) return; else{ temp = rt->lchild; rt->lchild = rt->rchild; rt->rchild = temp; } if(rt->lchild) exchange(rt->lchild); if(rt->rchild) exchange(rt->rchild); } 非递归:...

龙子湖区18999539790： (1)以二叉链表作为二叉树的存储结构,写出二叉树的存储结构定义(C或C++表示). (2)编程实现以二叉链 - ？
骑畏重组： 思想上,可以构造“节点”这种结构体,该结构体包含自身的值,还有左孩子指针,右孩子指针.朝这个方向自己构思,希望能帮到你!欢迎追问

龙子湖区18999539790： 用C语言编写:建立一棵以二叉链表结构存储的二叉树,并对其进行遍历.求该二叉树中的结点个数等操作. - ？
骑畏重组： 存储结构 typedef struct { int weight; int parent, lchild, rchild; } HTNode ,*HuffmanTree; // 动态分配数组存储huffman树 算法设计 void createHuffmantree(){ ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode);// 动态分配数组存储huffman树,0号单元未用// m:huffman 树中的结点数(m=2*n-1)

龙子湖区18999539790： 用C++程序语言:以二叉链表作存储结构,编写一个算法将二叉树左、右子树进行交换的程序 - ？
骑畏重组： template t search(bstnode* tree, const t& elemt) { stack*> travstack; bstnode *p = root; //遍历指针 bstnode *q = root; //层数看守 int num = 1; if(p != null) travstack.push(p); while(!travstack.empty()) { p = travstack.pop(); if(p->data != elemt) if(p == q) ...