mirror of
https://github.com/kangjianwei/Data-Structure.git
synced 2026-02-08 17:51:45 +08:00
211 lines
4.6 KiB
C
211 lines
4.6 KiB
C
/*==================
|
||
* 二叉树顺序存储结构
|
||
===================*/
|
||
|
||
#ifndef SQBITREE_H
|
||
#define SQBITREE_H
|
||
|
||
#include <stdio.h>
|
||
#include <stdlib.h> // 提供 malloc、free 原型
|
||
#include <string.h> // 提供 memset、strcmp 原型
|
||
#include <math.h> // 提供 pow 原型
|
||
#include "Status.h" //**▲01 绪论**//
|
||
|
||
/* 宏定义 */
|
||
#define MAX_TREE_SIZE 1024 // 二叉树的最大结点数
|
||
|
||
/* 二叉树元素类型定义，这里假设其元素类型为char */
|
||
typedef char TElemType;
|
||
|
||
/*
|
||
* 二叉树类型定义，0号单元存储根结点。
|
||
*
|
||
*【注】
|
||
* 在二叉树的顺序结构中，其元素是按照完全顺序二叉树的层序序列排列的。
|
||
*/
|
||
typedef TElemType SqBiTree[MAX_TREE_SIZE];
|
||
|
||
|
||
/*
|
||
* 初始化
|
||
*
|
||
* 构造空二叉树。
|
||
*/
|
||
Status InitBiTree(SqBiTree T);
|
||
|
||
/*
|
||
* 销毁
|
||
*
|
||
* 释放二叉树所占内存。
|
||
*
|
||
*【注】
|
||
* 二叉树的顺序存储结构无法销毁。
|
||
*/
|
||
Status DestroyBiTree(SqBiTree T);
|
||
|
||
/*
|
||
* 置空
|
||
*
|
||
* 清理二叉树中的数据，使其成为空树。
|
||
*/
|
||
Status ClearBiTree(SqBiTree T);
|
||
|
||
/*
|
||
* 创建
|
||
*
|
||
* 按照预设的定义来创建二叉树。
|
||
* 这里约定使用【先序序列】来创建二叉树。
|
||
*
|
||
*
|
||
*【备注】
|
||
*
|
||
* 教材中默认从控制台读取数据。
|
||
* 这里为了方便测试，避免每次运行都手动输入数据，
|
||
* 因而允许选择从预设的文件path中读取测试数据。
|
||
*
|
||
* 如果需要从控制台读取数据，则path为NULL或者为空串，
|
||
* 如果需要从文件中读取数据，则需要在path中填写文件名信息。
|
||
*/
|
||
Status CreateBiTree(SqBiTree T, char* path);
|
||
|
||
/*
|
||
* 判空
|
||
*
|
||
* 判断二叉树是否为空树。
|
||
*/
|
||
Status BiTreeEmpty(SqBiTree T);
|
||
|
||
/*
|
||
* 树深
|
||
*
|
||
* 返回二叉树的深度（层数）。
|
||
*/
|
||
int BiTreeDepth(SqBiTree T);
|
||
|
||
/*
|
||
* 取值
|
||
*
|
||
* 返回二叉树中指定结点的值。
|
||
*/
|
||
TElemType Value(SqBiTree T, TElemType e);
|
||
|
||
/*
|
||
* 赋值
|
||
*
|
||
* 为二叉树指定的结点赋值。
|
||
*/
|
||
Status Assign(SqBiTree T, TElemType e, TElemType value);
|
||
|
||
/*
|
||
* 根
|
||
*
|
||
* 返回二叉树的根结点。
|
||
*/
|
||
TElemType Root(SqBiTree T);
|
||
|
||
/*
|
||
* 双亲
|
||
*
|
||
* 返回二叉树中结点e的双亲结点。
|
||
*/
|
||
TElemType Parent(SqBiTree T, TElemType e);
|
||
|
||
/*
|
||
* 左孩子
|
||
*
|
||
* 返回二叉树中结点e的左孩子结点。
|
||
*/
|
||
TElemType LeftChild(SqBiTree T, TElemType e);
|
||
|
||
/*
|
||
* 右孩子
|
||
*
|
||
* 返回二叉树中结点e的右孩子结点。
|
||
*/
|
||
TElemType RightChild(SqBiTree T, TElemType e);
|
||
|
||
/*
|
||
* 左兄弟
|
||
*
|
||
* 返回二叉树中结点e的左兄弟结点。
|
||
*/
|
||
TElemType LeftSibling(SqBiTree T, TElemType e);
|
||
|
||
/*
|
||
* 右兄弟
|
||
*
|
||
* 返回二叉树中结点e的右兄弟结点。
|
||
*/
|
||
TElemType RightSibling(SqBiTree T, TElemType e);
|
||
|
||
/*
|
||
* 插入
|
||
*
|
||
* 已知c为与T不相交的非空二叉树，且c的右子树为空，
|
||
* 根据LR的取值(0或1)，将c插入为T中结点p的左子树/右子树，
|
||
* 并且，将p结点原有的左子树/右子树嫁接为二叉树c的右子树。
|
||
*/
|
||
Status InsertChild(SqBiTree T, TElemType p, int LR, SqBiTree c);
|
||
|
||
/*
|
||
* 删除
|
||
*
|
||
* 根据LR的取值(0或1)，删除结点p的左子树/右子树。
|
||
*/
|
||
Status DeleteChild(SqBiTree T, TElemType p, int LR);
|
||
|
||
/*
|
||
* 先序遍历
|
||
*/
|
||
Status PreOrderTraverse(SqBiTree T, Status(Visit)(TElemType));
|
||
|
||
/*
|
||
* 中序遍历
|
||
*/
|
||
Status InOrderTraverse(SqBiTree T, Status(Visit)(TElemType));
|
||
|
||
/*
|
||
* 后序遍历
|
||
*/
|
||
Status PostOrderTraverse(SqBiTree T, Status(Visit)(TElemType));
|
||
|
||
/*
|
||
* 层序遍历
|
||
*/
|
||
Status LevelOrderTraverse(SqBiTree T, Status(Visit)(TElemType));
|
||
|
||
|
||
/*━━━━━━━━━━━━━━━━━━━━━━ 仅限内部使用的函数 ━━━━━━━━━━━━━━━━━━━━━━*/
|
||
|
||
// 创建二叉树的内部函数
|
||
static void CreateTree(SqBiTree T, int i, FILE* fp);
|
||
|
||
// 求二叉树深度的内部函数
|
||
static int TreeDepth(SqBiTree T, int i);
|
||
|
||
// 返回二叉树结点e的索引号，i是结点p的索引号
|
||
static int EIndex(SqBiTree T, TElemType e, int i);
|
||
|
||
// 摘下二叉树T中的子树i，将其插入为二叉树R的子树j
|
||
static void Transfer(SqBiTree T, int i, SqBiTree R, int j);
|
||
|
||
// 删除二叉树T中的子树i
|
||
static void Delete(SqBiTree T, int i);
|
||
|
||
// 先序遍历的内部实现
|
||
static Status PreTraverse(SqBiTree T, Status(Visit)(TElemType), int i);
|
||
|
||
// 中序遍历的内部实现
|
||
static Status InTraverse(SqBiTree T, Status(Visit)(TElemType), int i);
|
||
|
||
// 后序遍历的内部实现
|
||
static Status PostTraverse(SqBiTree T, Status(Visit)(TElemType), int i);
|
||
|
||
|
||
/*━━━━━━━━━━━━━━━━━━━━━━ 图形化输出 ━━━━━━━━━━━━━━━━━━━━━━*/
|
||
|
||
// 以图形化形式输出当前结构，仅限内部测试使用
|
||
void PrintTree(SqBiTree T);
|
||
|
||
#endif
|