本文内容
- 环境
- 基本结构 basic.h
- 顺序二叉树 sqbitreee.h 文件
- 顺序二叉树 sqbitreee.c 文件
- 测试
本文主要是创建一个棵顺序二叉树，毕竟要是想测试什么算法的话，总得有一棵才行。
环境
- codeblock 12.11
- Windows 7 旗舰版 64位
基本结构 basic.h
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;
typedef int TElementType;
顺序二叉树 sqbitree.h 文件
#ifndef SQBITREE_H_INCLUDED
#define SQBITREE_H_INCLUDED
#include "basic.h"
/* 顺序二叉树只适合完全二叉树 */
/* 顺序二叉树的最大结点数 */
#define MAX_TREE_SIZE 100
/* 0号单元存储根结点 */
typedef TElementType SqBiTree[MAX_TREE_SIZE];
/* 初始化顺序二叉树 */
Status InitSqBiTree(SqBiTree T);
/* 创建顺序二叉树 */
Status CreateSqBiTree(SqBiTree T);
/* 置空顺序二叉树 */
Status IsSqBiTreeEmpty(SqBiTree T);
/* 顺序二叉树深度 */
int SqBiTreeDepth(SqBiTree T);
/* 顺序二叉树根节点 */
Status SqBiTreeRoot(SqBiTree T, TElementType *e);
/* 按数组输出顺序二叉树 */
void PrintSeq(SqBiTree T);
#endif
顺序二叉树 sqbitree.c 文件
#include "basic.h"
#include "sqbitree.h"
#include/* EOF(=^Z或F6),NULL */
#include/* floor(),ceil(),abs() */
#include
/* 初始化
构造空顺序二叉树。T 是固定大小数组，不需要 &
初值为 -1
*/
Status InitSqBiTree(SqBiTree T)
{ int i;
for(i=0; i
return OK;
}
/* 创建
按层序次序输入二叉树中结点的值(字符型或整型), 构造顺序存储的二叉树T
-1 表示空节点
-2 表示创建结束
*/
Status CreateSqBiTree(SqBiTree T)
{ int i=0;
TElementType e;
printf("请按层序输入结点的值(正整型)，结点数≤%d:\n", MAX_TREE_SIZE); while(1)
{ scanf("%d", &e); if(e==-2) break;
T[i]=e;
if( i!=0 && T[(i+1)/2 - 1]==-1 && T[i]!=-1 ) /* 此结点(不空)无双亲且不是根 */
{ printf("错误，无双亲的非根结点 %d\n",T[i]); exit(ERROR);
}
i++;
}
return OK;
}
/* 置空
初始条件: 二叉树T存在
操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */
Status IsSqBiTreeEmpty(SqBiTree T)
{ if(T[0]==-1) /* 根结点为空,则树空 */
return TRUE;
else
return FALSE;
}
/* 深度
初始条件: 二叉树T存在。
操作结果: 返回T的深度 */
int SqBiTreeDepth(SqBiTree T)
{ int i;
for(i=MAX_TREE_SIZE-1; i>=0; i--) /* 找到最后一个结点 */
if(T[i]!=-1) break;
i++;
return floor(log2(i))+1;
}
/* 根节点值
初始条件: 二叉树T存在
操作结果: 当T不空,用e返回T的根,返回OK;否则返回ERROR,e无定义 */
Status SqBiTreeRoot(SqBiTree T, TElementType *e)
{ if(IsSqBiTreeEmpty(T)) return ERROR;
else
{ *e=T[0];
return OK;
}
}
void PrintSeq(SqBiTree T)
{ int i;
for(i=0; i
printf("%d ", T[i]); }
测试
Status i;
TElementType e;
SqBiTree T;
InitSqBiTree(T);
CreateSqBiTree(T);
printf("\n建立二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n", IsSqBiTreeEmpty(T), SqBiTreeDepth(T)); i = SqBiTreeRoot(T,&e);
if(i)
printf("\n二叉树的根为：%d\n", e); else
printf("树空，无根\n"); PrintSeq(T);