C语言的二叉树中序遍历问题。

2024-12-23 08:08:42

推荐回答（5个）

回答1：

#include
#include
#define STACK_MAX_SIZE 30
#define QUEUE_MAX_SIZE 30
#ifndef elemType
typedef char elemType;
#endif
/************************************************************************/
/* 以下是关于二叉树操作的11个简单算法 */
/************************************************************************/
struct BTreeNode{
elemType data;
struct BTreeNode *left;
struct BTreeNode *right;
};

/* 1.初始化二叉树 */
void initBTree(struct BTreeNode* *bt)
{
*bt = NULL;
return;
}

/* 2.建立二叉树(根据a所指向的二叉树广义表字符串建立) */
void createBTree(struct BTreeNode* *bt, char *a)
{
struct BTreeNode *p;
struct BTreeNode *s[STACK_MAX_SIZE];/* 定义s数组为存储根结点指针的栈使用 */
int top = -1; /* 定义top作为s栈的栈顶指针，初值为-1,表示空栈 */
int k; /* 用k作为处理结点的左子树和右子树，k = 1处理左子树，k = 2处理右子树 */
int i = 0; /* 用i扫描数组a中存储的二叉树广义表字符串，初值为0 */
*bt = NULL; /* 把树根指针置为空，即从空树开始建立二叉树 */
/* 每循环一次处理一个字符，直到扫描到字符串结束符\0为止 */
while(a[i] != '\0'){
switch(a[i]){
case ' ':
break; /* 对空格不作任何处理 */
case '(':
if(top == STACK_MAX_SIZE - 1){
printf("栈空间太小！\n");
exit(1);
}
top++;
s[top] = p;
k = 1;
break;
case ')':
if(top == -1){
printf("二叉树广义表字符串错误!\n");
exit(1);
}
top--;
break;
case ',':
k = 2;
break;
default:
p = malloc(sizeof(struct BTreeNode));
p->data = a[i];
p->left = p->right = NULL;
if(*bt == NULL){
*bt = p;
}else{
if( k == 1){
s[top]->left = p;
}else{
s[top]->right = p;
}
}
}
i++; /* 为扫描下一个字符修改i值 */
}
return;
}

/* 3.检查二叉树是否为空，为空则返回1,否则返回0 */
int emptyBTree(struct BTreeNode *bt)
{
if(bt == NULL){
return 1;
}else{
return 0;
}
}

/* 4.求二叉树深度 */
int BTreeDepth(struct BTreeNode *bt)
{
if(bt == NULL){
return 0; /* 对于空树，返回0结束递归 */
}else{
int dep1 = BTreeDepth(bt->left); /* 计算左子树的深度 */
int dep2 = BTreeDepth(bt->right); /* 计算右子树的深度 */
if(dep1 > dep2){
return dep1 + 1;
}else{
return dep2 + 1;
}
}
}

/* 5.从二叉树中查找值为x的结点，若存在则返回元素存储位置，否则返回空值 */
elemType *findBTree(struct BTreeNode *bt, elemType x)
{
if(bt == NULL){
return NULL;
}else{
if(bt->data == x){
return &(bt->data);
}else{ /* 分别向左右子树递归查找 */
elemType *p;
if(p = findBTree(bt->left, x)){
return p;
}
if(p = findBTree(bt->right, x)){
return p;
}
return NULL;
}
}
}

/* 6.输出二叉树(前序遍历) */
void printBTree(struct BTreeNode *bt)
{
/* 树为空时结束递归，否则执行如下操作 */
if(bt != NULL){
printf("%c", bt->data); /* 输出根结点的值 */
if(bt->left != NULL || bt->right != NULL){
printf("(");
printBTree(bt->left);
if(bt->right != NULL){
printf(",");
}
printBTree(bt->right);
printf(")");
}
}
return;
}

/* 7.清除二叉树，使之变为一棵空树 */
void clearBTree(struct BTreeNode* *bt)
{
if(*bt != NULL){
clearBTree(&((*bt)->left));
clearBTree(&((*bt)->right));
free(*bt);
*bt = NULL;
}
return;
}

/* 8.前序遍历 */
void preOrder(struct BTreeNode *bt)
{
if(bt != NULL){
printf("%c ", bt->data); /* 访问根结点 */
preOrder(bt->left); /* 前序遍历左子树 */
preOrder(bt->right); /* 前序遍历右子树 */
}
return;
}

/* 9.前序遍历 */
void inOrder(struct BTreeNode *bt)
{
if(bt != NULL){
inOrder(bt->left); /* 中序遍历左子树 */
printf("%c ", bt->data); /* 访问根结点 */
inOrder(bt->right); /* 中序遍历右子树 */
}
return;
}

/* 10.后序遍历 */
void postOrder(struct BTreeNode *bt)
{
if(bt != NULL){
postOrder(bt->left); /* 后序遍历左子树 */
postOrder(bt->right); /* 后序遍历右子树 */
printf("%c ", bt->data); /* 访问根结点 */
}
return;
}

/* 11.按层遍历 */
void levelOrder(struct BTreeNode *bt)
{
struct BTreeNode *p;
struct BTreeNode *q[QUEUE_MAX_SIZE];
int front = 0, rear = 0;
/* 将树根指针进队 */
if(bt != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = bt;
}
while(front != rear){ /* 队列非空 */
front = (front + 1) % QUEUE_MAX_SIZE; /* 使队首指针指向队首元素 */
p = q[front];
printf("%c ", p->data);
/* 若结点存在左孩子，则左孩子结点指针进队 */
if(p->left != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = p->left;
}
/* 若结点存在右孩子，则右孩子结点指针进队 */
if(p->right != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = p->right;
}
}
return;
}

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

/*
int main(int argc, char *argv[])
{
struct BTreeNode *bt; /* 指向二叉树根结点的指针 */
char *b; /* 用于存入二叉树广义表的字符串 */
elemType x, *px;
initBTree(&bt);
printf("输入二叉树广义表的字符串：\n");
/* scanf("%s", b); */
b = "a(b(c), d(e(f, g), h(, i)))";
createBTree(&bt, b);
if(bt != NULL)
printf(" %c ", bt->data);
printf("以广义表的形式输出：\n");
printBTree(bt); /* 以广义表的形式输出二叉树 */
printf("\n");
printf("前序："); /* 前序遍历 */
preOrder(bt);
printf("\n");
printf("中序："); /* 中序遍历 */
inOrder(bt);
printf("\n");
printf("后序："); /* 后序遍历 */
postOrder(bt);
printf("\n");
printf("按层："); /* 按层遍历 */
levelOrder(bt);
printf("\n");
/* 从二叉树中查找一个元素结点 */
printf("输入一个待查找的字符：\n");
scanf(" %c", &x); /* 格式串中的空格跳过空白字符 */
px = findBTree(bt, x);
if(px){
printf("查找成功：%c\n", *px);
}else{
printf("查找失败！\n");
}
printf("二叉树的深度为：");
printf("%d\n", BTreeDepth(bt));
clearBTree(&bt);
return 0;
}

回答2：

#include "stdio.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 10 //栈的初始长度
#define STACKINCREMENT 5 //栈的追加长度

typedef struct bitree{
char data;
struct bitree *lchild,*rchild;
}bitree; //二叉树结点定义

typedef struct {
bitree **base;
bitree **top;
int stacksize;
}sqstack; // 链栈结点定义top栈顶 base栈底且栈元素是指向二叉树结点的二级指针
//建立一个空栈
int initstack(sqstack *s)
{s->base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree)); //栈底指向开辟空间
if(!s->base) exit(1); //抛出异常
s->top=s->base; //栈顶=栈尾表示栈空
s->stacksize=STACK_INIT_SIZE; //栈长度为开辟空间大小
return 1;
}
//进栈
int 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) exit(1); //抛出异常
s->top=s->base+s->stacksize; //感觉这一句没用
s->stacksize+=STACKINCREMENT;}
*(s->top)=e;s->top++; //进栈栈顶后移
return 1;
}
//出栈
int pop(sqstack *s,bitree **e)
{if(s->top==s->base) return 0; //栈空返回0
--s->top;*e=*(s->top); //栈顶前移取出栈顶元素给e
return 1;}
//取栈顶
int gettop(sqstack *s,bitree **e) //去栈顶元素注意top指向的是栈顶的后一个
{if(s->top==s->base) return 0; //所以 s->top-1
*e=*(s->top-1);
return 1;
}
/*------------------------非递归-----先序建立二叉树----------------------------------*/
bitree *createprebitree()
{char ch;bitree *ht,*p,*q;
sqstack *s;
s=malloc(sizeof(bitree)); //加上这一句为s 初始化开辟空间
ch=getchar();
if(ch!='#'&&ch!='\n') /* 输入二叉树先序顺序是以完全二叉树的先序顺序
不是完全二叉树的把没有的结点以#表示 */
{ht=(bitree *)malloc(sizeof(bitree));
ht->data=ch;
ht->lchild=ht->rchild=NULL;
p=ht;
initstack(s);
push(s,ht); //根节点进栈
while((ch=getchar())!='\n') // 算
{if(ch!='#') {q=(bitree *)malloc(sizeof(bitree)); // 法
q->data=ch; //
if(p==*(s->top-1)) p->lchild=q; // 核
else p->rchild=q; //
push(s,q);p=q; // 心
} //
else {if(p==*(s->top-1)) p->lchild=NULL; // 的
else p->rchild=NULL; //
pop(s,&p);} // 步
//
} // 骤
return ht;
}
else return NULL;
}
/*--------------------------递归---------先序建立二叉树-------------------------------*/
void CreateBiTree(bitree **T) {
//按先序次序输入二叉树中的结点的值（一个字符），空格字符表示空树，
//构造二叉链表表示二叉树
char ch;
scanf("%c",&ch);
if(ch=='#') *T=NULL;
else{
*T=(bitree * )malloc(sizeof(bitree));
if(!*T) exit(1);
(*T)->data=ch; //生成根结点
CreateBiTree(&(*T)->lchild); //构造左子树
CreateBiTree(&(*T)->rchild); //构造右子树
}
}
/*--------------------------非递归-------中序建立二叉树-------------------------------*/
/*--------------------------递归---------中序建立二叉树-------------------------------*/
/*--------------------------非递归-------后序建立二叉树-------------------------------*/
/*--------------------------递归---------后序建立二叉树-------------------------------*/

/*-----------------------非递归------先序输出二叉树------------------------------*/
void preordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);printf("%c",h->data);h=h->lchild;}
else{pop(&m,&h);
h=h->rchild;}
}
}
/*------------------------非递归-----中序输出二叉树----------------------------*/
void inordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);h=h->lchild;}
else {
pop(&m,&h);
printf("%c",h->data);
h=h->rchild;
}
}
}
/*---------------------非递归----后序遍历二叉树----------------------------------*/
void postordertraverse(bitree *h)
{
sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {
push(&m,h);
h=h->lchild;}
else {
bitree *r; //使用r结点表示访问了右子树代替标志域
gettop(&m,&h);
if(h->rchild&&h->rchild!=r)
{h=h->rchild;
push(&m,h);
h=h->lchild;}
else{pop(&m,&h);
printf("%c",h->data);
r=h;h=NULL;}
}
}
}
//层次遍历二叉树用队列哈哈以后做
/*-------------------------------主过程-------------------------------*/
int main()
{bitree *ht;
printf("先序非递归建立一个二叉树:");
if((ht=createprebitree())!=NULL) //非递归建立
//CreateBiTree(&ht);
//if(ht!=NULL) //递归建立
{
printf("先序遍历输出二叉树:");
preordertraverse(ht);
putchar('\n');
printf("中序遍历输出二叉树:");
inordertraverse(ht);
putchar('\n');
printf("后序遍历输出二叉树:");
postordertraverse(ht);
putchar('\n');
}
else printf("空二叉树\n");
}
这是先序递归和非递归建立二叉树和先、中、后的遍历输出

回答3：

#include
#include

typedef struct node
{
int data;
struct node *lchl,*rchl;
}NODE;

void create(NODE **t) //建立
{
int a;
scanf("%d",&a);
if(a)
{
*t=(NODE*)malloc(sizeof(NODE));
(*t)->data=a;
create(&((*t)->lchl));
create(&((*t)->rchl));
}
else
t=NULL;
}

void print(NODE *T) //中序遍历
{
if(T)
{
print(T->lchl);
printf("%4d",T->data);
print(T->rchl);
}
}

int main()
{
NODE *root;
create(&root);
print(root);

return 0;
}
要建立二叉树：
1
2 3
4 5 6 7
则应输入 1 2 4 0 0 5 0 0 3 6 0 0 7 0 0
输出为4 2 5 1 6 3 7
输入顺序为先根序，输出为中根序。
二楼的修改方法也是正确的。

回答4：

首先，有一点你要认识到：如果通过create()子函数操纵二叉树，实际上root的从初始化的时候根本没发生改变，一旦create（）,执行完，create中的变量的生命周期就结束了。因此程序跟
void main()
{
NODE *root;
print(root);
}
等价没有初始化root的值；

回答5：

#include
#include

typedef struct node
{
int data;
struct node *lchl,*rchl;
} NODE;

NODE *create(NODE *t) //函数带有返回值以影响调用者
{
int a;
scanf("%d",&a);
if(a)
{
t=(NODE*)malloc(sizeof(NODE));
t->data=a ;
t->lchl = create(t->lchl);
t->rchl = create(t->rchl);
return t ; // 此处返回刚才申请单元的指针 t
}
else
return NULL; // 无子树返回 NULL
}

void print(NODE *T) //中序遍历
{
if(T)
{
print(T->lchl);
printf("%4d",T->data);
print(T->rchl);
}
}

void main()
{
NODE *root;
root = create(root) ; // 接收返回值
print(root);
printf("\n") ;
}

// 关键就是你没理解子程序中改变的值不一定能影响调用者环境中变量的
// 值得，常见的方法有引用，指针，全局变量，这里二叉树用这种指针返回值，调用者
// 接收返回值来达到影响的目的，比较好