二叉树的构建

为了实现二叉树的遍历，我们要先构建一个二叉树，这里就先简单构建一个。

结点类型的定义

既然是链式二叉树，那必须得有自己的结点类型，以下是链式二叉树结点类型的定义

typedef char BTDataType;
typedef struct BinaryNode
{BTDataType x;struct BinaryNode* left;struct BinaryNode* right;
}BT;

构建二叉树之间的关系

BT* BuyNode(BTDataType x)
{BT* new = (BT*)malloc(sizeof(BT));if (new == NULL){printf("malloc failed\n");exit(-1);}new->x = x;new->left = NULL;new->right = NULL;return new;
}void BinaryCreat()
{BT* n1 = BuyNode('A');BT* n2 = BuyNode('B');BT* n3 = BuyNode('C');BT* n4 = BuyNode('D');BT* n5 = BuyNode('E');BT* n6 = BuyNode('F');n1->left = n2;n1->right = n3;n2->left = n4;n3->left = n5;n3->right = n6;
}

构建完之后的二叉树是这个样子的：

---

深度优先遍历

二叉树的深度优先遍历有以下三种

前序遍历

前序遍历，又叫先根遍历。
遍历顺序：根 -> 左子树 -> 右子树

代码实现

void BinaryPrev(BT* n1)
{if (n1==NULL){printf("NULL ");return ;}printf("%c ", n1->x);BinaryPrev(n1->left);BinaryPrev(n1->right);
}

很多小伙伴可能会觉得：哇！这么少的代码就可以解决了吗？对，就是这么几行，这也就是递归遍历的强大之处。但是这之间的递归过程是很复杂的。

图解递归（由于图片大小问题，建议用手机客户端查看，以下图解也是）

---

中序遍历

中序遍历，又叫中根遍历。
遍历顺序：左子树 -> 根 -> 右子树

代码实现

void MiddleOrder(BT* n1)
{if (n1 == NULL){printf("NULL ");return;}MiddleOrder(n1->left);printf("%c ", n1->x);MiddleOrder(n1->right);
}

这个也是同样的简单，只要按着它的顺序写就行了，但其中的过程很复杂。

图解递归

---

后序遍历

后序遍历，又叫后根遍历。
遍历顺序：左子树 -> 右子树 -> 根

代码实现

void AfterOrder(BT* n1)
{if (n1 == NULL){printf("NULL ");return;}AfterOrder(n1->left);AfterOrder(n1->right);printf("%c ", n1->x);
}

这个同样也是只要按着顺序写就可以了，递归起来很复杂。

图解递归

---

广度优先遍历

层序遍历

层序遍历，自上而下，从左往右逐层访问树的结点的过程就是层序遍历。

思路（借助一个队列）：
1.先把根入队列，然后开始从队头出数据。
2.出队头的数据，把它的左孩子和右孩子依次从队尾入队列（NULL不入队列）。
3.重复进行步骤2，直到队列为空为止。

代码实现

在实现过程中要用到队列，具体队列的实现这儿就不说了，博主之前的博客中有相关的文章。

void BinaryLevelOrder(BT* n1)
{Queue q;QueueInit(&q);if (n1!=NULL){QueuePush(&q, n1);}while (!QueueEmpty(&q)){BT* front = QueueTop(&q);QueuePop(&q);printf("%c ", front->x);// 不把NULL打印出来//if (front->left!=NULL)//{//	QueuePush(&q, front->left);//}//if (front->right != NULL)//{//	QueuePush(&q, front->right);//}if (front->left != NULL){QueuePush(&q, front->left);}else{printf("NULL ");}if (front->right != NULL){QueuePush(&q, front->right);}else{printf("NULL ");}}QueueDestory(&q);
}