二叉树的概念及结构创建
1、概念
简单回顾一下二叉树的概念：
★ 空树
★非空：根节点，根节点的左子树、根节点的右子树组成的。
从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。
2、结构创建
下面我们先看二叉树的结构体定义以及创建
typedef char BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; BTDataType data; }BTNode;
首先结构体的定义是元素本身，以及左右子树的指针。
2、创建结点函数
BTNode* BuyNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { printf("malloc fail\n"); exit(-1); } node->data = x; node->left = node->right = NULL; return node; }
我们指定每调用一次此函数，便新建一个结点空间，并将左右指针指向空即可。
3、建树函数
BTNode* CreatBinaryTree() { BTNode* nodeA = BuyNode('A'); BTNode* nodeB = BuyNode('B'); BTNode* nodeC = BuyNode('C'); BTNode* nodeD = BuyNode('D'); BTNode* nodeE = BuyNode('E'); BTNode* nodeF = BuyNode('F'); nodeA->left = nodeB; nodeA->right = nodeC; nodeB->left = nodeD; nodeC->left = nodeE; nodeC->right = nodeF; return nodeA; }
这个函数是树建立的关键步骤，将每个结点创建完成后，再将每个结点的左右指针重定义，继而完成建树，上述代码执行后表示的就是下图：
二叉树的遍历
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
主要分为以下几种：
1、前序遍历
前序遍历(Preorder Traversal | 先序遍历)——访问根结点的操作发生在遍历其左右子树之前，顺序为：根 ->左子树->右子树
比如上面这个二叉树前序遍历输出为:
A B D NULL NULL NULL C E NULL NULL F NULL NULL
实现代码如下：
void PreOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%c ", root->data); PreOrder(root->left); PreOrder(root->right); }
这个函数的实现是利用前序的性质，首先取根节点，之后每个结点先返回左结点，再返回右结点的顺序，进行递归调用，到最后的叶子结点之后再逐个返回打印输出，即为前序遍历。
2、中序遍历
中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中。
顺序为：左子树 ->根->右子树
比如这个二叉树中序遍历输出为:
NULL D NULL B NULL A NULL E NULL C NULL F NULL
实现代码如下：
void InOrder(BTNode* root) { if (root == NULL){ printf("NULL "); return; } InOrder(root->left); printf("%C ", root->data); InOrder(root->right); }
中序遍历就是将前序稍微做调整，先打印左子树，再打印根，之后才是右子树，同样用的是递归分治。
3、后序遍历
后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
顺序为：左子树 ->右子树->根
比如这个二叉树中序遍历输出为:
NULL NULL D NULL B NULL NULL E NULL NULL F C A
实现代码如下：
void PostOrder(BTNode* root) { if (root == NULL){ printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%C ", root->data); }
此函数与上面两个同理而得。
4、层序遍历
除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
比如这个二叉树，层序遍历结果为123456。
代码实现如下：
void BinaryTreeLevelOrder(BTNode* root) { if (root == NULL) return; Queue q; QueueInit(&q); QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); printf("%c ", front->data); if (front->left) QueuePush(&q, front->left); if (front->right) QueuePush(&q, front->right); } printf("\n"); QueueDestroy(&q); }
因为是链式结构，这里的层序遍历采用队列来实现，不了解队列的小伙伴可以看看我之前的文章：栈和队列之队列的介绍及实现
首先我们建立一个队列，初始化后先入根，再出根打印，继续打印其左右结点，继而循环打印，直到为空终止，最后释放队列空间，完成层序遍历打印。
二叉树的销毁
代码如下：
void BinaryTreeDestory(BTNode* root) { if (root == NULL) { return; } BinaryTreeDestory(root->left); BinaryTreeDestory(root->right); free(root); }
销毁与前中后序的实现一样，使用递归自下而上销毁。
结语
有兴趣的小伙伴可以关注作者，如果觉得内容不错，请给个一键三连吧，蟹蟹你哟！！！
制作不易，如有不正之处敬请指出
感谢大家的来访，UU们的观看是我坚持下去的动力
在时间的催化剂下，让我们彼此都成为更优秀的人吧！！！
