二叉树详细讲解（2/2）

4.  实现链式结构二叉树

⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址，其结构如下：

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	struct BinTreeNode* left;//指向左孩子
	struct BinTreeNode* right;//指向右孩子
	BTDataType val;//当前结点值域
}BTNode;

二叉树的创建方式比较复杂，为了更好的步入二叉树内容中，我们先手动创建一棵链式二叉树。

BTNode* BuyBTNode(int val)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->val = val;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}
BTNode* CreateTree()
{
	BTNode* n1 = BuyBTNode(1);
	BTNode* n1 = BuyBTNode(2);
	BTNode* n1 = BuyBTNode(3);
	BTNode* n1 = BuyBTNode(4);
	BTNode* n1 = BuyBTNode(5);
	BTNode* n1 = BuyBTNode(6);
	BTNode* n1 = BuyBTNode(7);


	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;
	n5->left = n7;
	return n1;
}

回顾⼆叉树的概念，⼆叉树分为空树和⾮空⼆叉树，⾮空⼆叉树由根结点、根结点的左⼦树、根结点的右⼦树组成的。

根结点的左⼦树和右⼦树分别⼜是由⼦树结点、⼦树结点的左⼦树、⼦树结点的右⼦树组成的，因此⼆叉树定义是递归式的,后序链式⼆叉树的操作中基本都是按照该概念实现的

4.1 前中后遍历

二叉树的操作理不理树的遍历，我们先来看看二叉树的遍历有哪些方式

4.1.1 遍历规则

按照规则，⼆叉树的遍历有：前序/中序/后序的递归结构遍历：
1）前序遍历(Preorder Traversal亦称先序遍历)：访问根结点的操作发⽣在遍历其左右⼦树之前访问顺序为：根结点、左⼦树、右⼦树
2）中序遍历(Inorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之中（间）访问顺序为：左⼦树、根结点、右⼦树
3）后序遍历(Postorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之后访问顺序为：左⼦树、右⼦树、根结点

4.1.2 代码实现

//}
//前序排列
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N");
		return ;
	}
	printf("%d", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}
//中序排列
void InOrder(BTNode* root)
{
	if (root = NULL)
	{
		printf("N");
		return;
	}
	InOrder(root->left);
	printf("%d", rooy->val);
	InOrder(root->right);
}
//后续排列
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N");
		return;
	}
	InOrder(root->left);
	InOrder(root->right);
	printf("%f", root->val);
}

4.2  判断是否为完全二叉树

int BinaryTreeComplete(BTNode* root)
{
	Queue qu;
	BTNode * cur;
	int tag = 0;

	QueueInit(&qu);

	QueuePush(&qu, root);

	while (!QueueIsEmpty(&qu))
	{
		cur = QueueTop(&qu);

		putchar(cur->_data);

		if (cur->_right && !cur->_left)
		{
			return 0;
		}

		if (tag && (cur->_right || cur->_left))
		{
			return 0;
		}

		if (cur->_left)
		{
			QueuePush(&qu, cur->_left);
		}

		if (cur->_right)
		{
			QueuePush(&qu, cur->_right);
		}
		else
		{
			tag = 1;
		}

		QueuePop(&qu);
	}

	QueueDestory(&qu);
	return 1;
}