万字超详：二叉树的基本操作（C 语言版）（上）
最编程
2024-04-15 09:31:23
...
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
//使用顺序结构完成二叉树的基本操作
//编写前序、中序、后序以及层次顺序遍历二叉树的算法，并计算二叉树的深度、所有的结点数
#define MAX_SIZE 100
typedef char TElemType;
typedef TElemType SqBiTree[MAX_SIZE];
TElemType Nil = '#';
void input(TElemType* x) {
scanf("%c", &x);
}
void visit(TElemType x) {
printf("%c", x);
}
void InitBiTree(SqBiTree T) {
//构造空二叉树
for (int i = 0; i < MAX_SIZE; i++) {
T[i] = Nil;//初始值为空 #表示为空
}
}
void CreateBiTree(SqBiTree T) {
int i = 1;//按照层次次序输入二叉树中结点的值
scanf("%s", T + 1);
while (T[i]!='\0')
{
i++;
}
T[i] = '#';
}
int BiTreeEmpty(SqBiTree T) {
//初始条件：二叉树T存在。操作结果为：若T为空二叉树，则返回true 否则false
if (T[1] == Nil) {
return 1;//空
}
else {
return 0;
}
}
//返回二叉树的深度
int BiTreeDepth(SqBiTree T) {
int i = MAX_SIZE - 1;
while (T[i] == '#') {
i--;
}
//现在得到的i是存储元素的最后一位
int j = i;
int dep = 0;
while (j >= 1) {
dep++;
j = j / 2;//根据的是树的深度为 【log2n】+1
}
return dep;
}
void PreTraverse(SqBiTree T, int e) {
if (T[e] != '#') {
visit(T[e]);
PreTraverse(T, 2 * e);
PreTraverse(T, 2 * e + 1);//遍历输出结点 左子树 右子树
}
}
void PreOrderTraverse(SqBiTree T) {
//先序遍历
if (!BiTreeEmpty(T)) {
//非空就调用PreTraverse
PreTraverse(T, 1);//从第一个元素就开始
}
printf("\n");
}
void InTraverse(SqBiTree T, int e) {
//中序遍历使用
if (T[e] != '#') {
InTraverse(T, 2 * e);
visit(T[e]);
InTraverse(T, 2 * e + 1);//中序遍历，先左后中再右
}
}
void InOrderTreaverse(SqBiTree T) {
if (!BiTreeEmpty(T)) {
InTraverse(T, 1);
}
printf("\n");
}
//后序遍历
void PostTreaverse(SqBiTree T, int e) {
if (T[e] != '#') {
PostTreaverse(T, e * 2);
PostTreaverse(T, e * 2 + 1);
visit(T[e]);
}
}
void PostOrderTraverse(SqBiTree T) {
if (!BiTreeEmpty(T)){
PostTreaverse(T, 1);
}
printf("\n");
}
//层序遍历二叉树
void LevelOrderTraverse(SqBiTree T) {
int dep = BiTreeDepth(T);
int tree_max = pow(dep, 2) - 1;//得到当前深度下完全二叉树应该有多少结点
for (int i = 1; i < tree_max; i++) {
if (T[i] == '#') {
continue;
}//不用输出‘#’ 而且获得的深度来看，不需要for很多没有价值的 下标 牛逼
visit(T[i]);
}
}
int main()
{
TElemType e;
SqBiTree Bt;
InitBiTree(Bt);
CreateBiTree(Bt);
printf("先序遍历结果为：");
PreOrderTraverse(Bt);
printf("中序遍历结果为：");
InOrderTreaverse(Bt);
printf("后序遍历结果为：");
PostOrderTraverse(Bt);
LevelOrderTraverse(Bt);
return 0;
}
上一篇： 顺序堆栈 - 基本操作和简单应用的实现 (C) (I)
下一篇： R 语言扫描示例解释