二叉树的遍历

二叉树：

二叉树是一种非线性的数据结构，其基本单元是数据+指向左子树的指针+指向右子树的指针

typedef int TreeDataType;
typedef struct BTNode
{
	TreeDataType data;
	struct BTNode* pleft;
	struct BTNode* pright;
}BTNode;

在二叉树中，特殊的二叉树有满二叉树，完全二叉树。

满二叉树：每一层的结点个数都是满的。满二叉树的高度为h,则结点个数为.

完全二叉树：每一层的结点个数是满的，或者是从左向右依次变满的

例如：

满二叉树是特殊的完全二叉树。

结点的度：指的是结点的孩子数量，在二叉树中，结点的度为0,1,2

二叉树的高度：指二叉树有多少层，如果只有一个根结点，默认是1层

祖先结点：一个结点的祖先结点是指该结点的父，父的父，……直到根结点，都是该节点的祖先结点

二叉树有一个比较重要的性质：度为0的结点个数始终要比度为2的结点个数多一个。

二叉树的前中后序遍历：二叉树的前中后序遍历相当于深度优先搜索

前序遍历：指的是先遍历根，在遍历左子树，在遍历右子树，然后在对左子树和右子树进行相同的操作

void PrevOrder(BTNode* root)
{
	if (root == NULL)
		return;
	printf("%d ", root->data);
	PrevOrder(root->pleft);
	PrevOrder(root->pright);
}

中序遍历：指的是先遍历左子树，在遍历根，在遍历右子树， 然后在对左子树和右子树进行相同的操作

void Inorder(BTNode* root)
{
	if(root == NULL)
		return;
	Inorder(root->pleft);
	printf("%d ", root->data);
	Inorder(root->pright);
}

后序遍历：指的是先遍历左子树，在遍历右子树，在遍历根， 然后在对左子树和右子树进行相同的操作

void Postorder(BTNode* root)
{
	if (root == NULL)
		return;
	Postorder(root->pleft);
	Postorder(root->pright);
	printf("%d ", root->data);
}

除此之外，二叉树还可以进行层序遍历，即一层一层的进行遍历，二叉树的层序遍历需要使用到队列，其基本思路是：先让根节点入队列，保存队列队头的元素，然后出队列队头的元素，在入保存的那个元素的左右节点。具体过程是：

 以此类推，既可以完成二叉树的层序遍历。二叉树的层序遍历相当于广度优先搜索

typedef  BTNode* QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType x;
}QNode;
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
bool QueueIsEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
void QueuePop(Queue* pq)
{
	assert(pq&&!QueueIsEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
void QueuePush(Queue* pq,QDataType data)
{
	assert(pq);
	QNode* tmp = (QNode*)malloc(sizeof(QNode));
	assert(tmp);
	tmp->next = NULL;
	tmp->x = data;
	if (QueueIsEmpty(pq))
	{
		pq->head = pq->tail = tmp;
	}
	else
	{
		pq->tail->next = tmp;
		pq->tail = tmp;
	}
}
BTNode* QueueHead(Queue* pq)
{
	assert(QueueIsEmpty(pq));
	return pq->head->x;
}
//二叉树的层序遍历
void LevelOrderTraversal(BTNode* root)
{
	if (root == NULL)
		return;
	Queue q;
	QueueInit(&q);
	//将根节点入队
	QueuePush(&q, root);
	while (!QueueIsEmpty(&q))//第一次根节点已经入队，队列一定有一个元素
	{
		BTNode* tmp = QueueHead(&q);//获取队头元素,保存在tmp中
		QueuePop(&q);//出队
		if (tmp != NULL)//队头的元素不是NULL,则让其左右节点入队
		{
			printf("%d ", tmp->data);
			QueuePush(&q, tmp->pleft);
			QueuePush(&q, tmp->pright);
		}
		else//队头元素是空指针的话，什么都不做，让其出队就行了
		{
			;
		}
	}
}

二叉树中还有一个比较经典的问题：判断一棵树是否为完全二叉树。可以采用层序遍历的方法进行解决，思路是将二叉树从上往下一层一层的进行遍历，当遍历到了NULL，停止遍历，然后判断此时队列中的元素是否全部为NULL.如果是，则树为完全二叉树，否则就不是完全二叉树。

bool IsCmpleteTree(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueIsEmpty(&q))
	{
		BTNode* tmp = QueueHead(&q);
		QueuePop(&q);
		if (tmp == NULL)
		{
			break;
		}
		else
		{
			QueuePush(&q, tmp->pleft);
			QueuePush(&q, tmp->pright);
		}
	}
	//下面就判断队列中剩下的是否都为NULL
	while (!QueueIsEmpty(&q))
	{
		BTNode* tmp = QueueHead(&q);
		QueuePop(&q);
		if (tmp != NULL)
		{
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true;
}