c++或c语言-遍历二叉树
发布网友
发布时间：2022-05-21 05:23
共2个回答
热心网友
时间：2023-10-15 18:41
{
char data;
struct bitnode *lchild, *rchild;
}bitnode, *bitree;
void createbitree(t,n)
bitnode ** t;
int *n;
{
char x;
bitnode *q;
*n=*n+1;
printf("\n Input %d DATA:",*n);
x=getchar();
if(x!='\n') getchar();
if (x=='\n')
return;
q=(bitnode*)malloc(sizeof(bitnode));
q->data=x;
q->lchild=NULL;
q->rchild=NULL;
*t=q;
printf(" This Address is: %o, Data is: %c,\n Left Pointer is: %o, Right Pointer is: %o",q,q->data,q->lchild,q->rchild);
createbitree(&q->lchild,n);
createbitree(&q->rchild,n);
return;
}
void visit(e)
bitnode *e;
{
printf(" Address: %o, Data: %c, Left Pointer: %o, Right Pointer: %o\n",e,e->data,e->lchild,e->rchild);
}
void preordertraverse(t)
bitnode *t;
{
if(t)
{
visit(t);
preordertraverse(t->lchild);
preordertraverse(t->rchild);
return ;
}
else
return ;
}
void countleaf(t,c)
bitnode *t;
int *c;
{
if(t!=NULL)
{
if (t->lchild==NULL && t->rchild==NULL)
{*c=*c+1;
}
countleaf(t->lchild,c);
countleaf(t->rchild,c);
}
return;
}
int treehigh(t)
bitnode *t;
{
int lh,rh,h;
if(t==NULL)
h=0;
else
{
lh=treehigh(t->lchild);
rh=treehigh(t->rchild);
h=(lh>rh ? lh:rh)+1;
}
return h;
}
main()
{
bitnode *t; int count=0;
int n=0;
printf("\n Please input TREE Data:\n");
createbitree(&t,&n);
printf("\n This is TREE struct: \n");
preordertraverse(t);
countleaf(t,&count);
printf("\n This TREE has %d leaves ",count);
printf(" , High of The TREE is: %d\n",treehigh(t));
}
我这个是比较复杂的，如果用stl，可能会简单些。
热心网友
时间：2023-10-15 18:42
二叉树的建立用先序与中序，分析
编辑 | 删除 | 权限设置 | 更多▼ 更多▲ 设置置顶 推荐日志 转为私密日志 jasper 发表于2010年04月25日 16:30 阅读(1) 评论(1)
分类： 编写 权限: 公开
欢迎上我的百度空间，
http://hi.baidu.com/%C1%F5%BB%C0%CD%A51989/blog/item/9e38cd3932a99028b8998fbc.html
/* 请用中序和先序来建立一个二叉树*/
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define NULL 0
struct node
{ char data;
struct node *lchild,*rchild;
};
/*这个是建立一个二叉树的存储结构，定义根节点，以及定义做孩子以及右孩子*/
/* 这个是输入一个先序以及一个中序，来完成对二叉树的建立*/
struct node *creat(char *pre,char *ord,int n)
{ /*pre为一个数组名包涵着先序，ord为一个数组名，是一个中序，而n为这个
二叉树的节点的数目*/
struct node *head;/* 定义这个根节点，*/
int ordsit;/* 为这个中序遍历的，数组下标*/
head=0;
if(n<=0)
return 0;
else
{
head=(struct node *)malloc(sizeof(struct node));
head->data=*pre;/* 因为这个pre是一个先序数组，所以，这个数组的首地址为这个要建立的数的跟指针*/
head->lchild=0;
head->rchild=0;/*对这个已获得的根节点的左右孩子复初值为NULL*/
ordsit=0;/* ord,中序的下标赋零*/
while(ord[ordsit]!=*pre)/*这个过程实质是在中序遍历中寻找，根节点的位置*/
{ ordsit++;
}
head->lchild=creat(pre+1,ord,ordsit); /* pre +1 是在获得先序中左子树的根节点的位置，而这个中序中左子树的位置不变*/
head->rchild=creat(pre+ordsit+1,ord+ordsit+1,n-ordsit-1);/* 在中序中这个柚子树的位置为，在先序中右子树的位置是*/
/* 其实就是是这个的左子树，以及柚子树都指向要递归的*/
return head;
}
}
/* 中序递归遍历*/
void inorder1(struct node *r)
{
if(!r)
return ;
else
{ inorder1(r->lchild); /* 进行递归遍历*/
printf("%c",r->data);
inorder1(r->rchild);
}http://hi.baidu.com/%C1%F5%BB%C0%CD%A51989/blog/item/9e38cd3932a99028b8998fbc.html
}
void inorder(struct node *head)/* 进行中序遍历*/
{
struct node *p;
struct node *stack[20];/* 设置一个站*/
int top=0;
p=head;
while(p||top!=0)
{
while(p)
{ stack[top++]=p;/* 沿着左子树进行遍历，遇到左子树就进栈保存*/
p=p->lchild;
}
p=stack[--top];/*出战来进行计算*/
printf("%c",p->data);
p=p->rchild;/* 注意这个p与上面的p!=NULL.密切联系*/
}
}
int main()
{ struct node *head;
char pre[20],ord[20];
int n;
gets(pre);
gets(ord);
n=strlen(pre);
head=creat(pre,ord,n);
inorder1(head);/* 都是中序遍历，但是一种是递归一种不是，*/
printf("\n");
inorder(head);
getch();
}
验证，，，
输入/*测试事例
-+a*b%cd/ef
a+b*c%d-e/f
*/
在这里，用到了栈的概念，其实关于递归调用，其实都是用栈来实现的 ，恩，
栈不是一种程序，而是一中算法，恩，就是啊，它是一种思想很是丰富的 算法，
尤其是在应用的时候，很是，光
我看了一个原始的二叉树的建立，其实，他们更是用到了，栈，的，梯队，
而且，还是自动分配空间的，就是说，
栈，咋就是栈里面的参数可以有多个，有不同的形式，可以使结构体的，形式‘、’
