数据结构初阶-二叉树链式

1.概念与结构

2.二叉数链式的实现

2.1遍历规则

2.2申请内存空间

2.3手动构建一棵二叉树

2.4二叉树结点的个数

2.5二叉树叶子结点的个数

2.6二叉树第K层结点个数

2.7二叉树的高度

2.8二叉树中查找值为x的结点

2.9二叉树的销毁

3.层序遍历

3.1概念

3.2层序遍历的实现

4.判断是否为完全二叉树

5.总结

1.概念与结构

用链表来表示一棵二叉树，即用链表来指示元素的逻辑关系。通常的方法是链表中每一个由三个域组成：数据域，左指针域和右指针域。左右指针分别用来给出该结点的左孩子和右孩子所在的链结点的存储地址，最终结点的结构是下面所示：

typedef int BTDataType;
typedef struct BinaryTreeNode
{
   BTDataType data;
   struct BinaryTreeNode* left;
   struct BinaryTreeNode* right;
}BTNode;

由于根结点的左子树分别又是由子树结点、子树结点的左子树、子树结点的右子树组成的。因此二叉树定义是递归式的，链式二叉树的操作中基本都是按照该概念实现的。所以我们在二叉树的各种操作中都要用到递归操作，所以代码比较简单，但是比较难写出来！

2.二叉数链式的实现

2.1遍历规则

（1）前序遍历

访问根结点的操作发生在左右结点之前，即我们先遍历更结点然后再是左结点，最后才是右结点。

我们从A开始进入二叉树，先打印A结点的数据，再打印A结点的左孩子即为B，再同理推出D，由于D的左孩子为NULL，打印完NULL后再进入D的右孩子，又为NULL，然后返回到B ，B 的左孩子已经打印完了，所以我们开始打印B的右孩子，由于为NULL，所以我们返回到B，B 子树已经全部遍历完了，所以我们开始遍历C 子树，以此类推，最终打印出顺序为：ABDNULLNULLNULLCENULLNULLFNULLNULL这就是我们所说的前序遍历。

代码实现：

//前序遍历
void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c", root->data);//我们主要是打印出这个结点的位置，所以我们用字母来表示这个//我们要把开始typedef的int 改为charPreOrder(root->left);PreOrder(root->right);
}

(2)中序遍历

中序遍历是先从左结点开始遍历后面是根结点最后是右结点。容易知道上副图的遍历结果为ABDNULLNULLNULLCENULLNULLFNULLNULL,所以最终代码实现是：

//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}

（3）后序遍历

后序遍历是先去遍历左结点，再是右结点最后才是根结点，所以开始的运行结果为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);
}

2.2申请内存空间

我们需要先malloc一个结点大小的空间并且把传入的数据赋值给data，左孩子和右孩子指针置为NULL，所以代码如下：

//申请内存空间
BTNode* buyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));node->data = x;node->left = node->right = NULL;
}

2.3手动构建一棵二叉树

我们如果和我们之前的那张图片一样构造二叉树的结果一样的话，我们可以写出以下代码：

//手动构造一块二叉树
BTNode* CreateTree()
{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;
}

2.4二叉树结点的个数

我们发现二叉树结点个数等于左子树的结点个数加上右结点个数加上根结点的个数（1）构成，而左子树也等于左二叉树的结点个数加上右二叉树的结点个数加上根结点的个数（1）构成，所以最终代码如下：

//二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

2.5二叉树叶子结点的个数

我们发现二叉树叶子结点的个数=左子树叶子结点的个数+右子树叶子结点的个数，所以最终代码如下：

//叶子结点的个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

2.6二叉树第K层结点个数

我们发现二叉树第K层结点个数=左子树第K层结点的个数+右子树第K层结点的个数，所以最终代码如下：

//二叉树第K层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

2.7二叉树的高度

我们要比较的是左子树深度和右子树的深度，比较大的一方才算，即为根结点+max(左子树，右子树）我们先调用一下左子树的递归序列，并把左子树的深度存储起来，然后把右子树按照同样的方法进行存储，后面返回其中最大的一个加1即可，最终代码如下：

//求二叉树的深度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return 1 + (leftDep > rightDep ? leftDep : rightDep);
}

2.8二叉树中查找值为x的结点

我们用前序遍历方法进行查找，代码如下：

//二叉树中查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryTreeFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryTreeFind(root->right, x);if (rightFind){return rightFind;}return NULL;
}

2.9二叉树的销毁

我们需要传一个指针，然后先进行左子树的销毁，最后再进行右子树的销毁，所以代码如下：

//二叉树的销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&(*root)->left);//->的优先级大于*BinaryTreeDestory(&(*root)->right);free(*root);*root = NULL;
}

3.层序遍历

3.1概念

层序遍历就是从二叉树的根结点出发，依次往左孩子到右孩子进行访问，像我们上一副图的层序遍历就是ABCDEF。

3.2层序遍历的实现

先说结论，我们用队列来实现层序遍历，先进行根结点入队列，若发现不为空，则把队头数据进行出队操作，若取出的结点有左孩子（右孩子），则把左孩子（右孩子）入队列，依次类推。所以我们需要队列这个数据结构的帮助。我们把之前的代码复制过来有

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>
#include<stdbool.h>
//定义队列结点的结构
typedef int STDataType;
typedef struct QueueNode
{STDataType data;struct QueueNode* next;
}QueueNode;
//队列的结构
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;
}Queue;
//队列的初始化
void QueueInit(Queue* pq)
{assert(pq);//防止传参为空pq->phead = pq->ptail = NULL;
}
//入队列
void QueuePush(Queue* pq, STDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!\n");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL){//也可以写为//pq->phead==pq->ptailpq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;//也可以把pq->ptail=newnode写到if-else语句之后}
}
//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}
//队列有效元素的个数
int QueueSize(Queue* pq)
{int size = 0;QueueNode* pcur = pq->phead;while (pcur){size++;pcur = pcur->next;}return size;
}
//出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}
}
//取队头数据
STDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}
//取队尾数据
STDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}
//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;//可以加pq->size=0
}
//测试函数
void test()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);int size = QueueSize(&q);printf("%d\n", size);QueuePop(&q);size = QueueSize(&q);printf("%d\n", size);size = QueueFront(&q);printf("%d\n", size);size = QueueBack(&q);printf("%d\n", size);QueueDestroy(&q);
}
int main()
{test();return 0;
}

我们需要改以下的东西：typedef struct BiaryTreeNode* STDataType;（我们所存储的数据类型是struct BinaryTreeNode*）,之所以是指针，因为我们之后要使用二级指针，这样子更方便，所以最终实现有：

//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);printf("%c ", top->data);if (top->left){QueuePush(&q, top->left);}if (top->right){QueuePush(&q, top->right);}}QueueDestroy(&q);
}

4.判断是否为完全二叉树

完全二叉树有两个特点：除最后一层外其余层数的结点个数都达到最大；最后一层结点从左到右依次排列。代码实现如下（我会注释）：

//判断是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头出队头BTNode* top = QueueFront(&q);QueuePop(&q);if (top == NULL){break;}//把不为空的队头结点的左右孩子入队列QueuePush(&q, top->left);QueuePush(&q, top->right);}//队列不一定为空，继续取队头出队头while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);if (top != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}