/*二叉树的各种操作复习*/
#include <stdio.h>
#define BACK_ODER -1
#define IN_ODER 0
#define PRE_ODER 1
#define LEVEL_ODER 2//层次化遍历
typedef struct _Node{
char data;
struct _Node *lchild;
struct _Node *rchild;
} Node,*Tree;
/* 生成二叉树的普通方法
* 按先序次序输入二叉树中结点的值
* 构造二叉链表表示的二叉树T。输入空格表示空子树。 */
Node * CreateTree()
{
char ch;
scanf("%c",&ch);
Node *T;
if(ch==' ') /* 空 */
return NULL;
else
{
T=(Node *)malloc(sizeof(Node));
if(!T)
exit(0);
T->data=ch; /* 生成根结点 */
T->lchild = CreateTree(); /* 构造左子树 */
T->rchild = CreateTree(); /* 构造右子树 */
}
return T;
}
/* 由先根序列和中根序列生成二叉树
* 递归法。pre 是先跟序列,in是中根序列
* pre_s是先根序列的起始,pre_e是先跟序列的结束
* in_s是中根序列的起始,in_e是中根序列的结束
*/
Node *Convert(char pre[], int pre_s, int pre_e,
char in [], int in_s , int in_e )
{
if(in_s > in_e)return NULL;
int i = in_s;
for(i=in_s;i<in_e&&in[i]!=pre[pre_s];i++);
Node *p = (Node *)malloc(sizeof(Node));
p->data = pre[pre_s];
p->lchild = Convert(pre, pre_s+1, pre_s+i-in_s,
in, in_s,i-1);
p->rchild = Convert(pre, pre_s+i-in_s+1,pre_e,
in, i+1,in_e);
return p;
}
/*求二叉树的度*/
int GetDegree(const Tree head)
{
int degree = 0;
int m,n;
if(!head)return 0;
if(head->lchild && head->rchild) return 2;
else if(!head->lchild && !head->rchild) return 0;
else {
m = GetDegree(head->lchild) ;
n = GetDegree(head->rchild) ;
if(2==m || 2==n)return 2;
else return 1;
}
return degree;
}
/*求二叉树的高度*/
int GetHight(const Tree head)
{
int m,n;
if(!head)return 0;
m = GetHight(head->lchild);
n = GetHight(head->rchild);
return 1 + (m > n ? m : n);
}
/* 输出二叉树中某个指定元素的祖父节点(包括自己)
* 递归思想:如果此节点在其子树中,那么它是祖父节点
* 返回值 :1表示子树中有 ,0表示无*/
int GetGrandPa(const Tree head, const char e)
{
if(!head)return 0;
if(GetGrandPa(head->lchild,e) || GetGrandPa(head->rchild,e) || e==head->data)//子树中有此节点
{
printf("%c",head->data);
return 1;
}
else return 0;
}
/*遍历二叉树,参数oder控制遍历方式*/
void Tranverse(Node *head,int oder)
{
if(!head)return ;
if(LEVEL_ODER == oder)
{
LevTranverse(&head,1);
return;
}
if(PRE_ODER == oder) printf("%c\t",head->data);
Tranverse(head->lchild,oder);
if(IN_ODER == oder) printf("%c\t",head->data);
Tranverse(head->rchild,oder);
if(BACK_ODER == oder) printf("%c\t",head->data);
return;
}
/* 层次化遍历,采用递归思想而不用队列。
* 递归思想:把当前层遍历的同时把下一层存储好
* nodes[]存储的当前层的节点,count表示当前层的元素个数*/
void LevTranverse(const Node* nodes[], int count)
{
int i=0, j=0;
if(0 == count) return;
Node *nextNodes[100] = {0};
for(i = 0,j=0; i<count; i++)
{
printf("%c\t",nodes[i]->data);
if(nodes[i]->lchild)nextNodes[j++] = nodes[i]->lchild;
if(nodes[i]->rchild)nextNodes[j++] = nodes[i]->rchild;
}
LevTranverse(nextNodes,j);
return;
}
int main(int argc, char *argv[])
{
char pre[]= "abcde";
char in[] = "bcade";
Node *head = NULL;
head = Convert(pre,0,strlen(pre)-1,
in ,0,strlen(in)-1);
printf("Hight : %d\n",GetHight(head));
printf("Degree : %d\n",GetDegree(head));
if(!GetGrandPa(head,'c'))printf("No grandpa !");printf("\n");
Tranverse(head,LEVEL_ODER);printf("\n");
system("PAUSE");
}
分享到:
相关推荐
这些程序都是本人在复习数据结构中自己写的,都是可以运行的,对学习数据结构绝对有好处
使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法,以及它们在程序中的使用方法。 使学生掌握软件设计的基本内容和设计方法,并培养学生进行规范化软件设计的能力。 3) 使...
(一)线性表的定义和基本操作 (二)线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 二、栈、队列和数组 (一)栈和队列的基本概念 (二)栈和队列的顺序存储结构 (三)栈和队列的链式存储结构 (四...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
2.复习顺序表及二叉树的基本操作过程。 3.编写完整程序完成下面的实验内容并上机运行。 4.整理并上交实验报告。 三、实验内容 1.二分查找又称为折半查找,它要求要查找的顺序表必须是有序表,即表中结点按关键字...
本资源为关于c++noip初赛(现为csp-j)的全面复习doc文档。 选择题、阅读程序写结果、代码填空。 知识点包括基础知识: 一、选择题 1.计算机技术(硬件) 2.二进制、八进制、十进制、十六进制转换及二进制编码(进制...
数据结构与算法复习题 1. 写出以下各词语对应的中文(英) sequential storge structure 顺序存储结构 Abstract Data Type (ADT) 抽象数据类型 二叉排序树 Binary sort tree queue 队列 storge structure 存储结构 ...
数据结构与算法课程内容包括数据结构与抽象数据类型、算法特性及分类、...二叉树的抽象数据类型、二叉树的搜索、二叉树的存储结构、树与二叉树的等价转换、树的抽象数据类型及树的遍历、树的链式存储结构、树的父指针...
复习、调试C程序 2 线性表基本操作1 4 线性表基本操作2 6 栈和队列基本操作1 8 栈和队列基本操作2 10 稀疏矩阵的运算 12 二叉树基本操作 14 图的存储和应用 16 查找运算实现 17 排序运算的实现 19
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
很适合初学者 ,可做复习、面试的资料。 1.C++树的生成与遍历 2.遍历二叉树 3.插入排序,快速排序 4.查找 5.抽象数据类型的表示与实现 6.串操作应用举例 7.串的表示和实现 8.串的定义 9.串的实现实验 10.动态查找表 ...
数据结构讲义(严蔚敏版)(含算法源码) 第0章 复习提示 1 一、 教材内容 1 二、 复习提示 1 1. 经典算法 1 2. 绪论 1 3. 线性表 1 4. 栈和队列 2 5. 串 2 6. 树和二叉树 2 ...11. 各种排序方法比较 73
基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和空间复杂度。 算法: 算法设计:研究如何将解决问题的步骤形式化为一系列指令,...
本人博客里配的代码,包含排序、二叉树、数组、链表等一些基础操作。
│ 操作系统复习建议.html │ 数据结构复习建议.html │ 数据结构复习重点归纳.doc │ 考研资料下载汇总.html │ 计算机应用技术方向大学排名.html │ 计算机系统结构方向大学排名.html │ 计算机考研专业课视频汇总...
│ 操作系统复习建议.html │ 数据结构复习建议.html │ 数据结构复习重点归纳.doc │ 考研资料下载汇总.html │ 计算机应用技术方向大学排名.html │ 计算机系统结构方向大学排名.html │ 计算机考研专业课...
这套导图深度契合统考大纲,对操作系统、计算机组成原理、计算机网络与数据结构四大板块的知识进行了系统性归纳与精炼概括,旨在引领您轻松穿越知识丛林,精准把握各科核心。 第一,全景展示:思维导图以直观的视觉...
第6章 树与森林 一、复习要点 本章主要介绍了树与森林、二叉树的定义、性质、操作和相关算法的实现。特别是二叉树的遍历算法,它们与许多以此为基础的递归算法都必
4-12 单向循环链表删除元素复习及链表扩展 4-13 双向链表及添加元素 4-14 双向链表删除元素 五、排序与搜索 5-01 排序算法的稳定性 5-02 冒泡排序及实现 5-03 选择排序算法及实现 5-04 插入算法 5-05 插入...
1、已知一个链表中存储了若干名学生的信息,每名学生的信息包括:学号、英语成绩、数学成绩、计算机成绩。 现编写一个函数search(),要求对输入的无序学号进行排序,然后采用折半...(复习c语言结构体和链表知识)