1. 背景说明
2. 示例代码
1) errorRecord.h
// 记录错误宏定义头文件
#ifndef ERROR_RECORD_H
#define ERROR_RECORD_H
#include <stdio.h>
#include <string.h>
#include <stdint.h>
// 从文件路径中提取文件名
#define FILE_NAME(X) strrchr(X, '\\') ? strrchr(X, '\\') + 1 : X
// 定义用于启用调试模式的 DEBUG 宏
#define DEBUG
// 打印错误消息
#ifdef DEBUG
#define ERR_RECORD(ERR_CODE, ...) do { \
printf(ANSI_COLOR_BRIGHT_CYAN \
"\n\nFile: %-25s Func: %-20s Line: %-10d ErrorCode: %-8d ErrorInfo: ", \
FILE_NAME(__FILE__), __func__, __LINE__, (ERR_CODE)); \
printf(""__VA_ARGS__); \
printf("\n" ANSI_COLOR_RESET); \
PrintErrorCodeInfo(ERR_CODE); \
} while (0)
#else
#define ERR_RECORD(ERR_CODE, FORMAT, ...)
#endif
// 函数结果状态代码
enum StatusCode {
RET_OK = 0, // 操作成功
ERR_NULL_PTR = 1, // 空指针错误
ERR_MEMORY_ALLOCATE = 2, // 内存分配错误
ERR_EMPTY_STACK = 3, // 空栈错误
ERR_FULL_STACK = 4, // 满栈错误
ERR_EMPTY_QUEUE = 5, // 空队列错误
ERR_FULL_QUEUE = 6, // 满队列错误
ERR_PARA_ILLEGAL = 7, // 参数非法错误
ERR_OPEN_FILE = 8, // 文件打开错误
ERR_NOT_EXIST = 9, // 目标不存在错误
ERR_UNKNOW_ERR = 10 // 未知错误
};
enum BoolCode {
TRUE = 1,
FALSE = 0
};
typedef uint32_t Status;
typedef uint8_t Boolean;
// ANSI 转义码定义
#define ANSI_COLOR_BRIGHT_RED "\x1b[91m"
#define ANSI_COLOR_BRIGHT_YELLOW "\x1b[93m"
#define ANSI_COLOR_BRIGHT_CYAN "\x1b[96m"
#define ANSI_COLOR_RESET "\x1b[0m"
// 打印错误代码信息
static void PrintErrorCodeInfo(int errorCode)
{
switch (errorCode) {
case ERR_NULL_PTR:
printf(ANSI_COLOR_BRIGHT_RED "Null Pointer Error\n\n" ANSI_COLOR_RESET);
break;
case ERR_MEMORY_ALLOCATE:
printf(ANSI_COLOR_BRIGHT_RED "Memory Allocation Error\n\n" ANSI_COLOR_RESET);
break;
case ERR_EMPTY_STACK:
printf(ANSI_COLOR_BRIGHT_RED "Empty Stack Error\n\n" ANSI_COLOR_RESET);
break;
case ERR_FULL_STACK:
printf(ANSI_COLOR_BRIGHT_RED "Full Stack Error\n\n" ANSI_COLOR_RESET);
break;
case ERR_EMPTY_QUEUE:
printf(ANSI_COLOR_BRIGHT_RED "Empty Queue Error\n\n" ANSI_COLOR_RESET);
break;
case ERR_FULL_QUEUE:
printf(ANSI_COLOR_BRIGHT_RED "Full Queue Error\n\n" ANSI_COLOR_RESET);
break;
case ERR_PARA_ILLEGAL:
printf(ANSI_COLOR_BRIGHT_RED "Illegal Parameter Error\n\n" ANSI_COLOR_RESET);
break;
case ERR_OPEN_FILE:
printf(ANSI_COLOR_BRIGHT_RED "File Open Error\n\n" ANSI_COLOR_RESET);
break;
case ERR_NOT_EXIST:
printf(ANSI_COLOR_BRIGHT_RED "Not Exist Error\n\n" ANSI_COLOR_RESET);
break;
default:
printf(ANSI_COLOR_BRIGHT_YELLOW "Unknown Error Code: %d\n\n" ANSI_COLOR_RESET, errorCode);
break;
}
}
#endif // !ERROR_RECORD_H
2）sqQueue.h
// 顺序队列实现头文件
#ifndef SQQUEUE_H
#define SQQUEUE_H
#include "errorRecord.h"
#define MAX_QUEUE_SIZE 5
typedef int QElemType;
typedef struct {
QElemType *base;
int front;
int rear;
} SqQueue;
Status InitQueue(SqQueue *queue);
Status DestroyQueue(SqQueue *queue);
Status ClearQueue(SqQueue *queue);
Status QueueEmpty(const SqQueue *queue, Boolean *isEmpty);
Status QueueLength(const SqQueue *queue, int *length);
Status GetQueueHead(const SqQueue *queue, QElemType *e);
Status EnQueue(QElemType e, SqQueue *queue);
Status DeQueue(SqQueue *queue, QElemType *e);
Status QueueTraverse(const SqQueue *queue, void(*vi)(QElemType));
#endif // !SQQUEUE_H
3) sqQueue.c
// 顺序队列实现源文件
#include "sqQueue.h"
#include <stdlib.h>
static Boolean QueueFull(const SqQueue *queue)
{
return (queue->rear >= MAX_QUEUE_SIZE) ? TRUE : FALSE;
}
/*
前置条件：queue 非空
操作结果：将 *queue 重置为空表
*/
Status InitQueue(SqQueue *queue)
{
if (!queue) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
queue->base = (QElemType *)malloc(sizeof(QElemType) * MAX_QUEUE_SIZE);
if (!queue->base) {
ERR_RECORD(ERR_MEMORY_ALLOCATE);
return ERR_MEMORY_ALLOCATE;
}
queue->front = queue->rear = 0;
return RET_OK;
}
/*
前置条件：queue 非空
操作结果：销毁队列 *queue
*/
Status DestroyQueue(SqQueue *queue)
{
if (!queue) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
if (queue->base) {
free(queue->base);
}
queue->base = NULL;
queue->front = queue->rear = 0;
return RET_OK;
}
/*
前置条件：queue 非空
操作结果：清空队列 *queue
*/
Status ClearQueue(SqQueue *queue)
{
if (!queue) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
queue->front = queue->rear = 0;
return RET_OK;
}
/*
前置条件：queue 非空
操作结果：用 *isEmpty 返回 *queue 是否为空
*/
Status QueueEmpty(const SqQueue *queue, Boolean *isEmpty)
{
if (!queue || !isEmpty) {
ERR_RECORD(ERR_NULL_PTR, "queue = %p, isEmpty = %p", queue, isEmpty);
return ERR_NULL_PTR;
}
*isEmpty = (queue->front == queue->rear) ? TRUE : FALSE;
return RET_OK;
}
/*
前置条件：queue 非空
操作结果：用 *length 返回 *queue 的元素个数,即队列的长度
*/
Status QueueLength(const SqQueue *queue, int *length)
{
if (!queue || !length) {
ERR_RECORD(ERR_NULL_PTR, "queue = %p, length = %p", queue, length);
return ERR_NULL_PTR;
}
*length = (queue->rear - queue->front);
return RET_OK;
}
/*
前置条件：queue 非空
操作结果：则用 *e 返回 *queue 的队头元素
*/
Status GetQueueHead(const SqQueue *queue, QElemType *e)
{
if (!queue || !e) {
ERR_RECORD(ERR_NULL_PTR, "queue = %p, e = %p", queue, e);
return ERR_NULL_PTR;
}
if (queue->front == queue->rear) {
ERR_RECORD(ERR_EMPTY_QUEUE);
return ERR_EMPTY_QUEUE;
}
*e = *(queue->base + queue->front);
return RET_OK;
}
/*
前置条件：queue 非空
操作结果：插入元素 e 为 *queue 的新的队尾元素
*/
Status EnQueue(QElemType e, SqQueue *queue)
{
if (!queue) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
if (QueueFull(queue)) {
QElemType *newBase = (QElemType *)realloc(queue->base, sizeof(QElemType) *
(unsigned long long)(queue->rear + 1));
if (!newBase) {
ERR_RECORD(ERR_MEMORY_ALLOCATE);
return ERR_MEMORY_ALLOCATE;
}
queue->base = newBase;
}
queue->base[queue->rear] = e;
++queue->rear;
return RET_OK;
}
/*
前置条件：queue 非空
操作结果：删除 *queue 的队头元素,用 *e 返回其值
*/
Status DeQueue(SqQueue *queue, QElemType *e)
{
if (!queue || !e) {
ERR_RECORD(ERR_NULL_PTR, "queue = %p, e = %p", queue, e);
return ERR_NULL_PTR;
}
Boolean isEmpty;
QueueEmpty(queue, &isEmpty);
if (isEmpty) {
ERR_RECORD(ERR_EMPTY_QUEUE);
return ERR_EMPTY_QUEUE;
}
*e = queue->base[queue->front];
queue->front = queue->front + 1;
return RET_OK;
}
/*
前置条件：queue 非空
操作结果：从队头到队尾依次对队列 queue 中每个元素调用函数 vi()
*/
Status QueueTraverse(const SqQueue *queue, void(*vi)(QElemType))
{
if (!queue || !vi) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
int pos = queue->front;
while (pos != queue->rear) {
vi(queue->base[pos]);
++pos;
}
return RET_OK;
}
4) sqBiTree.h
// 二叉树的顺序存储表示实现头文件
#ifndef SQ_BI_TREE_H
#define SQ_BI_TREE_H
#include "errorRecord.h"
#include "sqQueue.h"
#define MAX_TREE_NODE_SIZE 100 // 二叉树的最大结点数
#define CHAR 1
#if CHAR
typedef char TElemType;
static TElemType Nil = ' ';
#else
typedef int TElemType;
static TElemType Nil = 0;
#endif
typedef TElemType SqBiTree[MAX_TREE_NODE_SIZE]; // 0 号单元存储根结点
typedef struct {
int level; // 结点的层
int order; // 结点的序号，按照满二叉树计算
} Position;
typedef Boolean(*IsEqual)(const TElemType *, const TElemType *);
Status InitBiTree(SqBiTree biTree);
void DestroyBiTree();
Status CreateBiTree(SqBiTree biTree);
#define ClearBiTree InitBiTree
Status IsBiTreeEmpty(const SqBiTree biTree, IsEqual isEqual, Boolean *isEmpty);
int GetBiTreeDepth(const SqBiTree biTree);
Status GetBiTreeRoot(const SqBiTree biTree, IsEqual isEqual, TElemType *e);
Status GetValue(const SqBiTree biTree, const Position *pos, TElemType *e);
Status Assign(IsEqual isEqual, const Position *pos, const TElemType *e, SqBiTree biTree);
Status GetParentValue(const SqBiTree biTree, IsEqual isEqual, const TElemType *e, TElemType *parent);
Status GetLeftChildValue(const SqBiTree biTree, IsEqual isEqual, const TElemType *e, TElemType *leftChild);
Status GetRightChildValue(const SqBiTree biTree, IsEqual isEqual, const TElemType *e, TElemType *rightChild);
Status GetLeftSiblingValue(const SqBiTree biTree, IsEqual isEqual, const TElemType *e, TElemType *leftSibling);
Status GetRightSiblingValue(const SqBiTree biTree, IsEqual isEqual, const TElemType *e, TElemType *rightSibling);
Status InsertChildTree(int side, const TElemType *e, IsEqual isEqual, SqBiTree biTreeA, SqBiTree biTreeB);
Status DeleteChildTree(int side, IsEqual isEqual, const Position *pos, SqBiTree biTree);
Status PreOrderTraverse(const SqBiTree biTree, IsEqual isEqual, Status(*visit)(const TElemType *));
Status InOrderTraverse(const SqBiTree biTree, IsEqual isEqual, Status(*visit)(const TElemType *));
Status PostOrderTraverse(const SqBiTree biTree, IsEqual isEqual, Status(*visit)(const TElemType *));
Status LevelOrderTraverse(const SqBiTree biTree, IsEqual isEqual, Status(*visit)(const TElemType *));
Status PrintBiTree(const SqBiTree biTree, Status(*visit)(const TElemType *));
#endif // !SQ_BI_TREE_H
5) sqBiTree.c
// 二叉树的顺序存储表示实现源文件
#include "sqBiTree.h"
#include <math.h>
/*
前置条件：无
操作结果：构造空二叉树 biTree
*/
Status InitBiTree(SqBiTree biTree)
{
for (int i = 0; i < MAX_TREE_NODE_SIZE; ++i) {
biTree[i] = Nil;
}
return RET_OK;
}
/*
前置条件：无
操作结果：销毁二叉树 biTree
*/
void DestroyBiTree()
{
printf("由于 SqBiTree 是定长类型,无法销毁\n");
}
// 安全读取最多 n - 1 个字符，读取成功返回 str 地址，失败返回 NULL
static char *SafeGetStr(int n, char *str)
{
char *ret = fgets(str, n, stdin);
if (!ret) {
ERR_RECORD(ERR_UNKNOW_ERR);
return NULL;
}
int i = 0;
while ((str[i] != '\n') && (str[i] != '\0')) {
++i;
}
if (str[i] == '\n') {
str[i] = '\0';
} else {
while (getchar() != '\n') {
continue;
}
}
return ret;
}
/*
前置条件：无
操作结果：销按层序次序输入二叉树中结点的值(字符型或整型), 构造顺序存储的二叉树
*/
Status CreateBiTree(SqBiTree biTree)
{
#if CHAR
char str[MAX_TREE_NODE_SIZE + 1] = { 0 };
printf("请按层序输入结点的值(字符)，空格表示空结点，结点数 ≤ %d:\n", MAX_TREE_NODE_SIZE);
if (!SafeGetStr(MAX_TREE_NODE_SIZE + 1, str)) {
ERR_RECORD(ERR_UNKNOW_ERR);
return ERR_UNKNOW_ERR;
}
int length = (int)strlen(str);
for (int i = 0; i < length; ++i) {
biTree[i] = str[i];
if ((i != 0) && (Nil == biTree[(i + 1) / 2 - 1]) && (biTree[i] != Nil)) {
ERR_RECORD(ERR_PARA_ILLEGAL, "i = %d", i);
printf("出现无双亲的非根结点 %c\n", biTree[i]);
return ERR_PARA_ILLEGAL;
}
}
for (int i = length; i < MAX_TREE_NODE_SIZE; ++i) {
biTree[i] = Nil;
}
#else
printf("请按层序输入结点的值(整型)，0 表示空结点，-1 结束。结点数 ≤ %d:\n", MAX_TREE_NODE_SIZE);
int i = 0;
while (TRUE) {
scanf_s("%d", biTree + i);
if (-1 == biTree[i]) {
break;
}
if ((i != 0) && (Nil == biTree[(i + 1) / 2 - 1]) && (biTree[i] != Nil)) {
ERR_RECORD(ERR_PARA_ILLEGAL, "i = %d", i);
printf("出现无双亲的非根结点 %c\n", biTree[i]);
return ERR_PARA_ILLEGAL;
}
++i;
}
while (i < MAX_TREE_NODE_SIZE) {
biTree[i] = Nil;
++i;
}
#endif
return RET_OK;
}
/*
前置条件：二叉树 biTree 存在
操作结果：返回二叉树是否为空
*/
Status IsBiTreeEmpty(const SqBiTree biTree, IsEqual isEqual, Boolean *isEmpty)
{
if (!isEqual || !isEmpty) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
*isEmpty = isEqual(&Nil, biTree) ? TRUE : FALSE;
return RET_OK;
}
/*
前置条件：二叉树 biTree 存在
操作结果：返回二叉树 biTree 的深度
*/
int GetBiTreeDepth(const SqBiTree biTree, IsEqual isEqual)
{
// 找到最后一个结点的编号
int lastNodeId;
for (lastNodeId = MAX_TREE_NODE_SIZE - 1; lastNodeId >= 0; --lastNodeId) {
if (!isEqual(biTree + lastNodeId, &Nil)) {
break;
}
}
++lastNodeId; // 数组从 0 开始计数，因此需要加 1 以获取树的最后一个结点编号
int depth = -1;
do {
++depth;
} while (pow(2, depth) <= lastNodeId);
return depth;
}
/*
前置条件：二叉树 biTree 存在
操作结果：用 e 返回二叉树的根结点的值
*/
Status GetBiTreeRoot(const SqBiTree biTree, IsEqual isEqual, TElemType *e)
{
if (!isEqual || !e) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
Boolean isEmpty;
IsBiTreeEmpty(biTree, isEqual, &isEmpty);
if (isEmpty) {
ERR_RECORD(ERR_NOT_EXIST);
return ERR_NOT_EXIST;
}
*e = biTree[0];
return RET_OK;
}
/*
前置条件：二叉树 biTree 存在, pos 是 biTree 中某个结点的位置
操作结果：用 e 返回二叉树的 pos 位置结点的值
*/
Status GetValue(const SqBiTree biTree, const Position *pos, TElemType *e)
{
if (!pos || !e) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
*e = biTree[(int)pow(2, pos->level - 1) + pos->order - 2];
return RET_OK;
}
/*
前置条件：二叉树 biTree 存在, pos 是 biTree 中某个结点的位置
操作结果：给位置处于 pos 的结点赋值 e
*/
Status Assign(IsEqual isEqual, const Position *pos, const TElemType *e, SqBiTree biTree)
{
if (!isEqual || !pos || !e) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
int order = (int)pow(2, pos->level - 1) + pos->order - 2;
// 给叶子赋非空值但双亲为空
if (!isEqual(e, &Nil) && isEqual(biTree + (order + 1) / 2 - 1, &Nil)) {
ERR_RECORD(ERR_PARA_ILLEGAL);
return ERR_PARA_ILLEGAL;
}
// 给双亲赋空值但有叶子
if (isEqual(e, &Nil) && (isEqual(biTree + order * 2 + 1, &Nil) || isEqual(biTree + order * 2 + 2, &Nil))) {
ERR_RECORD(ERR_PARA_ILLEGAL);
return ERR_PARA_ILLEGAL;
}
biTree[order] = *e;
return RET_OK;
}
/*
前置条件：二叉树 biTree 存在, e 是 biTree 中某个结点的值
操作结果：返回该结点的双亲的值
*/
Status GetParentValue(const SqBiTree biTree, IsEqual isEqual, const TElemType *e, TElemType *parent)
{
if (!isEqual || !e || !parent) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
if (isEqual(biTree, &Nil)) {
ERR_RECORD(ERR_NOT_EXIST);
return ERR_NOT_EXIST;
}
for (int i = 1; i < MAX_TREE_NODE_SIZE; ++i) {
if (isEqual(e, biTree + i)) {
*parent = biTree[(i + 1) / 2 - 1];
return RET_OK;
}
}
ERR_RECORD(ERR_NOT_EXIST);
return ERR_NOT_EXIST;
}
/*
前置条件：二叉树 biTree 存在, e 是 biTree 中某个结点的值
操作结果：返回该结点的左孩子的值
*/
Status GetLeftChildValue(const SqBiTree biTree, IsEqual isEqual, const TElemType *e, TElemType *leftChild)
{
if (!isEqual || !e || !leftChild) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
if (isEqual(biTree, &Nil)) {
ERR_RECORD(ERR_NOT_EXIST);
return ERR_NOT_EXIST;
}
for (int i = 0; i < MAX_TREE_NODE_SIZE; ++i) {
if (isEqual(e, biTree + i)) {
*leftChild = biTree[2 * i + 1];
return RET_OK;
}
}
ERR_RECORD(ERR_NOT_EXIST);
return ERR_NOT_EXIST;
}
/*
前置条件：二叉树 biTree 存在, e 是 biTree 中某个结点的值
操作结果：返回该结点的右孩子的值
*/
Status GetRightChildValue(const SqBiTree biTree, IsEqual isEqual, const TElemType *e, TElemType *rightChild)
{
if (!isEqual || !e || !rightChild) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
if (isEqual(biTree, &Nil)) {
ERR_RECORD(ERR_NOT_EXIST);
return ERR_NOT_EXIST;
}
for (int i = 0; i < MAX_TREE_NODE_SIZE; ++i) {
if (isEqual(e, biTree + i)) {
*rightChild = biTree[2 * i + 2];
return RET_OK;
}
}
ERR_RECORD(ERR_NOT_EXIST);
return ERR_NOT_EXIST;
}
/*
前置条件：二叉树 biTree 存在, e 是 biTree 中某个结点的值
操作结果：返回该结点的左兄弟的值
*/
Status GetLeftSiblingValue(const SqBiTree biTree, IsEqual isEqual, const TElemType *e, TElemType *leftSibling)
{
if (!isEqual || !e || !leftSibling) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
if (isEqual(biTree, &Nil)) {
ERR_RECORD(ERR_NOT_EXIST);
return ERR_NOT_EXIST;
}
for (int i = 1; i < MAX_TREE_NODE_SIZE; ++i) {
if (isEqual(e, biTree + i) && (i % 2 == 0)) {
*leftSibling = biTree[i - 1];
return RET_OK;
}
}
ERR_RECORD(ERR_NOT_EXIST);
return ERR_NOT_EXIST;
}
/*
前置条件：二叉树 biTree 存在, e 是 biTree 中某个结点的值
操作结果：返回该结点的右兄弟的值
*/
Status GetRightSiblingValue(const SqBiTree biTree, IsEqual isEqual, const TElemType *e, TElemType *rightSibling)
{
if (!isEqual || !e || !rightSibling) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
if (isEqual(biTree, &Nil)) {
ERR_RECORD(ERR_NOT_EXIST);
return ERR_NOT_EXIST;
}
for (int i = 1; i < MAX_TREE_NODE_SIZE; ++i) {
if (isEqual(e, biTree + i) && (i % 2)) {
*rightSibling = biTree[i + 1];
return RET_OK;
}
}
ERR_RECORD(ERR_NOT_EXIST);
return ERR_NOT_EXIST;
}
// 把从 q 的 j 结点开始的子树移为从 p 的 i 结点开始的子树
static void Move(int i, int j, IsEqual isEqual, SqBiTree q, SqBiTree p)
{
// q 左子树非空
if (!isEqual(q + 2 * j + 1, &Nil)) {
Move(2 * i + 1, 2 * j + 1, isEqual, q, p);
}
// q 右子树非空
if (!isEqual(q + 2 * j + 2, &Nil)) {
Move(2 * i + 2, 2 * j + 2, isEqual, q, p);
}
p[i] = q[j];
q[j] = Nil;
}
/*
前置条件：二叉树 biTreeA 存在, e 是 biTreeA 中某个结点的值, side 为 0 或 1，非空二叉树 biTreeB 与 biTreeA 互不相交
且右子树为空
操作结果：根据 side 为 0 或 1，插入 biTreeB 为 biTreeA 中 e 所在结点的左或右子树， biTreeA 原有结点的左或右子树则
成为 biTreeB 的右子树
*/
Status InsertChildTree(int side, const TElemType *e, IsEqual isEqual, SqBiTree biTreeA, SqBiTree biTreeB)
{
if (!e || !isEqual) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
// 查找 e 的序号
int order = 0;
for (; order < (int)pow(2, GetBiTreeDepth(biTreeA, isEqual)) - 1; ++order) {
if (isEqual(e, biTreeA + order)) {
break;
}
}
int childId = 2 * order + 1 + side; // 元素 e 所在结点的左孩子或右孩子的序号
if (!isEqual(biTreeA + childId, &Nil)) { // 元素 e 所在结点的左孩子或右孩子非空
// 把从 biTreeA 的 childId 结点开始的子树移为从 childId 结点的右子树开始的子树
Move(2 * childId + 2, childId, isEqual, biTreeA, biTreeA);
}
// 把 biTreeB 移为从 biTreeA 的 childId 结点开始的子树
Move(childId, 0, isEqual, biTreeB, biTreeA);
return RET_OK;
}
/*
前置条件：二叉树 biTree 存在, e 是 biTree 中某个结点的值, side 为 0 或 1
操作结果：根据 side 为 0 或 1，删除 biTree 中 e 所在结点的左或右子树
*/
Status DeleteChildTree(int side, IsEqual isEqual, const Position *pos, SqBiTree biTree)
{
if (!isEqual || !pos) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
int order = (int)pow(2, pos->level - 1) + pos->order - 2;
if (isEqual(biTree + order, &Nil)) {
ERR_RECORD(ERR_PARA_ILLEGAL);
return ERR_PARA_ILLEGAL;
}
order = 2 * order + 1 + side; // 待删除子树的根结点的序号
SqQueue nodeQueue;
InitQueue(&nodeQueue);
Status ret = RET_OK;
while (!ret) {
if (!isEqual(biTree + 2 * order + 1, &Nil)) { // 左结点非空
EnQueue(2 * order + 1, &nodeQueue);
}
if (!isEqual(biTree + 2 * order + 2, &Nil)) { // 右结点非空
EnQueue(2 * order + 2, &nodeQueue);
}
biTree[order] = Nil;
ret = DeQueue(&nodeQueue, &order);
}
return RET_OK;
}
// 先序遍历二叉树辅助函数
static void PreTraverse(const SqBiTree biTree, int order, IsEqual isEqual, Status(*visit)(const TElemType *))
{
visit(biTree + order);
if (!isEqual(biTree + 2 * order + 1, &Nil)) {
PreTraverse(biTree, 2 * order + 1, isEqual, visit);
}
if (!isEqual(biTree + 2 * order + 2, &Nil)) {
PreTraverse(biTree, 2 * order + 2, isEqual, visit);
}
}
/*
前置条件：二叉树 biTree 存在
操作结果：先序遍历二叉树 biTree
*/
Status PreOrderTraverse(const SqBiTree biTree, IsEqual isEqual, Status(*visit)(const TElemType *))
{
if (!isEqual || !visit) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
Boolean isEmpty;
IsBiTreeEmpty(biTree, isEqual, &isEmpty);
if (!isEmpty) {
PreTraverse(biTree, 0, isEqual, visit);
}
return RET_OK;
}
// 中序遍历二叉树辅助函数
static void InTraverse(const SqBiTree biTree, int order, IsEqual isEqual, Status(*visit)(const TElemType *))
{
if (!isEqual(biTree + 2 * order + 1, &Nil)) {
InTraverse(biTree, 2 * order + 1, isEqual, visit);
}
visit(biTree + order);
if (!isEqual(biTree + 2 * order + 2, &Nil)) {
InTraverse(biTree, 2 * order + 2, isEqual, visit);
}
}
/*
前置条件：二叉树 biTree 存在
操作结果：中序遍历二叉树 biTree
*/
Status InOrderTraverse(const SqBiTree biTree, IsEqual isEqual, Status(*visit)(const TElemType *))
{
if (!isEqual || !visit) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
Boolean isEmpty;
IsBiTreeEmpty(biTree, isEqual, &isEmpty);
if (!isEmpty) {
InTraverse(biTree, 0, isEqual, visit);
}
return RET_OK;
}
// 后序遍历二叉树辅助函数
static void PostTraverse(const SqBiTree biTree, int order, IsEqual isEqual, Status(*visit)(const TElemType *))
{
if (!isEqual(biTree + 2 * order + 1, &Nil)) {
PostTraverse(biTree, 2 * order + 1, isEqual, visit);
}
if (!isEqual(biTree + 2 * order + 2, &Nil)) {
PostTraverse(biTree, 2 * order + 2, isEqual, visit);
}
visit(biTree + order);
}
/*
前置条件：二叉树 biTree 存在
操作结果：后序遍历二叉树 biTree
*/
Status PostOrderTraverse(const SqBiTree biTree, IsEqual isEqual, Status(*visit)(const TElemType *))
{
if (!isEqual || !visit) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
Boolean isEmpty;
IsBiTreeEmpty(biTree, isEqual, &isEmpty);
if (!isEmpty) {
PostTraverse(biTree, 0, isEqual, visit);
}
return RET_OK;
}
/*
前置条件：二叉树 biTree 存在
操作结果：层序遍历二叉树 biTree
*/
Status LevelOrderTraverse(const SqBiTree biTree, IsEqual isEqual, Status(*visit)(const TElemType *))
{
if (!isEqual || !visit) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
int lastNodeId = MAX_TREE_NODE_SIZE - 1;
while (isEqual(biTree + lastNodeId, &Nil)) {
--lastNodeId;
}
for (int i = 0; i <= lastNodeId; ++i) {
if (!isEqual(biTree + i, &Nil)) {
visit(biTree + i);
}
}
return RET_OK;
}
/*
前置条件：二叉树 biTree 存在
操作结果：逐层、按本层序号输出二叉树
*/
Status PrintBiTree(const SqBiTree biTree, IsEqual isEqual, Status(*visit)(const TElemType *))
{
if (!visit) {
ERR_RECORD(ERR_NULL_PTR);
return ERR_NULL_PTR;
}
Position pos = { 0 };
TElemType e;
Status ret;
for (int i = 1; i <= GetBiTreeDepth(biTree, isEqual); ++i) {
printf("第 %d 层: ", i);
for (int j = 1; j <= pow(2, i - 1); ++j) {
pos.level = i;
pos.order = j;
ret = GetValue(biTree, &pos, &e);
if (RET_OK == ret) {
printf("%d: ", j);
visit(&e);
}
}
printf("\n");
}
return RET_OK;
}
6) main.c
// 入口程序源文件
#include "sqBiTree.h"
static Status Visit(const TElemType *e)
{
printf("%c ", *e);
return RET_OK;
}
static Boolean IsEqualValue(const TElemType *e1, const TElemType *e2)
{
return (*e1 == *e2) ? TRUE : FALSE;
}
int main(void)
{
SqBiTree biTree;
InitBiTree(biTree);
CreateBiTree(biTree);
Boolean isEmpty;
IsBiTreeEmpty(biTree, IsEqualValue, &isEmpty);
printf("\n建立二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n", isEmpty, GetBiTreeDepth(biTree, IsEqualValue));
TElemType e;
Status ret = GetBiTreeRoot(biTree, IsEqualValue, &e);
if (RET_OK == ret) {
printf("\n二叉树的根为：%c\n", e);
} else {
printf("\n树空，无根\n");
}
printf("\n先序遍历二叉树:");
PreOrderTraverse(biTree, IsEqualValue, Visit);
printf("\n");
printf("\n中序遍历二叉树:");
InOrderTraverse(biTree, IsEqualValue, Visit);
printf("\n");
printf("\n后序遍历二叉树:");
PostOrderTraverse(biTree, IsEqualValue, Visit);
printf("\n");
printf("\n层序遍历二叉树:");
LevelOrderTraverse(biTree, IsEqualValue, Visit);
printf("\n");
printf("\n请输入待修改结点的层号 本层序号: ");
Position pos = { 0 };
scanf_s("%d%d", &pos.level, &pos.order);
GetValue(biTree, &pos, &e);
printf("\n待修改的结点值为：%c\n", e);
(void)getchar();
printf("\n请输入待修改的值：");
scanf_s("%c", &e, 1);
Assign(IsEqualValue, &pos, &e, biTree);
printf("\n修改后层序遍历二叉树：");
LevelOrderTraverse(biTree, IsEqualValue, Visit);
printf("\n");
TElemType parent;
ret = GetParentValue(biTree, IsEqualValue, &e, &parent);
if (RET_OK == ret) {
printf("\n结点 %c 的双亲为：", e);
printf("%c\n", parent);
}
TElemType leftChild;
ret = GetLeftChildValue(biTree, IsEqualValue, &e, &leftChild);
if (RET_OK == ret) {
printf("\n结点 %c 的左孩子为：", e);
printf("%c\n", leftChild);
}
TElemType rightChild;
ret = GetRightChildValue(biTree, IsEqualValue, &e, &rightChild);
if (RET_OK == ret) {
printf("\n结点 %c 的右孩子为：", e);
printf("%c\n", rightChild);
}
TElemType leftSibling;
ret = GetLeftSiblingValue(biTree, IsEqualValue, &e, &leftSibling);
if (RET_OK == ret) {
printf("\n结点 %c 的左兄弟为：", e);
printf("%c\n", leftSibling);
}
TElemType rightSibling;
ret = GetRightSiblingValue(biTree, IsEqualValue, &e, &rightSibling);
if (RET_OK == ret) {
printf("\n结点 %c 的右兄弟为：", e);
printf("%c\n", rightSibling);
}
(void)getchar();
SqBiTree insertTree;
InitBiTree(insertTree);
printf("\n建立右子树为空的树 insertTree:\n");
CreateBiTree(insertTree);
printf("\n将树 insertTree 插到树 biTree 中,请输入树 biTree 中树 insertTree 的双亲结点的值: ");
scanf_s("%c", &e, 1);
(void)getchar();
printf("\n请输入插入到该节点的左子树或右子树（0：左子树，1：右子树）：");
int side;
scanf_s("%d", &side);
(void)getchar();
InsertChildTree(side, &e, IsEqualValue, biTree, insertTree);
printf("\n插入后，层序遍历二叉树 biTree: ");
LevelOrderTraverse(biTree, IsEqualValue, Visit);
printf("\n");
printf("\n将输入待删除子树的根结点的位置: ");
scanf_s("%d%d", &pos.level, &pos.order);
(void)getchar();
printf("\n请输入删除该节点的左子树或右子树（0：左子树，1：右子树）：");
scanf_s("%d", &side);
(void)getchar();
DeleteChildTree(side, IsEqualValue, &pos, biTree);
printf("\n删除后，层序遍历二叉树 biTree: ");
LevelOrderTraverse(biTree, IsEqualValue, Visit);
printf("\n");
printf("\n详细遍历二叉树（层序）：");
PrintBiTree(biTree, IsEqualValue, Visit);
printf("\n");
ClearBiTree(biTree);
IsBiTreeEmpty(biTree, IsEqualValue, &isEmpty);
printf("\n清空二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n", isEmpty, GetBiTreeDepth(biTree, IsEqualValue));
printf("\n");
ret = GetBiTreeRoot(biTree, IsEqualValue, &e);
if (RET_OK == ret) {
printf("\n二叉树的根为：%c\n", e);
} else {
printf("\n树空，无根\n");
}
return 0;
}
3. 输出结果（DEBUG OFF)
1）测试输入
ABCDEF G HI J
3 3
X
ab cd
D
1
3 1
1
2) 测试输出
![【BUUCTF】[RoarCTF 2019]Easy Java1](https://img-blog.csdnimg.cn/direct/02a6810f75824aab98c77daefd584fe5.png)
