main.c
/*
* Change Logs:
* Date Author Notes
* 2021-07-01 tyustli first version
*/
#include "tree.h"
void visit(TElemType e)
{
printf("%d ", e);
}
int main(int argc, char *argv)
{
printf("this is tree sample \r\n");
Status i;
int j;
struct position p;
TElemType e;
SqBiTree T, s;
InitBiTree(T);
CreateBiTree(T);
printf("建立二叉树后,树空否？ %d (1:是 0:否) 树的深度 = %d \r\n", BiTreeEmpty(T), BiTreeDepth(T));
i = Root(T, &e);
if (i)
printf("二叉树的根为：%d\r\n", e);
else
printf("树空，无根\r\n");
printf("层序遍历二叉树:\r\n");
LevelOrderTraverse(T, visit);
printf("中序遍历二叉树:\r\n");
InOrderTraverse(T, visit);
printf("后序遍历二叉树:\r\n");
PostOrderTraverse(T, visit);
return 1;
}
/*
编译：make
运行：./obj
结果：
1
2 3
4 5 6 7
8 9
this is tree sample
请按层序输入结点的值(整型)，0表示空结点，输999结束。结点数≤ 100
1
2
3
4
5
6
7
8
9
999
建立二叉树后,树空否？ 0 (1:是 0:否) 树的深度 = 4
二叉树的根为：1
层序遍历二叉树:
1 2 3 4 5 6 7 8 9
中序遍历二叉树:
8 4 9 2 5 1 6 3 7
后序遍历二叉树:
8 9 4 5 2 6 7 3 1
*/
tree.c
/*
* Change Logs:
* Date Author Notes
* 2021-07-01 tyustli first version
*/
#include "tree.h"
TElemType Nil = 0; // 设整型以0为空
// 二叉树的顺序存储的基本操作(23个)
#define ClearBiTree InitBiTree // 在顺序存储结构中，两函数完全一样
#define DestroyBiTree InitBiTree // 在顺序存储结构中，两函数完全一样
void InitBiTree(SqBiTree T)
{ // 构造空二叉树T。因为T是数组名，故不需要&
int i;
for (i = 0; i < MAX_TREE_SIZE; i++)
T[i] = Nil; // 初值为空(Nil在主程中定义)
}
void CreateBiTree(SqBiTree T)
{ // 按层序次序输入二叉树中结点的值(字符型或整型), 构造顺序存储的二叉树T
int i = 0;
InitBiTree(T); // 构造空二叉树T
printf("请按层序输入结点的值(整型)，0表示空结点，输999结束。结点数≤ %d \r\n", MAX_TREE_SIZE);
while (1)
{
scanf("%d", &T[i]);
if (T[i] == 999)
{
T[i] = Nil;
break;
}
i++;
}
for (i = 1; i < MAX_TREE_SIZE; i++)
{
if (i != 0 && T[(i + 1) / 2 - 1] == Nil && T[i] != Nil) // 此结点(不空)无双亲且不是根
{
printf("出现无双亲的非根结点 %d \r\n", T[i]);
exit(-1);
}
}
}
// 初始条件：二叉树T存在。
// 操作结果：若T为空二叉树，则返回TRUE，否则FALSE
Status BiTreeEmpty(SqBiTree T)
{
if (T[0] == Nil) // 根结点为空，则树空
return TRUE;
else
return FALSE;
}
// 初始条件：二叉树T存在。
// 操作结果：返回T的深度
int BiTreeDepth(SqBiTree T)
{
int i, j = -1;
for (i = MAX_TREE_SIZE - 1; i >= 0; i--) // 找到最后一个结点
if (T[i] != Nil)
break;
i++; // 为了便于计算
do
j++;
while (i >= pow(2.0, j));
return j;
}
// 初始条件：二叉树T存在。
// 操作结果：当T不空，用e返回T的根，返回OK；否则返回ERROR，e无定义
Status Root(SqBiTree T, TElemType *e)
{
if (BiTreeEmpty(T)) // T空
{
return ERROR;
}
else
{
*e = T[0];
return OK;
}
}
// 初始条件：二叉树T存在，e是 T 中某个结点(的位置)
// 操作结果：返回处于位置 e (层,本层序号)的结点的值
TElemType Value(SqBiTree T, struct position e)
{
return T[(int)(pow(2, e.level - 1) + e.order - 2)];
}
// 初始条件：二叉树T存在，e 是 T 中某个结点(的位置)
// 操作结果：给处于位置 e (层,本层序号)的结点赋新值 value
Status Assign(SqBiTree T, struct position e, TElemType value)
{
int i = (int)(pow(2, e.level - 1) + e.order - 2); // 将层、本层序号转为矩阵的序号
if (value != Nil && T[(i + 1) / 2 - 1] == Nil) // 给叶子赋非空值但双亲为空
return ERROR;
else if (value == Nil && (T[i * 2 + 1] != Nil || T[i * 2 + 2] != Nil)) // 给双亲赋空值但有叶子(不空)
return ERROR;
T[i] = value;
return OK;
}
// 初始条件：二叉树 T 存在，e 是 T 中某个结点
// 操作结果：若 e 是 T 的非根结点，则返回它的双亲，否则返回＂空＂
TElemType Parent(SqBiTree T, TElemType e)
{
int i;
if (T[0] == Nil) // 空树
return Nil;
for (i = 1; i <= MAX_TREE_SIZE - 1; i++)
if (T[i] == e) // 找到e
return T[(i + 1) / 2 - 1];
return Nil; // 没找到e
}
// 初始条件：二叉树T存在，e 是 T 中某个结点。
// 操作结果：返回 e 的左孩子。若 e 无左孩子,则返回"空"
TElemType LeftChild(SqBiTree T, TElemType e)
{
int i;
if (T[0] == Nil) // 空树
return Nil;
for (i = 0; i <= MAX_TREE_SIZE - 1; i++)
if (T[i] == e) // 找到e
return T[i * 2 + 1];
return Nil; // 没找到e
}
// 初始条件：二叉树T存在，e 是 T 中某个结点。
// 操作结果：返回 e 的右孩子。若 e 无右孩子,则返回"空"
TElemType RightChild(SqBiTree T, TElemType e)
{
int i;
if (T[0] == Nil) // 空树
return Nil;
for (i = 0; i <= MAX_TREE_SIZE - 1; i++)
if (T[i] == e) // 找到e
return T[i * 2 + 2];
return Nil; // 没找到e
}
// 初始条件：二叉树 T 存在，e 是 T 中某个结点
// 操作结果：返回 e 的左兄弟。若 e 是 T 的左孩子或无左兄弟，则返回＂空＂
TElemType LeftSibling(SqBiTree T, TElemType e)
{
int i;
if (T[0] == Nil) // 空树
return Nil;
for (i = 1; i <= MAX_TREE_SIZE - 1; i++)
if (T[i] == e && i % 2 == 0) // 找到e且其序号为偶数(是右孩子)
return T[i - 1];
return Nil; // 没找到e
}
// 初始条件：二叉树T存在，e是T中某个结点
// 操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回＂空＂
TElemType RightSibling(SqBiTree T, TElemType e)
{
int i;
if (T[0] == Nil) // 空树
return Nil;
for (i = 1; i <= MAX_TREE_SIZE - 1; i++)
if (T[i] == e && i % 2) // 找到e且其序号为奇数(是左孩子)
return T[i + 1];
return Nil; // 没找到e
}
void Move(SqBiTree q, int j, SqBiTree T, int i) // InsertChild() 用到
{ // 把从 q 的 j 结点开始的子树移为从 T 的 i 结点开始的子树
if (q[2 * j + 1] != Nil) // q 的左子树不空
Move(q, (2 * j + 1), T, (2 * i + 1)); // 把 q 的 j 结点的左子树移为 T 的 i 结点的左子树
if (q[2 * j + 2] != Nil) // q 的右子树不空
Move(q, (2 * j + 2), T, (2 * i + 2)); // 把 q 的 j 结点的右子树移为 T 的 i 结点的右子树
T[i] = q[j]; // 把 q 的 j 结点移为 T 的 i 结点
q[j] = Nil; // 把 q 的 j 结点置空
}
// 初始条件：二叉树 T 存在，p 是 T 中某个结点的值，LR 为 0 或 1，非空二叉树 c 与 T 不相交且右子树为空
// 操作结果: 根据 LR 为 0 或 1,插入 c 为 T 中 p 结点的左或右子树。p 结点的原有左或右子树则成为 c 的右子树
void InsertChild(SqBiTree T, TElemType p, int LR, SqBiTree c)
{
int j, k, i = 0;
for (j = 0; j < (int)(pow(2, BiTreeDepth(T))) - 1; j++) // 查找p的序号
if (T[j] == p) // j为p的序号
break;
k = 2 * j + 1 + LR; // k为p的左或右孩子的序号
if (T[k] != Nil) // p原来的左或右孩子不空
Move(T, k, T, 2 * k + 2); // 把从T的k结点开始的子树移为从k结点的右子树开始的子树
Move(c, i, T, k); // 把从c的i结点开始的子树移为从T的k结点开始的子树
}
// typedef int QElemType; // 设队列元素类型为整型(序号)
// Status DeleteChild(SqBiTree T, position p, int LR)
// { // 初始条件：二叉树T存在，p指向T中某个结点，LR为1或0
// // 操作结果：根据LR为1或0，删除T中p所指结点的左或右子树
// int i;
// Status k = OK; // 队列不空的标志
// LinkQueue q;
// InitQueue(q); // 初始化队列，用于存放待删除的结点
// i = (int)pow(2, p.level - 1) + p.order - 2; // 将层、本层序号转为矩阵的序号
// if (T[i] == Nil) // 此结点空
// return ERROR;
// i = i * 2 + 1 + LR; // 待删除子树的根结点在矩阵中的序号
// while (k)
// {
// if (T[2 * i + 1] != Nil) // 左结点不空
// EnQueue(q, 2 * i + 1); // 入队左结点的序号
// if (T[2 * i + 2] != Nil) // 右结点不空
// EnQueue(q, 2 * i + 2); // 入队右结点的序号
// T[i] = Nil; // 删除此结点
// k = DeQueue(q, i); // 队列不空
// }
// return OK;
// }
void (*VisitFunc)(TElemType); // 函数变量
void PreTraverse(SqBiTree T, int e)
{ // PreOrderTraverse()调用
VisitFunc(T[e]);
if (T[2 * e + 1] != Nil) // 左子树不空
PreTraverse(T, 2 * e + 1);
if (T[2 * e + 2] != Nil) // 右子树不空
PreTraverse(T, 2 * e + 2);
}
void PreOrderTraverse(SqBiTree T, void (*Visit)(TElemType))
{ // 初始条件：二叉树存在，Visit是对结点操作的应用函数
// 操作结果：先序遍历T，对每个结点调用函数Visit一次且仅一次
VisitFunc = Visit;
if (!BiTreeEmpty(T)) // 树不空
PreTraverse(T, 0);
printf("\r\n");
}
void InTraverse(SqBiTree T, int e)
{ // InOrderTraverse()调用
if (T[2 * e + 1] != Nil) // 左子树不空
InTraverse(T, 2 * e + 1);
VisitFunc(T[e]);
if (T[2 * e + 2] != Nil) // 右子树不空
InTraverse(T, 2 * e + 2);
}
void InOrderTraverse(SqBiTree T, void (*Visit)(TElemType))
{ // 初始条件：二叉树存在，Visit是对结点操作的应用函数
// 操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次
VisitFunc = Visit;
if (!BiTreeEmpty(T)) // 树不空
InTraverse(T, 0);
printf("\r\n");
}
void PostTraverse(SqBiTree T, int e)
{ // PostOrderTraverse()调用
if (T[2 * e + 1] != Nil) // 左子树不空
PostTraverse(T, 2 * e + 1);
if (T[2 * e + 2] != Nil) // 右子树不空
PostTraverse(T, 2 * e + 2);
VisitFunc(T[e]);
}
void PostOrderTraverse(SqBiTree T, void (*Visit)(TElemType))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序遍历T，对每个结点调用函数Visit一次且仅一次
VisitFunc = Visit;
if (!BiTreeEmpty(T)) // 树不空
PostTraverse(T, 0);
printf("\r\n");
}
void LevelOrderTraverse(SqBiTree T, void (*Visit)(TElemType))
{ // 层序遍历二叉树
int i = MAX_TREE_SIZE - 1, j;
while (T[i] == Nil)
i--; // 找到最后一个非空结点的序号
for (j = 0; j <= i; j++) // 从根结点起，按层序遍历二叉树
if (T[j] != Nil)
Visit(T[j]); // 只遍历非空的结点
printf("\r\n");
}
void Print(SqBiTree T)
{ // 逐层、按本层序号输出二叉树
int j, k;
struct position p;
TElemType e;
for (j = 1; j <= BiTreeDepth(T); j++)
{
printf("第 %d 层: ", j);
for (k = 1; k <= pow(2, j - 1); k++)
{
p.level = j;
p.order = k;
e = Value(T, p);
if (e != Nil)
printf("k = %d e = %d", k, e);
}
printf("\r\n");
}
}
tree.h
/*
* Change Logs:
* Date Author Notes
* 2021-07-01 tyustli first version
*/
#include <string.h>
#include <ctype.h>
#include <malloc.h> // malloc()等
#include <limits.h> // INT_MAX等
#include <stdio.h> // EOF(=^Z或F6),NULL
#include <stdlib.h> // atoi()
#include <math.h> // floor(),ceil(),abs()
#define CHAR 0 // 整型(二者选一)
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
// #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
typedef int TElemType;
// 二叉树的顺序存储表示
#define MAX_TREE_SIZE 100 // 二叉树的最大结点数
typedef TElemType SqBiTree[MAX_TREE_SIZE]; // 0号单元存储根结点
struct position
{
int level, order; // 结点的层,本层序号(按满二叉树计算)
};
void InitBiTree(SqBiTree T);
void CreateBiTree(SqBiTree T);
Status BiTreeEmpty(SqBiTree T);
int BiTreeDepth(SqBiTree T);
Status Root(SqBiTree T, TElemType *e);
TElemType Value(SqBiTree T, struct position e);
Status Assign(SqBiTree T, struct position e, TElemType value);
TElemType Parent(SqBiTree T, TElemType e);
TElemType LeftChild(SqBiTree T, TElemType e);
TElemType RightChild(SqBiTree T, TElemType e);
TElemType LeftSibling(SqBiTree T, TElemType e);
TElemType RightSibling(SqBiTree T, TElemType e);
void Move(SqBiTree q, int j, SqBiTree T, int i);
void InsertChild(SqBiTree T, TElemType p, int LR, SqBiTree c);
Status DeleteChild(SqBiTree T, struct position p, int LR);
void PreTraverse(SqBiTree T, int e);
void PreOrderTraverse(SqBiTree T, void (*Visit)(TElemType));
void InTraverse(SqBiTree T, int e);
void InOrderTraverse(SqBiTree T, void (*Visit)(TElemType));
void PostTraverse(SqBiTree T, int e);
void PostOrderTraverse(SqBiTree T, void (*Visit)(TElemType));
void LevelOrderTraverse(SqBiTree T, void (*Visit)(TElemType));
void Print(SqBiTree T);
makefile
objects = main.o tree.o
obj: $(objects)
cc -o obj $(objects) -lm
main.o : tree.h
tree.o : tree.h
.PHONY : clean
clean :
-rm obj $(objects)