【数据结构】二叉树的链式结构--用C语言实现

技术文档

1.二叉树的链式结构

此前，我们通过数组（顺序表）完成了二叉树的顺序存储，并实现了二叉树的基础功能
那么，二叉树还有没有其他存储方式呢？

前面我们学习了链表，它是一种线性结构，而二叉树是一种非线性结构，但是通过思考，我们发现链表是通过next指针把一个一个的节点连接起来的，那么我们如何用相似的方式把二叉树相应的节点连接起来呢？

//链表节点typedef int LTDataType;//存储的数据类型typedef struct ListNode{LTDataType val;//数据值struct ListNode* next;//指向下一个节点}LTNOde;

【数据结构】二叉树的链式结构--用C语言实现

通过观察，我们发现二叉树中，节点最大的度为2(每个节点最多连接两个字节点)，所以我们可以在链表节点的基础上，再添加一个指针，用两个指针来指向子节点，即可把整个二叉树连接起来，形成一个链式结构

typedef int BTDataType;//存储的数据类型typedef struct BinaryTreeNode{LTDataType val;//数据值//指向左子节点struct BinaryTreeNode* left;//指向右子节点struct BinaryTreeNode* right;}BTNode;

【数据结构】二叉树的链式结构--用C语言实现

2.链式结构的遍历顺序

链式结构的遍历顺序分为三种：前序遍历、中序遍历、后序遍历

注：他们的顺序都是相对于根节点的
前序遍历：根节点-左节点-右节点
中序遍历：左节点-根节点-右节点
后续遍历：左节点-右节点-根节点

2.1.前序遍历

从根节点开始遍历，然后遍历左子树，最后遍历右子树
【数据结构】二叉树的链式结构--用C语言实现

根节点为A(当前前序遍历结果：A)
再遍历A的左子树，继续以根-左-右的顺序遍历，找到子树的根节点B(当前前序遍历结果：A-B)
遍历B的左子树，找到D，D没有子树了，所以B的左子树遍历完了(当前前序遍历结果：A-B-D)
B的根和左子树遍历完了，开始遍历B的右子树，找到节点E，此时A的左子树遍历完了(当前前序遍历结果：A-B-D-E)
A的根和左子树遍历完了，开始遍历A的右子树
找到A的子树的根节点C(当前前序遍历结果：A-B-D-E-C)
开始遍历C的左子树，找到F，C的左子树遍历完毕(当前前序遍历结果：A-B-D-E-C-F)
开始遍历C的右子树，找到G，此时A的右子树遍历完毕(当前前序遍历结果：A-B-D-E-C-F-G)
前序遍历完成
最终结果为A-B-D-E-C-F-G

2.1.中序遍历

从左子树开始遍历，再遍历根节点，最后遍历右子树
【数据结构】二叉树的链式结构--用C语言实现
11. 先遍历根节点A的左子树，来到子树中的根节点B，他有左子树，继续向下遍历找他的左子树，找到节点D，由于D没有左子树了，所以取D(当前中序遍历结果：D-)
12. B的左子树遍历完了，遍历根B本身，取B(当前中序遍历结果：D-😎
13. 遍历B的右子树，找到E，E没有子树了，取E，B的右子树遍历完成(当前中序遍历结果：D-B-E)
14. 此时A的左子树遍历完成，遍历根A本身，取A(当前中序遍历结果：D-B-E-A)
15. A的左子树和根遍历完成，遍历A的右子树来到C，C有左子树，来到F，F没有子树了，取F(当前中序遍历结果：D-B-E-A-F)
16. C的左子树遍历完成，遍历根C本身，取节点C(当前中序遍历结果：D-B-E-A-F-C)
17. C的左子树和根遍历完成，遍历右子树，找到节点G，它没有子树了，取G(当前中序遍历结果：D-B-E-A-F-C-G)
18. A的右子树遍历完成，中序遍历完毕
19. 最终结果为D-B-E-A-F-C-G

2.3.后序遍历

从左子树开始遍历，再遍历右子树，最后遍历根
【数据结构】二叉树的链式结构--用C语言实现

先遍历根A的左子树，找到节点B，B有左子树，继续遍历，找到节点D，D没有子树了，取D(当前后序遍历结果：D)
B的左子树遍历完成，继续遍历它的右子树，找到节点E，没有子树了，取E(当前后序遍历结果：D-E)
B的右子树遍历完成，取B本身(当前后序遍历结果：D-E-B)
A的左子树遍历完成，继续遍历A的右子树，找到节点C，继续遍历C的左子树，找到节点F，F没有子树了，取F(当前后序遍历结果：D-E-B-F)
C的左子树遍历完成，继续遍历它的右子树，找到节点G，G没有子树了，取G(当前后序遍历结果：D-E-B-F-G)
C的左右子树遍历完成，取根C本身(当前后序遍历结果：D-E-B-F-G-C)
此时A的左右子树遍历完成，取根A本身(当前后序遍历结果：D-E-B-F-G-C-A)
后序遍历完成，最终结果为D-E-B-F-G-C-A

3.二叉树链式结构的实现

3.1.二叉树节点结构的定义

一个结构体类型，成员包含存储数据的值和分别指向左孩子和右孩子的左右指针

typedef char BTDataType;typedef struct BinaryTreeNode{ BTDataType _data; struct BinaryTreeNode* _left; struct BinaryTreeNode* _right;}BTNode;

3.2.创建节点

开辟一个节点大小的空间，把数据值存入该节点，返回这片空间的地址

BTNode* BTBuyNode(BTDataType x){ BTNode* newNode = (BTNode*)malloc(sizeof(BTNode)); if(newNode == NULL) { perror(\"malloc error!\\n\"); return NULL; } newNode->_data = x; newNode->_left = newNode->_right = NULL; return newNode;}

3.3.创建二叉树

以前序遍历为例，把数组中的数据，转化为链式结构，存储到二叉树中

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi){ if(*pi >= n || a[*pi] == \'#\') { (*pi)++; return NULL; } BTNode* root = BTBuyNode(a[(*pi)++]); root->_left = BinaryTreeCreate(a, n, pi); root->_right = BinaryTreeCreate(a, n, pi); return root;}

注：形参中的pi必须传指针(传址调用)，因为在递归过程中该形参会发生改变，如果采用传值调用，该形参值不能被正常修改

3.4.二叉树链式结构的销毁

以后序遍历的方式，先销毁左右子树，最后销毁根节点（如果先销毁根节点，那就找不到它的左右指针了，不能进行后续操作）

//左-右-根void BinaryTreeDestory(BTNode** root){ if(root == NULL || *root == NULL) { return ; } //注：传二级指针--指针的地址 BinaryTreeDestory(&((*root)->_left)); BinaryTreeDestory(&((*root)->_right)); free(*root); *root = NULL;}

3.5.节点总数

用递归的方式，返回左子树的节点个数+右子树的节点个数+根即可

int BinaryTreeSize(BTNode* root){ if(root == NULL) return 0; return 1 + BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right);}

3.6.叶子节点数

同样用递归的方式，返回左子树的叶子节点数+右子树的叶子节点数，当该节点没有左右子树时，即为叶子节点，返回1

int BinaryTreeLeafSize(BTNode* root){ if(root == NULL) return 0; if(!root->_left && !root->_right) return 1; return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);}

3.7.返回第K层的节点数

同样采用递归的方式，第K层节点数=根节点左子树的第K-1层节点数+根节点的右子树的第K-1层节点数，以此类推，每递归一次都减少一层···

int BinaryTreeLevelKSize(BTNode* root, int k){ if(root == NULL || k < 1) return 0; if(k == 1) return 1; return BinaryTreeLevelKSize(root->_left, k-1) + BinaryTreeLevelKSize(root->_right, k-1);}

3.8.查找节点

还是采用递归的方式，从根节点开始，遍历每一个节点，直到遇到目标值，返回该节点的地址

BTNode* BinaryTreeFind(BTNode* root, BTDataType x){ if(root == NULL) return NULL; if(root->_data == x) return root; BTNode* Left = BinaryTreeFind(root->_left, x); BTNode* Right = BinaryTreeFind(root->_right, x); if(Left) return Left; if(Right) return Right; return NULL;}

3.9.前序遍历

先打印根节点数据，再分别递归调用左子树和右子树

//根-左-右void BinaryTreePrevOrder(BTNode* root){ if(root == NULL) return; printf(\"%c \", root->_data); BinaryTreePrevOrder(root->_left); BinaryTreePrevOrder(root->_right);}

3.10.中序遍历

先递归调用左子树，再打印根节点数据，最后递归调用右子树

//左-根-右void BinaryTreeInOrder(BTNode* root){ if(root == NULL) return; BinaryTreeInOrder(root->_left); printf(\"%c \", root->_data); BinaryTreeInOrder(root->_right);}

3.11.后序遍历

先分别递归调用左右子树，再打印根节点

//左-右-根void BinaryTreePostOrder(BTNode* root){ if(root == NULL) return; BinaryTreePostOrder(root->_left); BinaryTreePostOrder(root->_right); printf(\"%c \", root->_data);}

3.12.层序遍历

由于每一个节点都是通过指针连接的后继节点，所以一层一层地调用是不现实的，这个时候我们可以借助队列来实现层序遍历：

创建一个队列，先让根节点入队，取出队列头节点并打印，（如果有的话）让它的左右孩子入队，若队列不为空，继续取出队头节点并打印，让它的左右孩子入队，重复以上操作，直到队列为空，则层序遍历完成

队列的实现（队列的详细讲解）：
Queue.h

//// Queue.h#include #include #include #include typedef struct BinaryTreeNode BTNode;//队列节点的结构typedef struct QueueNode{ BTNode* data; struct QueueNode* next;}QueueNode;//队列的结构typedef struct Queue{ QueueNode* front; QueueNode* rear;}Queue;//初始化队列void QueueInit(Queue* pq);//入队void QueuePush(Queue* pq, BTNode* x);//判空bool QueueEmpty(Queue* pq);//出队void QueuePop(Queue* pq);//取队头BTNode* QueueFront(Queue* pq);//销毁队列void QueueDestroy(Queue* pq);

Queue.c

//// Queue.c#include \"Queue.h\"void QueueInit(Queue* pq){ assert(pq); pq->front = pq->rear = NULL;}void QueuePush(Queue* pq, BTNode* x){ assert(pq); QueueNode* newQueNode = (QueueNode*)malloc(sizeof(QueueNode)); if(newQueNode == NULL) { perror(\"malloc fail!\\n\"); return; } newQueNode->data = x; newQueNode->next = NULL; if(pq->front == NULL) { pq->front = pq->rear = newQueNode; } else { pq->rear->next = newQueNode; pq->rear = newQueNode; }}bool QueueEmpty(Queue* pq){ assert(pq); return pq->front == NULL;}void QueuePop(Queue* pq){ assert(!QueueEmpty(pq)); QueueNode* del = pq->front; pq->front = del->next; if(pq->front == NULL) { pq->rear = NULL; } free(del); del = NULL;}BTNode* QueueFront(Queue* pq){ assert(!QueueEmpty(pq)); return pq->front->data;}void QueueDestroy(Queue* pq){ //节点 QueueNode* pcur = pq->front; while(pcur) { QueueNode* next= pcur->next; free(pcur); pcur = next; } //队列首尾 pq->front = pq->rear = NULL;}

层序遍历：

void BinaryTreeLevelOrder(BTNode* root){ if(root == NULL) return; 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);}

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

我们知道，完全二叉树是由满二叉树得来的，在完全二叉树中，最后一层以上的所有层次中，节点数都达到了最大值，而最后一层不一定，但一定满足节点从左到右依次排列
因此，我们可以通过此性质，仿照层次遍历的方式，通过队列，来实现完全二叉树的判定
注：取队头时，不需要判断左右孩子是否为空，直接入队即可，当队列头节点为空时，跳出循环，此时判断队列后序数据是否存在非空值，若存在，则不是完全二叉树，不存在，则是完全二叉树

bool BinaryTreeComplete(BTNode* root){//当遍历到空节点时 递归结束 if(root == NULL) return true; Queue q; QueueInit(&q); 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;}

4.完整代码

Queue.h

//// Queue.h#include #include #include #include typedef struct BinaryTreeNode BTNode;//队列节点的结构typedef struct QueueNode{ BTNode* data; struct QueueNode* next;}QueueNode;//队列的结构typedef struct Queue{ QueueNode* front; QueueNode* rear;}Queue;//初始化队列void QueueInit(Queue* pq);//入队void QueuePush(Queue* pq, BTNode* x);//判空bool QueueEmpty(Queue* pq);//出队void QueuePop(Queue* pq);//取队头BTNode* QueueFront(Queue* pq);//销毁队列void QueueDestroy(Queue* pq);

Tree.h

//// Tree.h#pragma once#include #include #include #include #include typedef char BTDataType;typedef struct BinaryTreeNode{ BTDataType _data; struct BinaryTreeNode* _left; struct BinaryTreeNode* _right;}BTNode;//创建节点BTNode* BTBuyNode(BTDataType x);// 通过前序遍历的数组\"ABD##E#H##CF##G##\"构建二叉树BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);// 二叉树销毁void BinaryTreeDestory(BTNode** root);// 二叉树节点个数int BinaryTreeSize(BTNode* root);// 二叉树叶子节点个数int BinaryTreeLeafSize(BTNode* root);// 二叉树第k层节点个数int BinaryTreeLevelKSize(BTNode* root, int k);// 二叉树查找值为x的节点BTNode* BinaryTreeFind(BTNode* root, BTDataType x);// 二叉树前序遍历void BinaryTreePrevOrder(BTNode* root);// 二叉树中序遍历void BinaryTreeInOrder(BTNode* root);// 二叉树后序遍历void BinaryTreePostOrder(BTNode* root);// 层序遍历void BinaryTreeLevelOrder(BTNode* root);// 判断二叉树是否是完全二叉树bool BinaryTreeComplete(BTNode* root);

Queue.c

//// Queue.c#include \"Queue.h\"void QueueInit(Queue* pq){ assert(pq); pq->front = pq->rear = NULL;}void QueuePush(Queue* pq, BTNode* x){ assert(pq); QueueNode* newQueNode = (QueueNode*)malloc(sizeof(QueueNode)); if(newQueNode == NULL) { perror(\"malloc fail!\\n\"); return; } newQueNode->data = x; newQueNode->next = NULL; if(pq->front == NULL) { pq->front = pq->rear = newQueNode; } else { pq->rear->next = newQueNode; pq->rear = newQueNode; }}bool QueueEmpty(Queue* pq){ assert(pq); return pq->front == NULL;}void QueuePop(Queue* pq){ assert(!QueueEmpty(pq)); QueueNode* del = pq->front; pq->front = del->next; if(pq->front == NULL) { pq->rear = NULL; } free(del); del = NULL;}BTNode* QueueFront(Queue* pq){ assert(!QueueEmpty(pq)); return pq->front->data;}void QueueDestroy(Queue* pq){ //节点 QueueNode* pcur = pq->front; while(pcur) { QueueNode* next= pcur->next; free(pcur); pcur = next; } //队列首尾 pq->front = pq->rear = NULL;}

Tree.c

//// Tree.c#include \"Tree.h\"#include \"Queue.h\"BTNode* BTBuyNode(BTDataType x){ BTNode* newNode = (BTNode*)malloc(sizeof(BTNode)); if(newNode == NULL) { perror(\"malloc error!\\n\"); return NULL; } newNode->_data = x; newNode->_left = newNode->_right = NULL; return newNode;}//前序：根-左-右BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi){ if(*pi >= n || a[*pi] == \'#\') { (*pi)++; return NULL; } BTNode* root = BTBuyNode(a[(*pi)++]); root->_left = BinaryTreeCreate(a, n, pi); root->_right = BinaryTreeCreate(a, n, pi); return root;}//左-右-根void BinaryTreeDestory(BTNode** root){ if(root == NULL || *root == NULL) { return ; } BinaryTreeDestory(&((*root)->_left)); BinaryTreeDestory(&((*root)->_right)); free(*root); *root = NULL;}int BinaryTreeSize(BTNode* root){ if(root == NULL) return 0; return 1 + BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right);}int BinaryTreeLeafSize(BTNode* root){ if(root == NULL) return 0; if(!root->_left && !root->_right) return 1; return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);}int BinaryTreeLevelKSize(BTNode* root, int k){ if(root == NULL || k < 1) return 0; if(k == 1) return 1; return BinaryTreeLevelKSize(root->_left, k-1) + BinaryTreeLevelKSize(root->_right, k-1);}BTNode* BinaryTreeFind(BTNode* root, BTDataType x){ if(root == NULL) return NULL; if(root->_data == x) return root; BTNode* Left = BinaryTreeFind(root->_left, x); BTNode* Right = BinaryTreeFind(root->_right, x); if(Left) return Left; if(Right) return Right; return NULL;}//根-左-右void BinaryTreePrevOrder(BTNode* root){ if(root == NULL) return; printf(\"%c \", root->_data); BinaryTreePrevOrder(root->_left); BinaryTreePrevOrder(root->_right);}//左-根-右void BinaryTreeInOrder(BTNode* root){ if(root == NULL) return; BinaryTreeInOrder(root->_left); printf(\"%c \", root->_data); BinaryTreeInOrder(root->_right);}//左-右-根void BinaryTreePostOrder(BTNode* root){ if(root == NULL) return; BinaryTreePostOrder(root->_left); BinaryTreePostOrder(root->_right); printf(\"%c \", root->_data);}//借助队列来实现void BinaryTreeLevelOrder(BTNode* root){ if(root == NULL) return; 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);}bool BinaryTreeComplete(BTNode* root){ if(root == NULL) return true; Queue q; QueueInit(&q); 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;}

main.c

//// main.c#include \"Tree.h\"void test(void){ char str[] = \"ABD##E#H##CF##G##\"; int i = 0; int n = (int)strlen(str); BTNode* root = BinaryTreeCreate(str, n, &i); printf(\"二叉树节点总数为：%d\\n\", BinaryTreeSize(root)); printf(\"二叉树叶子结点数为：%d\\n\", BinaryTreeLeafSize(root)); printf(\"二叉树第2层节点数为：%d\\n\", BinaryTreeLevelKSize(root, 2)); printf(\"节点‘F’所在地址为：%p\\n\", BinaryTreeFind(root, \'F\')); printf(\"二叉树前序遍历结果为：\"); BinaryTreePrevOrder(root);printf(\"\\n\"); printf(\"二叉树中序遍历结果为：\"); BinaryTreeInOrder(root);printf(\"\\n\"); printf(\"二叉树后序遍历结果为：\"); BinaryTreePostOrder(root);printf(\"\\n\"); printf(\"二叉树层序遍历结果为：\"); BinaryTreeLevelOrder(root);printf(\"\\n\"); BinaryTreeDestory(&root);}int main(void){ test(); return 0;}

运行结果

【数据结构】二叉树的链式结构--用C语言实现

【数据结构】二叉树的链式结构--用C语言实现

1.二叉树的链式结构

2.链式结构的遍历顺序

2.1.前序遍历

2.1.中序遍历

2.3.后序遍历

3.二叉树链式结构的实现

3.1.二叉树节点结构的定义

3.2.创建节点

3.3.创建二叉树

3.4.二叉树链式结构的销毁

3.5.节点总数

3.6.叶子节点数

3.7.返回第K层的节点数

3.8.查找节点

3.9.前序遍历

3.10.中序遍历

3.11.后序遍历

3.12.层序遍历

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

4.完整代码

Queue.h

Tree.h

Queue.c

Tree.c

main.c

运行结果

公告

DeepSeek全套部署资料免费下载

免费可商用字体批量下载

【数据结构】二叉树的链式结构--用C语言实现

1.二叉树的链式结构

2.链式结构的遍历顺序

2.1.前序遍历

2.1.中序遍历

2.3.后序遍历

3.二叉树链式结构的实现

3.1.二叉树节点结构的定义

3.2.创建节点

3.3.创建二叉树

3.4.二叉树链式结构的销毁

3.5.节点总数

3.6.叶子节点数

3.7.返回第K层的节点数

3.8.查找节点

3.9.前序遍历

3.10.中序遍历

3.11.后序遍历

3.12.层序遍历

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

4.完整代码

Queue.h

Tree.h

Queue.c

Tree.c

main.c

运行结果

相关问题

公告

DeepSeek全套部署资料免费下载

免费可商用字体批量下载