C语言递归实现顺序二叉树
ADT_BinaryTree.h
/*-----------------------------------------Copyright (c) 2010-2011 Zidane LiUsage of this program is free for non-commercial use.-----------------------------------------*//*二叉树的顺序实现仅适用于完全二叉树*/#ifndef BINARY_TREE_SQ_H#define BINARY_TREE_SQ_H#include <stdlib.h>#include <math.h>#include "ADT_BinaryTree.h"#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0;#define INFEASIBLE -1typedef int Status;Status InitBiTree_Sq(SqBiTree& T){T.elem = (TElemType*)malloc(MAX_TREE_SIZE * sizeof(TElemType));//将所有未被初始化的结点赋值为' '，为了在输出时方便（如果结点为未定义，则会停止输出剩下的元素）for (int i = 0; i < MAX_TREE_SIZE; i++){T.elem[i] = SPACE;}T.len = 0;return OK;}Status DeleteTree(SqBiTree& T, int e){if (T.elem[2 * e + 1] != SPACE){DeleteTree(T, 2 * e + 1);}if (T.elem[2 * e + 2] != SPACE){DeleteTree(T, 2 * e + 2);}T.elem[e] = 0;return OK;}//A的子树（从i开始）移动到B的子树（从j开始）void Move(SqBiTree A, int p, SqBiTree& B, int q){B.elem[q] = A.elem[p];A.elem[p] = SPACE;if (A.elem[2 * p + 1] != SPACE){Move(A, (2 * p + 1), B, (2 * q + 1));}if (A.elem[2 * p + 2] != SPACE){Move(A, (2 * p + 2), B, (2 * q + 2));}}Status InsertChild(SqBiTree& T, int p, int LR, SqBiTree C){T.len += C.len;//如果p所指结点存在子结点，利用move递归移动p的子结点到将要插入的树C的右子树if (T.elem[2 * p + 1 + LR] != SPACE){Move(T, (2 * p + 1 + LR), C, 2);}Move(C, 0, T, (2 * p + 1 + LR));return OK;}Status DeleteChild(SqBiTree T, int p, int LR){DeleteTree(T, (2 * p + 1 + LR));return OK;}Status ClearBiTree(SqBiTree& T){DeleteTree(T, 0);T.len = 0;return OK;}Status DestoryBiTree_Sq(SqBiTree& T){ClearBiTree(T);free(T.elem);return OK;}Status CreateBiTree(SqBiTree& T){//自定义读入格式，只识别空格、a-z、A-Z和0到9scanf("%[ a-zA-Z0-9]", T.elem);T.len = strlen(T.elem);//清空缓冲区fflush(stdin);return OK;}Status BiTreeEmpty(SqBiTree T){return T.len == 0;}int BiTreeDepth(SqBiTree T){return (int)floor(log(float(T.len)) / log(2.0f)) + 1;}TElemType Root(SqBiTree T){return T.elem[0];}TElemType Value(SqBiTree T, int e){return T.elem[e];}int LocateElemType(SqBiTree T, TElemType e){for (int i = 0; i < T.len; i++){if (T.elem[i] == e){return i;}}return -1;}Status Assign(SqBiTree T, TElemType e, TElemType value){int i = LocateElemType(T, e);if (i == -1){return ERROR;}T.elem[i] = value;return OK;}TElemType Parent(SqBiTree T, TElemType e){int i = LocateElemType(T, e);return T.elem[(int)floor((float)i / 2)];}TElemType LeftChild(SqBiTree T, TElemType e){int i = LocateElemType(T, e);return T.elem[2 * i + 1];}TElemType RightChild(SqBiTree T, TElemType e){int i = LocateElemType(T, e);return T.elem[2 * i + 2];}TElemType LeftSibling(SqBiTree T, TElemType e){int i = LocateElemType(T, e);int a = 1;for (int j = 0; j < BiTreeDepth(T); j++){if (a - 1 == i){return 0;}a *= 2;}return T.elem[i - 1];}TElemType RightSibling(SqBiTree T, TElemType e){int i = LocateElemType(T, e);int a = 1;for (int j = 0; j < BiTreeDepth(T); j++){if (a - 1 == i){return 0;}a *= 2;}return T.elem[i + 1];}Status PreOrderTraverse(SqBiTree T, int e){visit(T, e);if (T.elem[2 * e + 1] >= 33){PreOrderTraverse(T, (2 * e + 1));}if (T.elem[2 * e + 2] >= 33){PreOrderTraverse(T, (2 * e + 2));}return OK;}Status InOrderTraverse(SqBiTree T, int e){if (T.elem[2 * e + 1] != SPACE){InOrderTraverse(T, (2 * e + 1));}visit(T, e);if (T.elem[2 * e + 2] != SPACE){InOrderTraverse(T, (2 * e + 2));}return OK;}Status PostOrderTraverse(SqBiTree T, int e){if (T.elem[2 * e + 1] != SPACE){PostOrderTraverse(T, (2 * e + 1));}if (T.elem[2 * e + 2] != SPACE){PostOrderTraverse(T, (2 * e + 2));}visit(T, e);return OK;}Status LevelOrderTraverse(SqBiTree T){printf("%s", T.elem);return OK;}#endif
