2022年数据结构C语言实现系列[]树 .pdf

《2022年数据结构C语言实现系列[]树 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构C语言实现系列[]树 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构 C 语言实现系列8树 1#include#include#define kk 3 /*定义树的度*/#define MS 10 /*定义在建立树的存储结构时的栈空间大小*/#define MQ 10 /*定义在树的按层遍历算法中的队列空间大小*/typedef char elemType;/*/*以下是关于树操作的4 个简单算法 */*/struct GTreeNode elemType data;struct GTreeNode*tkk;struct GTreeNode*parent;/*建立树的存储结构*/void createGTree(struct GTreeNode*gt,

2、char*a)struct GTreeNode*sMS;/*数组 s 作为存储树中结点指针的栈使用*/int dMS;/*数组 d 作为存储孩子结点链接到双亲结点指针域的序号栈使用*/int top=-1;/*top 作为两个栈的栈顶指针，初值为-1 表示栈空*/struct GTreeNode*p;/*定义 p 为指向树结点的指针*/int i=0,j;/*i 指示扫描字符串a中的当前字符位置*/*gt=NULL;/*初始将树根指针置空*/while(ai!=o)/*每次循环处理一个字符，直到字符串结束为止*/switch(ai)/*对空格不作处理*/case :break;/*处理左括号时

3、，让p 指针进 s 栈，进d 栈，表明待扫描的孩子结点将被链接到s栈顶元素所指结点的第一个指针域*/case(:top+;stop=p;dtop=0;break;/*处理右括号时，让s和 d 退栈*/case):top-;break;/*处理逗号时，让待读入的孩子的结点链接到s 栈顶元素所指结点的下一个指针域*/名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -case,:dtop+;break;/*此处处理的必然是字符元素*/default:/*根据 ai 字符生成新结点*/p=malloc(sizeof(struct GTreeNode);p-data=ai;for(

4、j=0;j tj=NULL;if(NULL=*gt )*gt=p;/*使结点 p 成为树根*/else stop-tdtop=p;/*链接到双亲结点对应的指针域*/break;i+;/*准备处理下一个字符*/return;/*2.树的遍历*/*先根*/void preRoot(struct GTreeNode*gt)int i;if(gt!=NULL)printf(%c,gt-data);/*访问根结点*/for(i=0;i ti);/*递归遍历每一棵子树*/return;/*后根*/void postRoot(struct GTreeNode*gt)int i;if(gt!=NULL)for

5、(i=0;i ti);/*递归遍历每一棵子树*/printf(%c,gt-data);/*访问根结点*/*按层*/void levelOrder(struct GTreeNode*gt)struct GTreeNode*p;int i;struct GTreeNode*qMQ;/*队列用的数组q，存放根结点*/int front=0,rear=0;/*将整棵树的树根指针入队*/if(gt!=NULL)rear=(rear+1%MQ);qrear=gt;/*当队列非空时执行循环*/while(front!=rear)front=(front+1)%MQ;/*/*删除队首元素，输出队首元素所指结点

6、的值*/p=qfront;printf(%c,p-data);/*非空的孩子结点的指针依次进队*/for(i=0;i ti!=NULL)rear=(rear+1)%MQ;qrear=p-ti;return;/*3.从树中查找结点*/elemType*findGTree(struct GTreeNode*gt,elemType x)/*若树空则返回NULL*/if(gt=NULL)return NULL;else elemType*p;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 6 页 -int i;/*若查找成功返回结点值域的地址*/if(gt-data=x)return&(

7、gt-data);/*向每棵子树继续查找，返回得到的值域地址*/for(i=0;i ti,x)return p;return NULL;/*查找不成功返回NULL*/数据结构 C 语言实现系列8 树2/*树的输出*/void printGTree(struct GTreeNode*gt)if(gt!=NULL)int i;printf(%c,gt-data);/*判断 gt 结点是否有孩子*/for(i=0;i ti!=NULL)break;/*有孩子时才执行条件语句体的向下递归调用*/if(i t0);/*输出第一棵子树*/*输出其余各个子树*/for(i=1;i ti);printf();

8、return;/*5.求树的深度*/名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -int depthGTree(struct GTreeNode*gt)int i,max;/*空树的深度为0*/if(gt=NULL)return 0;/*求非空树的深度，max 的初值为 0*/max=0;for(i=0;i ti);/*计算出一棵子树的深度并赋值给d*/if(d max)max=d;return max+1;/*返回非空树的深度，它等于各子树的最大深度加1*/*6.清除树中的所有结点，使之成为一棵空树*/void clearGTree(struct GTreeNode

9、*gt)if(*gt!=NULL)int i;for(i=0;i ti);free(*gt);*gt=NULL;return;/*/int main(int argc,char*argv)char ch;struct GTreeNode*gt=NULL;char b50;/*用于存入k 叉树广义表的字符数组*/printf(输入一棵%d 叉树的广义表字符串：,kk);scanf(%s,b);createGTree(>,b);名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -printf(先根遍历：);preRoot(gt);printf();printf(后根遍历：);postRoot(gt);printf();printf(按层遍历：);levelOrder(gt);printf();printf(按广义表的形式输出：);printGTree(gt);printf();printf(树的深度为：%d,depthGTree(gt);printf(输入待查找的字符：);scanf(%c,&ch);if(findGTree(gt,ch)printf(查找成功！);else printf(查找失败！);clearGTree(>);return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 6 页 -