




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、二叉树结点typedef struct BiTNode数据char data;左右孩子指针struct BiTNode *lchild,*rchild;BiTNode,*BiTree;按先序序列创建二叉树int CreateBiTree(BiTree & T)char data;,表示空树按先序次序输入二叉树中结点的值(一个字符), scanf(%c,&data);,表示空树if(data = #)T = NULL; elseT = (BiTree)malloc(sizeof(BiTNode);生成根结点T-data = data;构造左子树CreateBiTree(T-lchild);构造右
2、子树CreateBiTree(T-rchild);return 0;void Visit(BiTree T) if(T-data != #)printf(%c ,T-data);先序遍历void PreOrder(BiTree T)if(T != NULL)访问根节点Visit(T);访问左子结点PreOrder(T-lchild);访问右子结点PreOrder(T-rchild);中序遍历void InOrder(BiTree T)if(T != NULL)访问左子结点InOrder(T-lchild);访问根节点Visit(T);访问右子结点InOrder(T-rchild);后序遍历vo
3、id PostOrder(BiTree T)if(T != NULL)访问左子结点PostOrder(T-lchild);访问右子结点PostOrder(T-rchild);访问根节点Visit(T);/*先序遍历(非递归)思路:访问T-data后,将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T, 出栈,再先序遍历T的右子树。*/void PreOrder2(BiTree T) stackvBiTree stack;p是遍历指针BiTree p = T;栈不空或者p不空时循环while(p II !stack.empty()if(p != NULL)存入栈中stack.push(p)
4、;访问根节点printf(%c ,p-data);遍历左子树p = p-lchild;else退栈p = stack.top();stack.pop();访问右子树p = p-rchild;/whilev2中序遍历【思路】:T是要遍历树的根指针,中序遍历要求在遍历完左子树后,访问根,再遍历右子 树。先将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,访问 T-data,再中序遍历T的右子树。cpp view plaincopyvoid InOrder2(BiTree T)stack stack;/p是遍历指针BiTree p = T;栈不空或者p不空时循环while(p II !
5、stack.empty()if(p != NULL)存入栈中stack.push(p);遍历左子树p = p-lchild;else退栈,访问根节点p = stack.top();printf(%c ,p-data);stack.pop();访问右子树p = p-rchild;/while后序遍历【思路】:T是要遍历树的根指针,后序遍历要求在遍历完左右子树后,再访问根。需要判 断根结点的左右子树是否均遍历过。cpp view plaincopy后序遍历(非递归)typedef struct BiTNodePostBiTree biTree;char tag;BiTNodePost,*BiTre
6、ePost;void PostOrder2(BiTree T)stackvBiTreePost stack;/p是遍历指针BiTree p = T;BiTreePost BT;栈不空或者p不空时循环while(p != NULL II !stack.empty()遍历左子树while(p != NULL)BT = (BiTreePost)malloc(sizeof(BiTNodePost);BT-biTree = p;访问过左子树BT-tag = L; stack.push(BT);p = p-lchild;左右子树访问完毕访问根节点while(!stack.empty() & (stack.
7、top()-tag = R)BT = stack.top();退栈stack.pop();BT-biTree;printf(%c ,BT-biTree-data);遍历右子树if(!stack.empty()BT = stack.top();访问过右子树BT-tag = R;p = BT-biTree; p = p-rchild;/while层次遍历【思路】:按从顶向下,从左至右的顺序来逐层访问每个节点,层次遍历的过程中需要用队 列。cpp view plaincopy层次遍历void LevelOrder(BiTree T)BiTree p = T;队列queuevBiTree queue;
8、根节点入队queue.push(p);队列不空循环while(!queue.empty()对头元素出队p = queue.front();访问p指向的结点printf(%c ,p-data);退出队列queue.pop();左子树不空,将左子树入队if(p-lchild != NULL) queue.push(p-lchild);右子树不空,将右子树入队if(p-rchild != NULL) queue.push(p-rchild);测试用例:输入:ABC#DE#G#F# 输出:代码:cpp view plaincopy #includeviostream #includevstack #i
9、ncludevqueue using namespace std;二叉树结点typedef struct BiTNode数据char data;左右孩子指针struct BiTNode *lchild,*rchild;BiTNode,*BiTree;按先序序列创建二叉树int CreateBiTree(BiTree & T)char data;,表示空树按先序次序输入二叉树中结点的值(一个字符), scanf(%c,&data);,表示空树if(data = #)T = NULL; elseT = (BiTree)malloc(sizeof(BiTNode);生成根结点T-data = dat
10、a;构造左子树CreateBiTree(T-lchild);构造右子树CreateBiTree(T-rchild);return 0;输出void Visit(BiTree T) if(T-data != #)printf(%c ,T-data);先序遍历void PreOrder(BiTree T)if(T != NULL)访问根节点Visit(T);访问左子结点PreOrder(T-lchild);访问右子结点PreOrder(T-rchild);中序遍历void InOrder(BiTree T)if(T != NULL)访问左子结点InOrder(T-lchild);访问根节点Visi
11、t(T);访问右子结点InOrder(T-rchild);后序遍历void PostOrder(BiTree T)if(T != NULL)访问左子结点PostOrder(T-lchild);访问右子结点PostOrder(T-rchild);访问根节点Visit(T);/*先序遍历(非递归)思路:访问T-data后,将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T, 出栈,再先序遍历T的右子树。*/void PreOrder2(BiTree T)stackvBiTree stack;p是遍历指针BiTree p = T;栈不空或者p不空时循环while(p II !stack.emp
12、ty()if(p != NULL)存入栈中stack.push(p);访问根节点printf(%c ,p-data);遍历左子树p = p-lchild;else退栈p = stack.top(); stack.pop();访问右子树p = p-rchild;/while/*中序遍历(非递归)思路:T是要遍历树的根指针,中序遍历要求在遍历完左子树后,访问根,再遍历右子 树。先将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,访问 T-data,再中序遍历T的右子树。*/void InOrder2(BiTree T)stackvBiTree stack;/p是遍历指针BiTree
13、p = T;栈不空或者p不空时循环while(p II !stack.empty()if(p != NULL)存入栈中stack.push(p);遍历左子树p = p-lchild;else退栈,访问根节点p = stack.top();printf(%c ,p-data);stack.pop();访问右子树p = p-rchild;/while后序遍历(非递归)typedef struct BiTNodePostBiTree biTree;char tag;BiTNodePost,*BiTreePost;void PostOrder2(BiTree T)stackvBiTreePost st
14、ack;/p是遍历指针BiTree p = T;BiTreePost BT;栈不空或者p不空时循环while(p != NULL II !stack.empty()遍历左子树while(p != NULL)BT = (BiTreePost)malloc(sizeof(BiTNodePost);BT-biTree = p;访问过左子树BT-tag = L;stack.push(BT);p = p-lchild;左右子树访问完毕访问根节点 while(!stack.empty() & (stack.top()-tag = R) BT = stack.top();退栈stack.pop();BT-b
15、iTree;printf(%c ,BT-biTree-data);遍历右子树if(!stack.empty()BT = stack.top();访问过右子树BT-tag = R;p = BT-biTree;p = p-rchild;/while层次遍历void LevelOrder(BiTree T)BiTree p = T;队列queuevBiTree queue;根节点入队queue.push(p);队列不空循环while(!queue.empty()对头元素出队p = queue.front();访问p指向的结点printf(%c ,p-data);退出队列queue.pop();左子树不空,将左子树入队 if(p-lchild != NULL) queue.push(p-lchild);右子树不空,将右子树入队 if(p-rchild != NULL) queue.push(p-rchild);int main()BiTree T;CreateBiTree(T); printf(先序遍历:n); PreOrder(T);printf(n);printf(”先序
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 比亚迪交付活动方案
- 汽车疫情活动方案
- 水果销售活动方案
- 民警三八活动方案
- 汶上管理咨询活动方案
- 武汉近期讲座活动方案
- 森林演练活动方案
- 桐庐教研活动方案
- 桥头镇会议策划活动方案
- 汽修店铺活动方案
- 2025年 中国南水北调集团新能源投资公司第一批中层及考试笔试试卷附答案
- 叙事护理学智慧树知到答案2024年中国人民解放军海军军医大学
- 火龙罐综合灸技术课件
- 大海(张雨生)原版五线谱钢琴谱正谱乐谱
- 有限空间作业实操评分标准
- 规划展览馆方案-南京军区军史馆布展总体方案
- (完整版)煤矿主扇司机考试卷(含答案)
- 双柏县工业用大麻开发种植实施计划方案
- 租赁房屋交接清单
- 吊顶检验报告(共5页)
- (完整版)10KV电力线路施工组织设计方案
评论
0/150
提交评论