数据结构：二叉树的链式结构及相关算法详解

目录

一.链式结构的实现

1.二叉树结点基本结构，初始化与销毁：

二.链式结构二叉树的几种遍历算法

1.几种算法的简单区分：

2.前序遍历：

3.中序遍历：

4.后序遍历：

5.层序遍历（广度优先遍历BFS）：

三.链式二叉树的几种使用

1.计算树的结点个数：

2.计算树的叶子结点个数：

3.计算树的第k层结点个数：

4.计算树的深度：

5.查找结点为X的结点：

6.判断二叉树是否为完全二叉树：

---

一.链式结构的实现

1.二叉树结点基本结构，初始化与销毁：

（1）⽤链表来表示⼀棵⼆叉树，即⽤链来指示元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩子和右孩子所在的链结点的存储地址， 其结构如下：

（2）二叉树结点的初始化与树的创建：

#include"Tree.h"
//结点的初始化
BTNode* buyNode(char x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));node->data = x;node->left = node->right = NULL;return node;
}
//树结构的创建
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->right = nodeE;nodeC->right = nodeF;
}

（3）链式二叉树的销毁：

（使用后序遍历，我在下文会写出具体操作）

void BinaryTreeDestory(BTNode** root)
{//这里因为要改变根节点，应该传入的是根节点的地址，所以得拿二级指针接收//递归出口if ((*root) == NULL){return;}//自叶向根方向的释放//如果先释放的话，就找不到叶子节点了BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}

---

二.链式结构二叉树的几种遍历算法

1.几种算法的简单区分：

举一个普遍的例子具体说明一下，如图：

2.前序遍历：

简单说明一下前序遍历的基本逻辑：

假设一个树：   

    A
   / \
  B   C
 / \
D   E

那么其遍历过程为：
访问根节点  A 。
递归遍历左子树（以  B  为根）：
访问  B 
递归遍历左子树（以  D  为根）：
访问  D 
递归遍历右子树（以  E  为根）：
访问  E 
递归遍历右子树（以  C  为根）：
访问  C 

//前序遍历
void preOrder(BTNode* root)
{//头 左 右//递归出口if (root == NULL){printf("NULL");return;}printf("%c",root->data);preOrder(root->left);preOrder(root->right);
}

3.中序遍历：

void inOrder(BTNode* root)
{//左 头 右//递归出口if (root == NULL){printf("NULL");return;}inOrder(root->left); //注意别调用错了，调用中序的printf("%c", root->data);inOrder(root->right);
}

4.后序遍历：

void postOrder(BTNode* root)
{//递归出口if (root == NULL){printf("NULL");return;}postOrder(root->left);postOrder(root->right);printf("%c", root->data);
}

总结：如上述所示，前中后序遍历的代码共同点也是相当明显了，主要就是递归顺序左右子树的顺序不同而影响的代码输出顺序不同，其根本上来说就是函数栈帧的不断进行嵌套式的创建与销毁，如果挨个遍历可能会显得比较复杂，但通过代码所示的这种递归算法，前中后序的遍历实现也显得十分简洁明了

但还有一点尤其需要注意：就是不同于层序遍历，我上面所说的三种遍历都属于深度优先遍历（DFS），而层序遍历却属于广度优先遍历，关于这两大类遍历的优劣我会在实现层序遍历后作详细介绍

5.层序遍历（广度优先遍历BFS）：

思路：

借助数据结构：队列，先通过根节点入队列，再循环判断队列是否为空，不为空则取队头然后出队头，并将队头结点的左右孩子入队列

(由于后续层序遍历的实现需要用到好些队列的知识，所有我先将队列的一些简单用法附在下面，需要的可以稍微看看)

//定义结点结构
typedef int QDataTpe;
typedef struct QueueNode
{struct QueneNode* next;QDataTpe data;
}QueueNode;//定义队列的结构
typedef struct Queue
{QueueNode* phead;//队头QueueNode* ptail;//队尾int size;
}Queue;BTNode* buyNode(char x);//队列初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;
}//入队（从队尾入）
void QueuePush(Queue* pq, QDataTpe x)
{assert(pq);//申请一个结点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc failed");exit(1);}newnode->data = x;newnode->next = NULL;//队列为空，newnode是对头也是队尾if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else //队列非空，尾插{pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == 0;
}//出队（从队头出）
void QueuePop(Queue* pq)
{assert(!QueueEmpty(pq));//只有一个结点的情况下，要把队尾和队头的两个指针都考虑到if (pq->phead == pq->ptail){free(pq->ptail);pq->phead = pq->ptail = NULL;}QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;  pq->size--;
}//取队头数据
QDataTpe QueueFront(Queue* pq)
{assert(!QueueEmpty(pq));return pq->phead->data;
}
//取队尾数据
QDataTpe QueueBack(Queue* pq)
{assert(!QueueEmpty(pq));return pq->ptail->data;
}//队列的销毁
void QueueDestory(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;
}//取队列元素个数
int QueueSize(Queue* pq)
{return pq->size;
}

//层序遍历
void LeveIOrder(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);}QueuDestroy(&q);}}

小结： 
DFS 优点（深度优先遍历）
节点少时效率高，节省内存
适合需要“全探索”或“找到任意解即可”的场景（如迷宫路径）
 
DFS 缺点
可能陷入无限循环（需记录已访问节点）
不保证最短路径（除非剪枝优化）

BFS 优点 （广度优先遍历）
保证找到最短路径（无权图中）
层级分明，易于理解
 
BFS 缺点
内存占用大（需存储整个层级节点）
不适合大规模数据或深层结构（如树深度极大）

---

三.链式二叉树的几种使用

1.计算树的结点个数：

法一：把size作为一个函数的形参，然后把这个树遍历一遍，每遍历一个节点就size（节点个数）加一，但需要注意的是，需要传入size的地址才能改变size的值

void BinaryTreeSize(BTNode* root,int* size)
{if (root == NULL){return;}(*size)++;BinaryTreeSize(root->left,size);BinaryTreeSize(root->right, size);
}

法二：递归，  节点个数=左子树节点个数+右子树节点个数，所以我们以此为基础递归就可以了

int BinaryTreeSize(BTNode* root)
{//节点个数=左子树节点个数+右子树节点个数//递归出口if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

2.计算树的叶子结点个数：

叶子结点：即没有左右孩子结点的结点4

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);
}

3.计算树的第k层结点个数：

如上图，当k=1时就是最底层结点，因此从最底层往上嵌套遍历就可以实现

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);
}

4.计算树的深度：

int BinaryTreeDeep(BTNode* root)
{//计算树的深度if (root == NULL){return 0;}int lefDep = BinaryTreeDeep(root->left);int rigDep = BinaryTreeDeep(root->right);return 1 + (lefDep > rigDep ? lefDep : rigDep);
}

5.查找结点为X的结点：

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{//递归出口if (root == NULL){return 0;}if (root->data == x){return root;}//代码走到这里证明根节点并不是我们要找的结点//接下来是左右子树各自分开递归搜查BTNode* left = BinaryTreeFind(root->left, x);if (left)//由于函数最后返回NULL，所以如果这个if条件可以进入就足以说明找到了需要的结点{return root;}BTNode* right = BinaryTreeFind(root->right, x);if (right){return root;}return NULL;
}

6.判断二叉树是否为完全二叉树：

// 判断⼆叉树是否是完全⼆叉树
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);}//队列不为空，继续取队头出队头//1）队头存在非空结点----非完全二叉树//2）队头不存在非空结点----完全二叉树while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);if (top != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

第一个while是为了验证根结点，如果根结点为空，直接返回false，如果根结点不为空，就将树里的结点循环入队列然后继续将子结点入队列并且判断其是否为空，同样的第一次循环的的结束条件是当出现空为止，因此，当来到第二次循环时，树的结点里说明已经第一次循环出了空结点，而当树是完全二叉树时，第二次循环之后队列里应该全是空结点，因此，只要当第二次循环里出现非空结点时，就可以判断其时非完全二叉树（这题思路比较复杂，可以多想一会）

欧克，本次关于链式二叉树的知识点就到此为止了，相关的题目我也会在未来附上

ok，全文终