二叉树链式结构的实现

二叉树的概念及结构创建1、概念2、结构创建2、创建结点函数3、建树函数 二叉树的遍历1、前序遍历2、中序遍历3、后序遍历4、层序遍历 二叉树的销毁结语

二叉树的概念及结构创建

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们的观看是我坚持下去的动力
在时间的催化剂下，让我们彼此都成为更优秀的人吧！！！