课程设计——非递归实现二叉树的三种遍历算法及创建排序二叉树
2019-05-26 本文已影响0人
LetUsGoOn
本次课程设计主要含三部分内容，并且每一部分内容独立为一个小的课程设计
1.二叉树的建立及其非递归的先序、中序、后序遍历；
2.二叉树的层序遍历
3.排序二叉树的创建及中序遍历输出
- 首先我们来实现第一小部分的内容，先序递归构建二叉树并按非递归的方法对其进行先序、中序和后序遍历。
接下来我们用下面这颗二叉树作为我们示例进行演示，我们示例二叉树长这样：
图1 示例二叉树
在前序遍历生成二叉树中，我们用‘#’表示结点为NULL，因此前序遍历生成二叉树时的输入序列应该为："abd#h##k##cef##g##m##"。通过CreateTree()函数我们就建立起了一颗如上图所示的二叉树，然后就可以愉快的开始各种遍历测试了，具体代码如下：
#include<stdio.h>
#include<stdlib.h>
typedef struct treeNode{
char data;
struct treeNode*rchild, *lchild;
}TreeNode;
char str[] = "abd#h##k##cef##g##m##";
int pos = 0;
void CreateTree(TreeNode** T)
{//前序递归创建二叉树
char ch;
//scanf("%c", &ch);//读入字符
ch = str[pos++];
if (ch == '#')//.代表空子树
*T = NULL;
else
{
*T = (TreeNode *)malloc(sizeof(TreeNode));
if (!(*T))
{
printf("开辟内存失败\n");
exit(1);
}
(*T)->data = ch;//给T赋值
CreateTree(&(*T)->lchild);//给左子树赋值
CreateTree(&(*T)->rchild);//给右子树赋值
}
}
void preorderTraversal(TreeNode* root)
{
if (!root)
return;
TreeNode* stack[10]; int top = -1;
stack[++top] = root;
while (top > -1)
{
TreeNode* temp = stack[top--];
printf("%c ", temp->data);
if (temp->rchild)
stack[++top] = temp->rchild;
if (temp->lchild)
stack[++top] = temp->lchild;
}
}
void midorderTraversal(TreeNode* root)
{//中序非递归遍历二叉树
TreeNode *stack[10]; int top = -1;
TreeNode *p = root;
while (p != NULL || top > -1)
{
while (p != NULL)
{
stack[++top] = p;
p = p->lchild;
}
if (top > -1)
{
p = stack[top];
printf("%c ", p->data);
--top;
p = p->rchild;
}
}
}
typedef struct tempNode{
TreeNode* btnode;
bool isFirst;
}TempNode;
void postorderTraversal(TreeNode* root)
{//后续非递归遍历二叉树
TempNode *stack[10]; int top = -1;
TreeNode *p = root;
TempNode *temp;
while (p != NULL || top > -1)
{
while (p != NULL) //沿左子树一直往下搜索，直至出现没有左子树的结点
{
TempNode *tempNode = new TempNode;
tempNode->btnode = p;
tempNode->isFirst = true;
stack[++top] = tempNode;
p = p->lchild;
}
if (top > -1)
{
temp = stack[top--];
if (temp->isFirst == true) //表示是第一次出现在栈顶
{
temp->isFirst = false;
stack[++top] = temp;
p = temp->btnode->rchild;
}
else //第二次出现在栈顶
{
printf("%c ", temp->btnode->data);
p = NULL;
}
}
}
}
int choice()
{
printf("*********欢迎来到二叉树非递归遍历演示界面************\n");
printf("0-退出\n");
printf("1-显示前序非递归遍历结果\n");
printf("2-显示中序非递归遍历结果\n");
printf("3-显示后序非递归遍历结果\n");
int n;
printf("请选择:"); scanf("%d", &n);
return n;
}
int main()
{
//freopen("data.txt", "r", stdin);
TreeNode* root;
CreateTree(&root);
int n;
while (1)
{
n = choice();
if (!(n >= 0 && n <= 3))
{
printf("菜单选择错误");
continue;
}
if (n == 0)break;
switch (n)
{
case 1:printf("前序遍历结果:");
preorderTraversal(root); break;
case 2: printf("中序遍历结果:");
midorderTraversal(root);
break;
case 3:
printf("\n后序遍历结果:");
postorderTraversal(root);
break;
}
putchar('\n');
system("pause"); system("cls");
}
}//运行结果ok 2019年5月26日15:36:55
以上代码的运行结果为：
图2 前序遍历
图3 中序遍历
图4 后续遍历
通过比较我在图1中手动遍历的结果与程序运行之后的结果，可以看到我们的代码给出了正确的结果。
- 接下来我们再继续第二个小设计——二叉树的层序遍历，这部分内容比较简单，没什么好讲述的直接贴代码好了，代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef struct treeNode{
char data;
struct treeNode*rchild, *lchild;
}TreeNode;
void CreateTree(TreeNode** T)
{//前序递归创建二叉树
char ch;
scanf("%c", &ch);//读入字符
if (ch == '#')//.代表空子树
*T = NULL;
else
{
*T = (TreeNode *)malloc(sizeof(TreeNode));
if (!(*T))
{
printf("开辟内存失败\n");
exit(1);
}
(*T)->data = ch;//给T赋值
CreateTree(&(*T)->lchild);//给左子树赋值
CreateTree(&(*T)->rchild);//给右子树赋值
}
}
void levelorderTraversal(TreeNode*root)
{//二叉树从左至右，从上至下层次遍历
int front, rear;
TreeNode*que[10];
front = rear = 0;
TreeNode*q;
if (root)
{
rear = (rear + 1) % 10;
que[rear] = root;
while (front != rear)
{
front = (front + 1) % 10;
q = que[front];
printf("%c ", q->data);
if (q->lchild)
{
rear = (rear + 1) % 10;
que[rear] = q->lchild;
}
if (q->rchild)
{
rear = (rear + 1) % 10;
que[rear] = q->rchild;
}
}
}
}
int main()
{
freopen("data.txt", "r", stdin);
TreeNode* root;
CreateTree(&root);
printf("层序遍历结果:");
levelorderTraversal(root);
putchar('\n');
}//运行结果ok2019年5月26日14:37:20
这是一个完整可以执行出结果的代码，不过我们重定义了标准输入为“data.txt”，因此运行这段代码之前你需要在程序所在的文件夹内创建名为“data.txt”的文件，并将"abd#h##k##cef##g##m##"写入该文件保存(字符串不含引号)，然后程序就可以直接从“data.txt”文本中读入二叉树的数据，并将按层序遍历的结果输出。演示结果为：
图5 层序遍历结果
- 完成了第二个关于层序遍历的小任务，再让我们来看最后一个与排序二叉树有关的小任务。
该任务比较简单，要求我们首先生成一颗二叉排序树，然后对其进行中序遍历，输出递增序列。由于中序遍历我们在任务一中已经完成了，因此只需要构建一个能生成二叉排序树的函数就可以了，这里我们采用递归的方式来实现，具体代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef struct treeNode{
int data;
struct treeNode*rchild, *lchild;
}TreeNode;
bool CreateTree(TreeNode** root, int data)
{//二叉排序树创建
if ((*root) == NULL) //如果为空，则创建一个节点
{
*root = (TreeNode *)malloc(sizeof(TreeNode));
(*root)->data = data; ( *root)->lchild = (*root)->rchild = NULL; //该节点为根节点，左孩子和右孩子指针均置空
return true;
}
else if (data == (*root)->data) //如果存在，则返回false
return false;
else if (data < (*root)->data) //如果被插入数据较小，则插入到左子树
return CreateTree(&((*root)->lchild), data);
else //如果被插入数据较大，则插入到右子数
return CreateTree(&((*root)->rchild), data);
}
void midorderTraversal(TreeNode* root)
{//中序非递归遍历二叉树
TreeNode *stack[10]; int top = -1;
TreeNode *p = root;
while (p != NULL || top > -1)
{
while (p != NULL)
{
stack[++top] = p;
p = p->lchild;
}
if (top > -1)
{
p = stack[top];
printf("%d ", p->data);
--top;
p = p->rchild;
}
}
}
int main()
{
TreeNode* root = NULL;
int data;
srand((unsigned)time(NULL));
printf("依次保存在排序树中的值：");
for (int i = 0; i < 10;)
{//通过随机生成数字建立二叉排序树
data = rand() % 20;
if (CreateTree(&root, data))
{
printf("%d ", data);
++i;
}
}
printf("\n中序遍历结果:");
midorderTraversal(root);
putchar('\n');
}//运行结果ok 2019年5月26日14:57:05
图6 二叉排序树演示结果
- 感想：本次课程设计比较简单，但是它一次性的总结了二叉树的创建、非递归先序、中序、后序及层序遍历，对掌握二叉树的遍历方法比较全面系统，因此有必要进行总结，方便下次使用的时候直接参考或者拷贝代码。最后该课程设计也涉及了少量的二叉排序树的知识，但是还不够全面，对二叉排序树的查找和结点删除等相对复杂的点没有过多涉及，以后还需要补充这方面的知识。
