二叉树实现及其基本原理

话不多说,都在图上.

再上代码

typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a,int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树前序遍历 (非递归)
void BinaryTreePrevOrderno(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树中序遍历(非递归)
void BinaryTreeInOrderno(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 二叉树后序遍历(非递归)
void BinaryTreePostOrderno(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);
BTNode* BinaryTreeCreate(BTDataType* str, int* std) {
	if (str[*std] != '#') {
		BTNode* root = (BTNode*)malloc(sizeof(BTNode));
		root->_data = str[*std];
		(*std)++;
		root->_left = BinaryTreeCreate(str, std);
		(*std)++;
		root->_right = BinaryTreeCreate(str, std);
		return root;

	}
	else {
		return NULL;
	}
}
void BinaryTreeDestory(BTNode** root) {
	if (*root) {
		BinaryTreeDestory(&(*root)->_left);
		BinaryTreeDestory(&(*root)->_right);
		free(*root);
		*root = NULL;
	}
}
void BTsize(BTNode* root, int* size) {
	if (root) {
		BTsize(root->_left, size);
		BTsize(root->_right, size);
		(*size)++;
	}
}
int BinaryTreeSize(BTNode* root) {
	int size = 0;
	BTsize(root, &size);
	return size;
}
void BTLsize(BTNode* root, int* size) {
	if (root) {
		BTLsize(root->_left,size);
		BTLsize(root->_right,size);
		if (root->_left == NULL && root->_right == NULL) {
			(*size)++;
		}
	}
}
int BinaryTreeLeafSize(BTNode* root) {
	int size = 0;
	BTLsize(root, &size);
	return size;
}
int BinaryTreeLevelKSize(BTNode* root, int k) {
	if (root && k != 1) {
		k--;
		return BinaryTreeLevelKSize(root->_left, k) +
			BinaryTreeLevelKSize(root->_right, k);
	}
	else if (root && k == 1) {
		return 1;
	}
	else 
		return 0;
	
}
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {
	if (root == NULL)
		return NULL;
	if (root->_data == x)
		return root;
	BTNode* res = BinaryTreeFind(root->_left, x);
	if (res)
		return res;
	res = BinaryTreeFind(root->_right, x);
	return res;
}
void BinaryTreePrevOrder(BTNode* root) {
	if (root) {
		printf("%c ", root->_data);
		BinaryTreePrevOrder(root->_left);
		BinaryTreePrevOrder(root->_right);
	}
}
void BinaryTreeInOrder(BTNode* root) {
	if (root) {
		BinaryTreePrevOrder(root->_left);
		printf("%c ", root->_data);
		BinaryTreePrevOrder(root->_right);
	}
}
void BinaryTreePostOrder(BTNode* root) {
	if (root) {
		BinaryTreePrevOrder(root->_left);
		BinaryTreePrevOrder(root->_right);
		printf("%c ", root->_data);
	}
}
void BinaryTreeLevelOrder(BTNode* root) {
	//建队列
	Queue q;
	//初始化队列
	QueueInit(&q);
	if(root)
		QueuePush(&q, root);
		//root入队
	while (QueueEmpty(&q) == 0) {
		//获取队头元素
		BTNode* tmp = QueueFront(&q);
		//出队列
		QueuePop(&q);
		printf("%c ", tmp->_data);
		//左右子树入队列
		if (tmp->_left) {
			QueuePush(&q, tmp->_left);
		}
		if (tmp->_right) {
			QueuePush(&q, tmp->_right);
		}
	}
}
int BinaryTreeComplete(BTNode* root) {
	//建队列
	Queue q;
	//初始化队列
	QueueInit(&q);
	//root入队
	QueuePush(&q, root);
	while (QueueEmpty(&q) == 0) {
		//获取队头元素
		BTNode* tmp = QueueFront(&q);
		//出队列
		QueuePop(&q);
		if (tmp) {
			//左右子树入队列
			QueuePush(&q, tmp->_left);
			QueuePush(&q, tmp->_right);
		}
		else {
			break;
		}
	}
	//判断队列是否为空
	while (QueueEmpty(&q) == 0) {
		//获取队头元素
		BTNode* res = QueueFront(&q);
		//出队列
		QueuePop(&q);
		if (res)
			return 0;
	}
	return 1;
}
void BinaryTreePrevOrderno(BTNode* root) {
	//建栈
	Stack s;
	//初始化栈
	StackInit(&s);
	BTNode* cur = root;
	//判断cur是否为空或栈是否为空
	while (cur || StackEmpty(&s) == 0) {
		while (cur) {
			printf("%c ", cur->_data);
			//cur入栈
			StackPush(&s,cur);
			cur = cur->_left;
		}
		//获取栈顶元素
		BTNode* tmp = StackTop(&s);
		//出栈
		StackPop(&s);
		cur = tmp->_right;
	}
}
void BinaryTreeInOrderno(BTNode* root) {
	//建栈
	Stack s;
	//初始化栈
	StackInit(&s);
	BTNode* cur = root;
	//判断cur是否为空或栈是否为空
	while (cur || StackEmpty(&s) == 0) {
		while (cur) {
			//cur入栈
			StackPush(&s, cur);
			cur = cur->_left;
		}
		//获取栈顶元素
		BTNode* tmp = StackTop(&s);
		//出栈
		StackPop(&s);
		printf("%c ", tmp->_data);
		cur = tmp->_right;
	}
}
void BinaryTreePostOrderno(BTNode* root) {
	//建栈
	Stack s;
	//初始化栈
	StackInit(&s);
	BTNode* cur = root;
	BTNode* prev = NULL;
	//判断cur是否为空或栈是否为空
	while (cur || StackEmpty(&s) == 0) {
		while (cur) {
			//cur入栈
			StackPush(&s, cur);
			cur = cur->_left;
		}
		//获取栈顶元素
		BTNode* tmp = StackTop(&s);
		if (tmp->_right == NULL || tmp->_right == prev) {
			printf("%c ", tmp->_data);
			//出栈
			StackPop(&s);
			prev = tmp;
		}
		else {
			cur = tmp->_right;
		}	
	}
}

代码中涉及到的用字符串建树问题,具体请参考牛客网二叉树遍历
二叉树遍历过程中又涉及到队列和栈的调用,为方便参考,已在代码中标记出