学习笔记—数据结构—二叉树（链式）

目录

二叉树（链式）

概念

结构

初始化

遍历

前序遍历

中序遍历

后序遍历

层序遍历

结点个数

叶子结点个数

第k层结点个数

深度/高度

查找值为x的结点

销毁

判断是否为完整二叉树

总结

头文件Tree.h

Tree.c

测试文件test.c

补充文件Queue.h

补充文件Queue.c

---

二叉树（链式）

概念

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

结构

//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;               //值域struct BinaryTreeNode* left;   //左孩子struct BinaryTreeNode* right;  //右孩子
}BTNode;

初始化

//初始化
BTNode* buyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("mallor fail!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}

遍历

前序遍历

前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发生在遍历其左右⼦树之前

访问顺序为：根结点、左子树、右子树

//前序遍历--根左右
void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}

中序遍历

中序遍历(Inorder Traversal)：访问根结点的操作发生在遍历其左右子树之中（间）

访问顺序为：左子树、根结点、右子树

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

后序遍历

后序遍历(Postorder Traversal)：访问根结点的操作发生在遍历其左右子树之后

访问顺序为：左子树、右子树、根结点

//后续遍历--左右根
void PostOrder(BTNode* root)
{if (root == NULL){return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);}

层序遍历

在二叉树的层序遍历是指按照树的层次顺序，从上到下、从左到右逐层访问二叉树的节点。这种遍历方式可以帮助我们了解二叉树的结构布局，特别是在处理树状数据结构时非常有用。

对于这么一个二叉树来说，我们通过层序遍历最后得到的是1 2 3 4 5 6

这里我们是不能通过递归来实现的

但是我们可以借助队列来实现这么一个结构

队列的结构是先进先出

恰好我们队列的底层结构就是链表来实现的，和这里的链式二叉树一样的

我们将之前写的Queue.c文件和Queue.h文件复制到我们链式二叉树的文件夹里面

typedef struct BinaryTreeNode* QDataType;

struct BinaryTreeNode*这个就是我们要保存在队列中的数据类型

之前的在队列中保存的数据类型是int类型

队列中存储的是堆节点的地址

那么存储的就是节点的指针，那么我们将这个类型重新定义

//层序遍历
void Levelorder(BTNode* root)
{//创建一个队列结构Queue q;QueueInit(&q);//进行初始化//第一步：让根节点直接入队列QueuePush(&q, root);//往队列中push根节点while (!Queuempty(&q))//只要队列不为空，我们就一直取队头数据{//取队头数据BTNode* front = QueueFront(&q);//将队头取出，返回值是节点的地址//打印对头printf("%d ", front->data);//让队头出队列QueuePop(&q);//那么此时的队列是空的//将队头节点的左右孩子入队列if (front->left)//如果这个节点的左孩子不是空的，那么我们将这个节点往队列中入{QueuePush(&q, front->left);}if (front->right)//如果这个节点的右孩子不是空的，那么我们将这个节点往队列中入{QueuePush(&q, front->right);}}QueueDestroy(&q);//销毁
}

结点个数

利用递归的方法，左右子树调用，如果该节点为NULL 便会返回0，否则返回1。

// 二叉树结点个数
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 ==NULL && root->right ==NULL){return 1;}//进行递归return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

第k层结点个数

假设查找第三层，K为3 ，每次递归K–，知道K== 1 的时候 返回1

// 二叉树第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));
}

深度/高度

利用 left和right记录左右子树的个数，然后比较 选择较大的一个。

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

查找值为x的结点

节点的查找，如果节点为NULL饭后NULL，如果此节点的data等于x，返回节点的地址。

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

销毁

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return 0;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}

判断是否为完整二叉树

除了最后一层，其它层的节点数达到最大，那么这个数就是完全二叉树

这里涉及到每层，那么这里还是要借助队列这么一个结构的

我们先取根节点放进队列，队列不为空，我们将队列中的节点取出来

然后将这个节点的左右孩子一起放进队列中去

我们再将队头取出，将队头的左右孩子放进去，如果孩子为空放个NULL进去

如果我们队列剩下的都是NULL的话，我们将队列中第一个NULL取出

那么我们取到的数据为空，取到为空的情况我们就跳出循环

//判断二叉树是否为完全二叉树
//借助队列
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);//进行初始化//将二叉树根节点入队列QueuePush(&q, root);//往队列中push根节点while (!Queuempty(&q))//队列不为空，我们就循环取队头{BTNode* front = QueueFront(&q);//将队头取出QueuePop(&q);//让队头出队，保证下次取到的是最新的队头数据//如果我们取到的front是空的话if (front == NULL)//如果此时的队头是空的，那么我们就取不到左右孩子{break;}//将队头的左右孩子取出放到队列中QueuePush(&q, front->left);QueuePush(&q, front->right);}//此时队列不一定为空while (!Queuempty(&q))//只要队列不为空{BTNode* front = QueueFront(&q);//取队头QueuePop(&q);//出队列//如果我们在队列中剩下的节点中遇到了节点的话，那么这个树就不是一个完全二叉树了if (front != NULL){QueueDestroy(&q);//销毁return false;}}QueueDestroy(&q);//销毁//到这里就说明没有找到完全二叉树return true;
}

总结

头文件Tree.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>//定义二叉树链式结构
//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;               //值域struct BinaryTreeNode* left;   //左孩子struct BinaryTreeNode* right;  //右孩子
}BTNode;//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后续遍历
void PostOrder(BTNode* root);// 二叉树结点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树的深度/高度
int BinaryTreeDepth(BTNode * root);
// 二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);//层序遍历---借助数据结构（队列）
void Levelorder(BTNode* root);
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

Tree.c

#include"Tree.h"
#include"Queue.h"
//前序遍历--根左右
void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}//中序遍历--左根右
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}//后续遍历--左右根
void PostOrder(BTNode* root)
{if (root == NULL){return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);}// 二叉树结点个数
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 ==NULL && root->right ==NULL){return 1;}//进行递归return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}// 二叉树第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));
}// 二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
}// 二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return 0;}if (root->data == x){return 1;}BTNode* leftFind = BinaryTreeFind(root->left,x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryTreeFind(root->right,x);if (leftFind){return rightFind;}return NULL;
}// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return 0;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}//层序遍历
void Levelorder(BTNode* root)
{//创建一个队列结构Queue q;QueueInit(&q);//进行初始化//第一步：让根节点直接入队列QueuePush(&q, root);//往队列中push根节点while (!Queuempty(&q))//只要队列不为空，我们就一直取队头数据{//取队头数据BTNode* front = QueueFront(&q);//将队头取出，返回值是节点的地址//打印对头printf("%d ", front->data);//让队头出队列QueuePop(&q);//那么此时的队列是空的//将队头节点的左右孩子入队列if (front->left)//如果这个节点的左孩子不是空的，那么我们将这个节点往队列中入{QueuePush(&q, front->left);}if (front->right)//如果这个节点的右孩子不是空的，那么我们将这个节点往队列中入{QueuePush(&q, front->right);}}QueueDestroy(&q);//销毁
}//判断二叉树是否为完全二叉树
//借助队列
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);//进行初始化//将二叉树根节点入队列QueuePush(&q, root);//往队列中push根节点while (!Queuempty(&q))//队列不为空，我们就循环取队头{BTNode* front = QueueFront(&q);//将队头取出QueuePop(&q);//让队头出队，保证下次取到的是最新的队头数据//如果我们取到的front是空的话if (front == NULL)//如果此时的队头是空的，那么我们就取不到左右孩子{break;}//将队头的左右孩子取出放到队列中QueuePush(&q, front->left);QueuePush(&q, front->right);}//此时队列不一定为空while (!Queuempty(&q))//只要队列不为空{BTNode* front = QueueFront(&q);//取队头QueuePop(&q);//出队列//如果我们在队列中剩下的节点中遇到了节点的话，那么这个树就不是一个完全二叉树了if (front != NULL){QueueDestroy(&q);//销毁return false;}}QueueDestroy(&q);//销毁//到这里就说明没有找到完全二叉树return true;
}

测试文件test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"tree.h"BTNode* buyNode(BTDataType x)//创建一个节点
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
void test01()
{BTNode* node1 = buyNode(1);BTNode* node2 = buyNode(2);BTNode* node3 = buyNode(3);BTNode* node4 = buyNode(4);/*BTNode* node5 = buyNode(5);BTNode* node6 = buyNode(6);*/node1->left = node2;node1->right = node3;node2->left = node4;/*node2->right = node5;node3->left = node6;*///前序遍历PreOrder(node1);// 1 2 4 3printf("\n");//中序遍历InOrder(node1);// 4 2 1 3//二叉树节点的个数printf("size:%d\n", BinaryTreeSize(node1));//4printf("size:%d\n", BinaryTreeSize(node2));//2// 二叉树叶子结点的个数printf("leaf size:%d\n", BinaryTreeLeafSize(node1));//第k层节点的个数printf("k size:%d\n", BinaryTreeLevelKSize(node1, 3));//二叉树的高度printf("depth/height :%d\n", BinaryTreeDepth(node1));//查找值为x的节点BTNode*find=BinaryTreeFind(node1, 5);printf("%s\n", find == NULL ? "没找到":"找到了");//层序遍历Levelorder(node1);//判断是否为完全二叉树bool ret = BinaryTreeComplete(node1);printf("%s\n", ret == false ? "不是完全二叉树" : "是完全二叉树");//二叉树的销毁BinaryTreeDestory(&node1);}
int main()
{test01();return 0;
}

补充文件Queue.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义队列结构
//typedef int QDataType;typedef struct BinaryTreeNode* QDataType;
//struct BinaryTreeNode*这个就是我们要保存在队列中的数据类型
//struct BinaryTreeNode*这个是个数据类型，和之前的
//之前的在队列中保存的数据类型是int类型
//因为我们在tree.h中将结构体类型重命名了
//那么我们可以这么写
//typedef struct BTNode* QDataType;typedef struct QueueNode
{QDataType data;struct QueueNode* next;}QueueNode;typedef struct Queue
{QueueNode* phead;//指向头节点的指针---队头--删除数据QueueNode* ptail;//指向尾节点的指针---队尾--插入数据int size;//保存队列有效个数
}Queue;//初始化
void QueueInit(Queue* pq);//入队列，队尾   插入数据
void QueuePush(Queue* pq, QDataType x);//出队列,队头    删除数据
void QueuePop(Queue* pq);//判断队列是否为空
bool Queuempty(Queue* pq);//取队头数据
QDataType QueueFront(Queue* pq);//取队尾数据
QDataType QueueBack(Queue* pq);//队列有效元素个数
int QueueSize(Queue* pq);//队列的销毁
void QueueDestroy(Queue* pq);

补充文件Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"//初始化
void QueueInit(Queue* pq)
{assert(pq);//传过来的不能是空指针 pq->phead = pq->ptail = NULL;//空的队列pq->size = 0;
}//判断队列是否为空
bool Queuempty(Queue* pq)
{assert(pq);return pq->phead == NULL && pq->ptail == NULL;//如果后面的表达式成立，那么就是真，返回的是true//就是说如果这里的是空队列的话，那么就返回的是true
}//入队列，队尾   插入数据
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//申请新节点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//申请一个节点大小的空间if (newnode == NULL){perror("malloc dail!");exit(1);}//对newnode进行初始化操作newnode->data = x;newnode->next = NULL;if (pq->phead == NULL)//说明队列为空{pq->phead = pq->ptail = newnode;//那么此时的newnode不仅是头结点也是尾节点}else//队列不为空{pq->ptail->next = newnode;//那么此时的newnode 就是新的ptailpq->ptail = newnode;}pq->size++;
}//出队列,队头    删除数据    从头结点开始删除数据
void QueuePop(Queue* pq)
{assert(pq);//队列为空（不可删除数据，因为没有数据）//队列不为空（可删除数据）assert(!Queuempty(pq));//队列为空白的话就报错//处理只有一个节点的情况，避免ptail变成野指针//判断只有一个节点的情况if (pq->ptail == pq->phead)//头尾指针相同，说明只有一个节点{free(pq->phead);//随便释放pq->phead = pq->ptail = NULL;}else//处理多个节点的情况{//删除队头元素//那么我们现将下个节点的位置进行保存QueueNode* next = pq->phead->next;//存储好之后我们直接将头结点进行释放free(pq->phead);pq->phead = next;//那么之前存的next就是新的头结点了}pq->size--;
}//取队头数据
QDataType QueueFront(Queue* pq)//返回队头数据
{assert(pq);assert(!Queuempty(pq));//队列不为空return pq->phead->data;//将队头里面的数据直接返回就行了
}//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!Queuempty(pq));//队列不为空return pq->ptail->data;
}//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);//下面这种遍历的话效率太低了//int size = 0;//定义一个指针进行遍历//QueueNode* pcur = pq->phead;//指向队列的头结点//while (pcur)//pcur不为空就往后走//{//  size++;//  pcur = pcur->next;//}//return size;return pq->size;
}//队列的销毁
void QueueDestroy(Queue* pq)
{assert(pq);//assert(!Queuempty(pq));//队列不为空//遍历QueueNode* pcur = pq->phead;while (pcur){//销毁之前先把下个节点进行保存QueueNode* next = pcur->next;free(pcur);//将Pcur销毁之后，那么之前保存的next就是新的头结点pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}