看东西容易,写东西确实就复杂多了呀,花了两天时间把二叉树的数据结构及一些相关基本算法的原理认真研究了下,并写出了相应的代码,包括二叉树的前序创建、前中后序遍历、层序遍历、删除、通过前序和中序序列构造二叉树等等
#include <stdio.h>
//定义数据元素类型
typedef int Element;
//定义二叉树节点
typedef struct bitree
{
Element data;
struct bitree *left, *right;
} Bitree;
//定义队列节点,层序遍历
typedef struct queueNode
{
Bitree * data;
struct queueNode *next;
} QueueNode;
typedef struct queue
{
QueueNode *front, *rear;
} Queue;
//创建队列
void createQueue(Queue **Q)
{
*Q = (Queue *) malloc(sizeof(Queue));
if(!*Q)
exit("Memory error...\n");
(*Q)->front = (*Q)->rear = NULL;
}
//入队操作
void EnQueue(Queue *Q, Bitree *data)
{
QueueNode * qn = (QueueNode*) malloc(sizeof(QueueNode));
if(!qn)
exit("Memory error...\n");
qn->data = data;
qn->next = NULL;
if(IsQueueEmpty(Q))
Q->front = Q->rear = qn;
else
{
Q->rear->next = qn;
Q->rear = qn;
}
}
//出队操作
void DeQueue(Queue *Q, Bitree **T)
{
if(!IsQueueEmpty(Q))
{
QueueNode *qn = Q->front;
(*T) = qn->data;
Q->front = qn->next;
free(qn);
qn = NULL;
}
}
//判断队列是否为空
int IsQueueEmpty(Queue *Q)
{
if(!Q->front)
return 1;
return 0;
}
//二叉树的创建
void createBitree(Bitree **T)
{
Element data;
scanf("%d", &data);
if(data != 0)
{
(*T) = (Bitree*)malloc(sizeof(Bitree));
if(!*T)
exit("Memory error...\n");
(*T)->data = data;
(*T)->left = (*T)->right = NULL;
createBitree(&(*T)->left);
createBitree(&(*T)->right);
}
}
//根据前序和中序遍历结果生成二叉树(总是假设给定的序列是有效的,这里不进行错误检测)
//@param p 递归前序子序列的起始位置
//@param m 递归中序子序列的起始位置
//@param length 递归子序列的长度
void creByPreMid(Bitree **T, int p, int m, int length, int *pre, int *mid)
{
int i=0;
for(;(i<length)&&(pre[p]!=mid[m+i]);i++);
(*T) = (Bitree *) malloc(sizeof(Bitree));
if(!*T)
exit("Memory error...\n");
(*T)->data = pre[p];
(*T)->left = (*T)->right = NULL;
//若有左子树则创建左子树
if(i>0)
{
creByPreMid(&(*T)->left, p+1, m, i, pre, mid);
}
//若有右子树则创建右子树
if(i<length-1)
{
creByPreMid(&(*T)->right, p+1+i, m+i+1, length-i-1, pre, mid);
}
}
//删除树
void delBitree(Bitree **T)
{
if(*T)
{
delBitree(&(*T)->left);
delBitree(&(*T)->right);
free(*T);
*T = NULL;
}
}
//二叉树的前序遍历
void preOrder(Bitree *T)
{
if(T)
{
printf("%d ", T->data);
preOrder(T->left);
preOrder(T->right);
}
}
//二叉树的中序遍历
void midOrder(Bitree *T)
{
if(T)
{
midOrder(T->left);
printf("%d ", T->data);
midOrder(T->right);
}
}
//二叉树的后序遍历
void afterOrder(Bitree *T)
{
if(T)
{
afterOrder(T->left);
afterOrder(T->right);
printf("%d ", T->data);
}
}
//二叉树的层序遍历
//思路:利用队列,如果树不为空,将根节点入队
// 然后循环队头元素出队,并作一下处理:判断出队的节点是否有左孩子,有则将左孩子入队,判断出队的节点是否有右孩子,有则将又孩子入队。
// 重复以上过程直到队列为空
void layOrder(Bitree *T)
{
Queue *Q = NULL;
createQueue(&Q);
if(!T)
return;
EnQueue(Q, T);
while(!IsQueueEmpty(Q))
{
DeQueue(Q, &T);
if(T->left)
EnQueue(Q, T->left);
if(T->right)
EnQueue(Q, T->right);
printf("%d ", T->data);
}
//释放队列空间
if(IsQueueEmpty(Q))
{
free(Q);
Q = NULL;
}
}
int main()
{
Bitree *T = NULL;
createBitree(&T);
printf("The preOrder result is: ");
preOrder(T);
printf("\n\n");
printf("The midOrder result is: ");
midOrder(T);
printf("\n\n");
printf("The afterOrder result is: ");
afterOrder(T);
printf("\n\n");
printf("The layOrder result is: ");
layOrder(T);
printf("\n\n");
delBitree(&T);
printf("After delete the tree, the preOrder result is: ");
preOrder(T);
printf("\n\n");
//假定前序和中序序列如下
int pre[6] = {5, 6, 7, 1, 2, 3};
int mid[6] = {7, 1, 6, 2, 5, 3};
creByPreMid(&T, 0, 0, 6, pre, mid);
printf("After creByPreMid, the preOrder result is: ");
preOrder(T);
printf("\n\n");
return 0;
}
分享到:
相关推荐
运用二叉链表实现二叉树的基本操作,包括:创建二叉树的存储结构、复制已有的二叉树、计算已有的二叉树的深度、先根序序列、中根序序列、后根序序列等。 输入格式:AB#C##D## 二、实验目的 掌握二叉链表及二叉树的...
二叉树的基本操作的各种操作 先序 中序 后序 遍历二叉树 还有二叉树的节点数的求法
二叉树的基本操作,使用递归算法,先序遍历建造二叉树。
二叉树的基本操作java代码
南邮数据结构实验使用C++描述,二叉树的基本操作
设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1. 按先序次序建立一个二叉树 ,用#表示某结点的左右子树是否为空,用于表示该结点是否...
二叉树的先序遍历,判断二叉树是否为空,深度的计算,结点多少的计算
一.需求分析 实现平衡二叉树的基本操作,插入,删除,修改,等功能!
C++二叉树基本操作
递归二叉树的基本操作,递归创建,递归先序遍历、中序遍历、后序遍历,求树的高度,求叶子结点的个数,交换树的左右孩子
目的:1、掌握二叉链表上实现二叉树基本操作。 2、学会设计基于遍历的求解二叉树应用问题的递归算法。 3、理解哈夫曼树的构造算法,学习设计哈夫曼编码和译码系统 要求:能成功演示二叉树的有关算法,运算完毕后能...
熟悉二叉树结点的结构和对二叉树的基本操作。掌握对二叉树每一种操作的具体实现。学会利用递归方法和非递归方法编写对二叉树这种递归数据结构进行处理的算法。
数据结构中对二叉树的基本操作 包括创建二叉树 遍历二叉树 求二叉树的深度 求叶子树
问题描述:采用二叉链表作为存储结构,完成图1的二叉树的建立和遍历操作。 基本要求: (1)基于先序遍历的构造算法。输入是二叉树的先序序列,但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符...
设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1 按先序次序建立一个二叉树 2按(A:先序 B:中序 C:后序 )遍历输出二叉树的所有结点
1、根据输入的数据建立一个二叉树; 2、分别采用前序、中序、后序的遍历方式显示输出二叉树的遍历结果 3、采用非递归的编程方法,分别统计二叉树的节点个数、度为1、度为2和叶子节点的个数,以及数据值的最大值和...