| C语言 | 您所在的位置：网站首页 › c语言的与操作 › C语言 |
C语言
|
程序需求
1.内容包括二叉链表的结构描述。 2.二叉树的建立。 3.二叉树的先序、中序与后序遍历算法。 先序遍历：先访问根节点,再先序遍历左子树,最后先序遍历右子树 中序遍历：先中序遍历左子树,再访问根节点,最后中序遍历右子树 后序遍历：先后序遍历左子树,再后序遍历右子树,最后访问根节点 4.建立二叉树,并通过调用函数。 5.输出先序遍历、中序遍历与后序遍历的结果。 算法的基本思想 根据题目要求，采用二叉链表来存储二叉树结构，二叉树是非线性数据集结构，通过遍历可以把二叉树中的结点访问一次且一次，从而得到顺序序列。 先序遍历： 1.先访问根节点 2.再先序遍历左子树 3.最后先序遍历右子树 中序遍历： 1.先中序遍历左子树 2.再访问根节点 3.最后中序遍历右子树 后序遍历： 1.先后序遍历左子树 2.再后序遍历右子树 3.最后访问根节点 程序的流程 程序由三个模块组成： 1.输入模块：输入二叉树的扩展，就要先进行二叉树的扩展，也就是将二叉树每个结点的空指针引出一个虚结点，其值为一个特定值，比如“”。用“”来表示空子树，处理后的二叉树称为原二叉树的扩展二叉树。 2.计算模块：设计先序PreOrder，中序InOrder，后序PostOrder遍历函数，进行函数调用二叉树结点排序。 3.输出模块：输出三种遍历结果。 二叉树遍历 #include #include typedef struct Node//定义二叉树链表结点结构 { char data; struct Node * LChild; struct Node * RChild; }BiTNode,* BiTree; BiTree creat(BiTree root)//创建二叉树 { char x; x = getchar(); if(x == '*') root = NULL; else { root = (BiTNode*)malloc(sizeof(BiTNode)); root->data = x; root->LChild = creat(root->LChild); root->RChild = creat(root->RChild); } return root; } void PreOrder (BiTree root)//先序遍历二叉树 {if(root!=NULL) { printf(" %c ",root->data); PreOrder (root->LChild); PreOrder (root->RChild); } } void InOrder (BiTree root)//中序遍历二叉树 { if(root!=NULL) { InOrder(root->LChild); printf(" %c ",root->data); InOrder(root->RChild); } } void PostOrder(BiTree root)//后序遍历二叉树 { if(root!=NULL) { PostOrder(root->LChild); PostOrder(root->RChild); printf(" %c ",root->data); } } void main() { BiTree t=NULL; printf("请输入二叉树的数据(输入格式为扩展二叉树序列,空子树输入*):\n"); t = creat(t); printf("先序遍历:\n"); PreOrder(t); printf("\n"); printf("中序遍历:\n"); InOrder(t); printf("\n"); printf("后序遍历:\n"); PostOrder(t); printf("\n"); }输入和输出的格式 输入：输入的遍历序列是一种“扩展的遍历序列”，在扩展的遍历序列中，必须用特定的元素来表示空子树。输入扩展二叉树序列，空子树用“*”表示 输入如下二叉树： |
输出：分别输出先序，中序，后序遍历的排序结果 先序遍历：A B D F G C E H 中序遍历：B F D G A C E H 后序遍历：F G D B H E C A 
【本文地址】
公司简介
联系我们