#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string>

enum Status
{
	OK,
	ERROR
};

/*顺序二叉树说明：书上没有调整操作，故而删除了就是删除了*/
typedef char TreeElemType;
typedef struct BinaryTree {
	TreeElemType* data;
	int lastIndex;
}BinaryTree, * BinaryTreeLink;

/*初始化*/
Status Init_BinaryTree(BinaryTree& BT,int length) {
	BT.lastIndex = 0;
	BT.data = (TreeElemType*)malloc(length);
	memset(BT.data, '\0', length);
	if (BT.data == NULL) {
		return ERROR;
	}
	return OK;
}


/*插入*/
Status Insert_BinaryTree(BinaryTree& BT,TreeElemType data,int i = 1) {
	if (i >= 400) {
		BT.data = (TreeElemType*)realloc(BT.data, 1000);//到要插入时，空间不够插入就多分配单元，放心，不会覆盖原有元素的
	}
	if (BT.data[i] == '\0') {
		BT.data[i] = data;
		BT.lastIndex++;
		return OK;
	}
	if (BT.data[i] == data) {
		printf("采用顺序存储结构的二叉排序树无法在左右子树都存在的情况下插入重复元素，请谅解。\n");
		return ERROR;
	}

	if (BT.data[i] > data) {
		return Insert_BinaryTree(BT, data, i * 2);
	}
	if (BT.data[i] < data) {
		return Insert_BinaryTree(BT, data, i * 2 + 1);
	}
}

/*删除--删除之后还得做调整操作--但是就一棵普通二叉树， 我不打算做这么多功能，就算了，日后用链表实现。*/
Status Delete_BinaryTree(BinaryTree& BT,TreeElemType data,int i = 1) {
	if (i > BT.lastIndex || BT.data[i] == '\0') {
		printf("该二叉树中没有这个元素，你删除啥呢？\n");
		return ERROR;
	}
	if (BT.data[i] == data) {
		BT.data[i] = '\0';
		BT.lastIndex--;
		//删除成功后还得做调整操作，否则被删除结点的子孙将全部无法显示。这里应该调用调整二叉排序树的函数。
		return OK;
	}

	if (BT.data[i] > data) {
		return Delete_BinaryTree(BT, data, i * 2);
	}
	if (BT.data[i] < data) {
		return Delete_BinaryTree(BT, data, i * 2 + 1);
	}
}


/*查找--顺序结构查找代码写起来真方便--不代表复杂度低*/
Status Find_BinaryTree(BinaryTree BT, TreeElemType data) {
	if (BT.lastIndex == 0) {
		printf("空树。\n");//因为也可能是删除之后自动调用这个函数，故而不打印“请勿做删除操作”的字样。
		return ERROR;
	}
	for (int i = 0; i < BT.lastIndex; i++) {
		if (BT.data[i] == data) {
			printf("已找到，%c存在于此二叉树中。\n", BT.data[i]);
			return OK;
		}
	}
	printf("没找到，该元素不存在于此二叉树中。\n");
	return ERROR;
}

/*清空*/
void Clear_BinaryTree(BinaryTree& BT) {
	for (int i = 0; i < (1 << BT.lastIndex); i++) {
		BT.data[i] = '\0';
	}
	BT.lastIndex = 0;
	printf("已清空。\n");
}


/**
非递归遍历图形化显示
图形化二叉树乃至多叉树--不仅仅是完全二叉树
BUG：运行普通窗口下显示超过14个元素会错位； 全屏不得超过17个--即不得超过四行
*/
void ArrayShow_BinaryTree(BinaryTree BT) {
	if (BT.data[1] == '\0') {
		printf("空树。\n");
		return;
	}
	int i = 1, j;//j表示层数，i表示第几个元素 
	int k = 1;//k表示显示/\的个数，与循环之前的i同步
	int depth = ceil(log(BT.lastIndex) / log(2) + 1)+1;//计算log2^N + 2--打印行数只求多不求少，如果是空数据大不了打印空字符,故而使用ceil函数向上取整 

	if (depth > 4) {
		printf("元素过多，屏幕不足以输入全部字符（包括空格），图形化会错位，故而不予展示。温馨提示：超过4行就不行。\n");
		return;
	}
	printf("+++++++++++++++二叉树的全部元素如下：+++++++++++++++\n");
	for (j = 0; j < depth; j++) {
		int w = 1 << (depth - j + 1);//决定每一层的元素的前置空格数--换句话说，就是每一层的前置空格数都不一样,这层元素的个数越少，前置空格就越多 
		int tmp = i;
		for (; i < (1 << j) + tmp; i++) {//tmp保留的是上一次传下来的i,tmp存在是因为这一层要打印1<<j个元素，而不是打印到1<<j号元素。 
			printf("%*c%*c", w, BT.data[i], w, ' ');//%5c表示这个字符要占五个格子，默认数据在右边，%-5c是在左边。%*c是动态占格。 
		}
		printf("\n");
		for (; k < (1 << j) + tmp; k++) {
			if (BT.data[k] != '\0') {
				printf("%*c", w, '/');
				printf("\\%*c", w - 1, ' ');//这里单独一个\会被认为是转义字符\n少了n之类，所以要\\ 
			}
			else {
				printf("%*c %*c", w, ' ',w-1,' ');
			}
		}
		printf("\n");
	}
	printf("\n++++++++++++++++++++++++++++++++++++++++++\n");
}