2022年二叉树c语言的程序代码 .pdf

《2022年二叉树c语言的程序代码 .pdf》由会员分享，可在线阅读，更多相关《2022年二叉树c语言的程序代码 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、# include stdio.h # include stdlib.h # include malloc.h typedef struct Node char data; / 定义根结点struct Node *lchild; / 定义左子树struct Node *rchild; / 定义右子树Node,*BiTree; int JianShu(BiTree &T) / 构造二叉链表表示的二叉树T, 按先序遍历输入二/ 叉树中结点的值(一个字符 ),空格字符表示空树. char e; T=(Node *)malloc(sizeof(Node); / 开辟一个以sizeof(Node)为单位

2、的空间if(!T) / 开辟失败exit (-2); fflush(stdin); / 清空缓存scanf (%c,&e); if(e= ) T=NULL; else T-data=e; / 生成根结点printf ( 请输入 %c 的左孩子 :,e); JianShu(T-lchild); / 构造左子树printf ( 请输入 %c 的右孩子 :,e); JianShu(T-rchild); / 构造右子树 return 1; int DLR_P(BiTree &T) / 先序遍历打印二叉树中所有数据if (T!=NULL) / 非空二叉树printf (%c ,T-data); / 访问

3、 T DLR_P(T-lchild); / 递归遍历左子树DLR_P(T-rchild); / 递归遍历右子树 return 1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - int LDR_P(BiTree &T) / 中序遍历打印二叉树中所有数据if (T!=NULL) / 非空二叉树LDR_P(T-lchild); / 递归遍历左子树printf (%c ,T-data); / 访问 T LDR_P(T-rchild)

4、; / 递归遍历右子树 return 1; int LRD_P(BiTree &T) / 后序遍历打印二叉树中所有数据if (T!=NULL) / 非空二叉树LRD_P(T-lchild); / 递归遍历左子树LRD_P(T-rchild); / 递归遍历右子树printf (%c ,T-data); / 访问 T return 1; int DLR_0(BiTree &T,int &s_0) / 用先序遍历求二叉树T 中所有叶子总数if (T!=NULL) / 非空二叉树if(!T-lchild&!T-rchild) / 判断该结点是否为叶子s_0+; / 是叶子则计数并打印printf (

5、%c ,T-data); DLR_0(T-lchild,s_0); / 递归遍历左子树,直到叶子处DLR_0(T-rchild,s_0); / 递归遍历右子树,直到叶子处 return s_0; int DLR_1(BiTree &T,int &s_1) / 用先序遍历求二叉树T 中所有 1 度结点总数if (T!=NULL) / 非空二叉树if(T-lchild&!T-rchild) / 判断该结点是否为1 度结点s_1+; / 是 1 度结点则计数并打印printf (%c ,T-data); if(!T-lchild&T-rchild) / 判断该结点是否为1 度结点名师资料总结 - -

6、 -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - s_1+; / 是 1 度结点则计数并打印printf (%c ,T-data); DLR_1(T-lchild,s_1); / 递归遍历左子树,直到 1 度结点处DLR_1(T-rchild,s_1); / 递归遍历右子树,直到 1 度结点处 return s_1; int DLR_2(BiTree &T,int &s_2) / 用先序遍历求二叉树T 中所有 2 度结点总数if (T!=NULL)

7、/ 非空二叉树if(T-lchild&T-rchild) / 判断该结点是否为2 度结点s_2+; / 是 2 度结点则计数并打印printf (%c ,T-data); DLR_2(T-lchild,s_2); / 递归遍历左子树,直到 2 度结点处DLR_2(T-rchild,s_2); / 递归遍历右子树,直到 2 度结点处 return s_2; int ShenDu(BiTree &T,int l,int &h) / 用递归求二叉树的深度if (T!=NULL) / 非空二叉树l=l+1; if (lh) h=l; ShenDu(T-lchild,l,h); / 递归遍历左子树She

8、nDu(T-rchild,l,h); / 递归遍历右子树 return 1; int QingKong(BiTree &T) / 清空二叉树if (T!=NULL) QingKong(T-lchild); / 遍历清空左子树free(T-lchild); QingKong(T-rchild); / 遍历清空右子树free(T-rchild); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - return 1; int main

9、() / 主函数int i,a=0; Node *T; / 定义一个二叉树T while(1) system(cls); printf (t|=|tn); printf (t| |tn); printf (t| 二 叉 树 的 链 式 存 储|tn); printf (t| |tn); printf (t|=|tn); printf (nt【1】 建立二叉树及先序输入!t 【2】 遍历二叉树打印!n); printf (nt【3】 打印各结点并统计! t 【4】 求二叉树的深度!n); printf (nt【5】 清空二叉树 !tt 【0】 退出程序 !n); system(color F0)

10、; printf (nnttt请输入你的选择:); / 输入选择的功能序号scanf (%d,&i); switch(i) case 1: / 建立二叉树T 并输入数据printf ( 请输入二叉树T 的根 :); JianShu(T); a=1; system(pause); break; case 2: / 遍历打印二叉树中所有数据if(a=1) if(T!=NULL) / 非空二叉树T printf ( 先序遍历打印结果:); / 执行先序遍历并打印DLR_P(T); printf (nn中序遍历打印结果:); / 执行中序遍历并打印LDR_P(T); printf (nn后序遍历打印结

11、果:); / 执行后序遍历并打印LRD_P(T); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - printf (n); else printf ( 二叉树 T 为空树 !n); else / 未建立二叉树printf ( 未建立二叉树!n); system(pause); break; case 3: / 先序遍历打印二叉树中 0 度 1 度 2 度结点if(a=1) if(T!=NULL) / 非空二叉树T int s_0

12、=0,s_1=0,s_2=0; printf ( 二叉树中叶子:); DLR_0(T,s_0); / 执行先序遍历打印叶子并统计printf ( 共有 %d 个叶子 !n,s_0); printf (n二叉树中1 度结点 :); DLR_1(T,s_1); / 执行先序遍历打印1 度结点并统计printf ( 共有 %d 个 1 度结点 !n,s_1); printf (n二叉树中2 度结点 :); DLR_2(T,s_2); / 执行先序遍历打印2 度结点并统计printf ( 共有 %d 个 2 度结点 !n,s_2); else printf ( 二叉树 T 为空树 !n); else

13、/ 未建立二叉树printf ( 未建立二叉树!n); system(pause); break; case 4: / 用递归求二叉树的深度if(a=1) if(T!=NULL) / 非空二叉树T int l=0,h=0; ShenDu(T,l,h); printf ( 二叉树的深度为%d.n,h); else printf ( 二叉树 T 为空树 !n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - else / 未建立二

14、叉树printf ( 未建立二叉树!n); system(pause); break; case 5: / 清空二叉树if(a=1) if(T!=NULL) / 非空二叉树QingKong(T); / 清空二叉树T=NULL; printf ( 二叉树已清空!n); else printf ( 二叉树 T 为空树 ,既不用清空 !n); else / 未建立二叉树printf ( 未建立二叉树,既不用清空 !n); system(pause); break; case 0: / 退出程序printf ( 退出程序 !n); return 1; default: / 重新输入选择的功能序号printf ( 输入有误 ,请重新输入 !n); system(pause); break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -