数据结构——二叉树遍历、深度、叶子节点数计算

比眉伴天荒 2022-08-03 00:24 126阅读 0赞

效果如下：

其中“\#”代表空节点

![Center][]

/\*数据结构——二叉树\*/

\#define StACK\_INIt\_SIZE 100 //存储空间初始分配量

\#define StACKNCREMENt 50 //存储空间分配增量  
\#include<stdio.h>  
\#include<stdlib.h>  
\#include<string.h>  
int n;  
typedef char telemtype;  
typedef struct bitnode  
\{  
telemtype data;  
struct bitnode \*lchild,\*rchild;  
\}binode,\*bitree;  
  
  
int createbitree(bitree &t);//创建二叉树  
void preordertraverse(bitree t);//先序遍历  
void inordertraverse(bitree t);//中序遍历  
void postordertraverse(bitree t);//后序遍历  
int depth(bitree t);//求二叉树深度  
int leaf(bitree t);//求二叉树叶子节点数  
int main()  
\{  
int j,M,x;  
bitree t;  
  
  
  
printf("请输入:\\n");  
createbitree(t) ;  
printf("先序遍历的结果是:");  
preordertraverse(t);  
printf("\\n");  
printf("中序遍历的结果是:");  
inordertraverse(t);  
printf("\\n");  
printf("后序遍历的结果是:");  
postordertraverse(t);  
printf("\\n");  
printf("叶子节点数是:");  
x=leaf(t);  
printf("%d\\n",x);  
M=depth(t);  
printf("二叉树的深度是:");printf("%d\\n",M);  
return 0;  
\}  
  
  
// 按先序次序输入二叉树中结点的值（一个字符），“\#”字符表示空树，  
// 构造二叉链表表示的二叉树T。  
int createbitree(bitree &t)  
\{  
char ch;  
scanf("%c",&ch);  
if(ch=='\#') t=NULL;  
else  
\{  
if(!(t=(bitnode\*)malloc(sizeof(bitnode)))) exit(0);  
t->data=ch;  
createbitree(t->lchild);  
createbitree(t->rchild);  
\}  
return 0;  
\}  
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);  
\}  
\}  
int leaf(bitree t)  
\{  
//int n=0;  
if(t)  
\{  
if(t->lchild==NULL&&t->rchild==NULL)  
n=n+1;  
leaf(t->lchild);  
leaf(t->rchild);  
  
\}  
return n;  
\}  
int depth(bitree t)  
\{  
int dep1,dep2;  
if(t==NULL)  
return 0;  
else  
\{  
dep1=depth(t->lchild);  
dep2=depth(t->rchild);  
if(dep1>=dep2)  
return (dep1+1);  
else  
return (dep2+1);  
\}  
\}

[Center]: /images/20220731/55df180d9461412ba22db6670029df42.png