给定二叉树，设计程序构造和遍历二叉树：
前序遍历输入，后序遍历输出
例如二叉树：
输入序列
ABD..EH...CF.I..G..
输出结果为：
DHEBIFGCA
基本思想：
采用递归建立和遍历二叉树
建立：先建立根节点，然后建立左、右子树
遍历：左、右、根
源程序：
#include<malloc.h>
#include <stdio.h>
struct node{
char info;
struct node *llink, *rlink;
};
typedef
struct node NODE;
NODE *create(){
char x;
NODE *p;
scanf(
"%c", &x);
printf(
"%c", x);
if(x!='.'){
p=(NODE *)malloc(
sizeof(NODE));
p->info=x;
p->llink=create();
p->rlink=create();
}
else
p=NULL;
return p;
}
void run(NODE *t){
if(t){
run(t->llink);
run(t->rlink);
printf(
"%c", t->info);
}
}
main()
{
NODE *T;
printf(
"Please input a tree:\n" );
T=create();
printf(
"\n");
if(!T)
printf(
"This is a empty binary tree.");
else
{
printf(
"The result of post travese is: \n");
run(T);
}
printf(
"\n");
}
编写递归算法，计算二叉树中叶子节点的数目：
源代码：
代码：
#include<malloc.h>
#include <stdio.h>
struct node{
char info;
struct node *llink, *rlink;
};
typedef
struct node NODE;
NODE *create(){
char x;
NODE *p;
scanf(
"%c", &x);
printf(
"%c", x);
if(x!='.'){
p=(NODE *)malloc(
sizeof(NODE));
p->info=x;
p->llink=create();
p->rlink=create();
}
else
p=NULL;
return p;
}
int run(NODE *t){
static
int count=0;
if(t){
run(t->llink);
run(t->rlink);
if(t->llink ==NULL && t->rlink == NULL) {
count++;
}
}
return count;
}
main()
{
NODE *T;
int left_number;
printf(
"Please input a tree:\n" );
T=create();
printf(
"\n");
if(!T)
printf(
"This is a empty binary tree.");
else
{
left_number=run(T);
printf(
"There are %d leaves in this binary tree. \n", left_number);
}
printf(
"\n");
}
编写递归算法，在二叉树中求位于先序序列中第K个位置的节点。
#include<malloc.h>
#include <stdio.h>
struct node{
char info;
struct node *llink, *rlink;
};
typedef
struct node NODE;
NODE *create(){
char x;
NODE *p;
scanf(
"%c", &x);
// printf("%c", x);
if(x!='.'){
p=(NODE *)malloc(
sizeof(NODE));
p->info=x;
p->llink=create();
p->rlink=create();
}
else
p=NULL;
return p;
}
run(NODE *t,
int k){
static
int i=0;
if(t&&i!=k)
{
i++;
if(i==k) printf(
"%c",t->info);
else
{
run(t->llink,k);
run(t->rlink,k);
}
}
}
main()
{
NODE *T;
int k;
printf(
"Please input a tree:\n" );
T=create();
printf(
"\n");
printf(
"input k:\n");
scanf(
"%d", &k);
if(!T)
printf(
"This is a empty binary tree.");
else
{
run(T,k);
}
printf(
"\n");
}
本文转自 fsjoy1983 51CTO博客，原文链接：http://blog.51cto.com/fsjoy/113510，如需转载请自行联系原作者
