C学习（数据结构）--＞实现链式结构二叉树

目录

一、链式二叉树结构

 二、实现

1、申请新结点

2、前、中、后序遍历

1）前序遍历

例：

2）中序遍历

3）后序遍历

 3、结点个数

1）二叉树结点个数

 例：​编辑

2）二叉树叶子结点个数

3）二叉树第k层结点个数

​编辑 4、二叉树深度

例： 

5、寻找值为x的结点

6、二叉树的销毁

三、其它

0、注意：

1、层序遍历

例：​编辑

当前队列初始化后为空队列

首先入队列

然后如果队列不为空则进入循环

 退出循环，层序遍历完成

2、判断是否为完全二叉树

四、总代码

队列  

链式二叉树

Tree.h

Tree.cpp

main.cpp

---

一、链式二叉树结构

//定义二叉树的链式结构
typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

 二、实现

1、申请新结点

//申请二叉树结点
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;
}

2、前、中、后序遍历

1）前序遍历

前序遍历的遍历顺序是：根结点-->左孩子结点-->右孩子结点

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

例：

一个链式二叉树

首先 1 作为根节点，遍历根结点，且打印根节点

打印完后，再向左孩子结点遍历，即标号为 2 的结点

标号为 2 的结点作为新的根结点，遍历 2 结点，且打印

然后遍历 2 结点的左孩子结点，即标号为 4 的结点

标号为 4 的结点作为新的根结点，遍历 4 结点，且打印

 

遍历 4 结点的左孩子结点，即为为NULL

 

应为是NULL，所以返回，然后遍历4 结点的右孩子结点，也是NULL

 

 4 结点的右孩子结点，也是NULL，所以返回。

此时4结点已经遍历完，放回 2 结点，因为 4 结点是 2 结点的左孩子结点，开始遍历 2 结点的右孩子结点，即标号为 6 的结点

遍历完 6 结点，再次返回 2 结点，此时 2 结点的左右孩子结点都遍历完，所以返回 1 结点，此时 1 结点的左孩子结点已经遍历完成，则遍历1 结点的右孩子结点，即 3 结点

 此时整个链式二叉树已经遍历完成，打印顺序为：1 2 4 5 3 6

2）中序遍历

 中序遍历的顺序：是左孩子结点-->根节点-->右孩子结点

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

以前序遍历为例，易得中序遍历的打印顺序为：4 2 5 1 6 3

3）后序遍历

后序遍历的遍历顺序为：左孩子结点-->右孩子结点-->根节点

//后序遍历--左右根
void PostOrder(BTNode* root)
{if (root == NULL)//判空{return;}PostOrder(root->left);//遍历左孩子结点PostOrder(root->right);//遍历右孩子结点printf("%d ", root->data);//打印根结点
}

 以前序遍历为例，易得后序遍历的打印顺序为：4 5 2 6 3 1

 3、结点个数

1）二叉树结点个数

//二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL)//判空{return 0;//当结点为空时返回 0 }//该节点不是空结点，返回 1 + 递归左右孩子结点返回的个数return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

 例：

 所以二叉树的结点个数为 6 

2）二叉树叶子结点个数

//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL)//判空{return 0;//结点为空时返回 0 }if (root->left == NULL && root->right == NULL)//判读叶子结点{return 1;//该结点是叶子结点返回 1}//当该节点既不是空结点也不是叶子结点时，返回递归左右孩子结点返回的个数return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

易得该二叉树叶子结点个数为 3 

3）二叉树第k层结点个数

//二叉树第k层结点个数
int BinaryTreeLexelKSize(BTNode* root, int k)
{if (root == NULL)//判空，空结点返回 0{return 0;}if (k == 1)// k 的递归是递减的，当 k == 1 时，即到达第 k 层，返回 1{return 1;}//即不是第 k 层，也不是空结点，返回递归左右孩子结点得到的数return BinaryTreeLexelKSize(root->left, k - 1) + BinaryTreeLexelKSize(root->right, k - 1);
}

 例：求第二层结点个数

 4、二叉树深度

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}//保存递归左右孩子结点返回的数int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);//比较左右孩子结点返回的数大小，满足条件返回 1 + leftdep，否则 1 + rightDepreturn leftDep > rightDep ? 1 + leftDep : 1 + rightDep;
}

例： 

所以该二叉树的深度为 3  

5、寻找值为x的结点

//二叉树寻找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{//如果结点为空if (root == NULL){return NULL;}if (root->data == x)//找到该x值返回该结点地址{return root;}BTNode* leftFind = BinaryTreeFind(root->left, x);//保存递归返回的结点地址if (leftFind)//结点地址不为空，只有找到 x 值才不为空{return leftFind;//返回的结点地址}BTNode* rightFind = BinaryTreeFind(root->right, x);//保存递归返回的结点地址if (rightFind)//结点地址不为空，只有找到 x 值才不为空{return rightFind;//返回的结点地址}//x值找不到return NULL;
}

6、二叉树的销毁

类似后序遍历

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

三、其它

0、注意：

需要用到队列，具体到C学习（数据结构）--＞队列_cpp 队列-CSDN博客

需要将队列的

typedef int QDataType;

改为

typedef struct BinaryTreeNode* QDataType;

1、层序遍历

//层序遍历，借用队列来实现
void LevelOrder(BTNode* root)
{Qu q;//初始化QueueInit(&q);//入队列QueuePush(&q, root);while (!QueueEmpty(&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);
}

例：

当前队列初始化后为空队列

首先入队列

	//入队列QueuePush(&q, root);

然后如果队列不为空则进入循环

while (!QueueEmpty(&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);//入队列}
}

重复通过取队头数据，入队列，出队列来层序遍历二叉树

 退出循环，层序遍历完成

2、判断是否为完全二叉树

//用队列判断是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Qu q;//初始化QueueInit(&q);//入队列QueuePush(&q, root);while (!QueueEmpty(&q))//判空{BTNode* front = QueueFront(&q);QueuePop(&q);//出队列if (front == NULL)//判空{break;}//入队列QueuePush(&q, front->left);QueuePush(&q, front->right);}//队列不一定为空while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

与层序遍历类似，不同的是，取消了判断左右孩子结点是否为空结点，所以就算左右孩子结点为空值结点也会入队列，所以不完全二叉树会出现这种情况

	//入队列QueuePush(&q, root);while (!QueueEmpty(&q))//判空{BTNode* front = QueueFront(&q);QueuePop(&q);//出队列if (front == NULL)//判空{break;}//入队列QueuePush(&q, front->left);QueuePush(&q, front->right);}

 当出队列的结点为空结点时退出循环，此时队列不为空，进入另一个循环

	//队列不一定为空while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){QueueDestroy(&q);return false;}}	QueueDestroy(&q);return true;

通过判断队列里是否还有空值来判断是否是完全二叉树

 

四、总代码

队列  

queue.h

queue.cpp

 具体到C学习（数据结构）--＞队列_cpp 队列-CSDN博客

需要将队列的

typedef int QDataType;

改为

typedef struct BinaryTreeNode* QDataType;

链式二叉树

Tree.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.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 BinaryTreeLexelKSize(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);
//申请二叉树结点
BTNode* BuyNode(BTDataType x);

Tree.cpp

#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 BinaryTreeLexelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLexelKSize(root->left, k - 1) + BinaryTreeLexelKSize(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 ? 1 + leftDep : 1 + rightDep;
}//二叉树寻找值为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;}//x值找不到return NULL;
}//二叉树的销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}//层序遍历，借用队列来实现
void LevelOrder(BTNode* root)
{Qu q;//初始化QueueInit(&q);//入队列QueuePush(&q, root);while (!QueueEmpty(&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)
{Qu q;//初始化QueueInit(&q);//入队列QueuePush(&q, root);while (!QueueEmpty(&q))//判空{BTNode* front = QueueFront(&q);QueuePop(&q);//出队列if (front == NULL)//判空{break;}//入队列QueuePush(&q, front->left);QueuePush(&q, front->right);}//队列不一定为空while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}//申请二叉树结点
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;
}

main.cpp

#include"Tree.h"
#include"Queue.h"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;printf("前序遍历：");PreOrder(node1);printf("\n");printf("中序遍历：");InOrder(node1);printf("\n");printf("后序遍历：");PostOrder(node1);printf("\n");printf("二叉树结点个数：%d\n", BinaryTreeSize(node1));printf("二叉树叶子结点个数：%d\n", BinaryTreeLeafSize(node1));printf("二叉树第k层结点个数：%d\n", BinaryTreeLexelKSize(node1, 2));printf("二叉树的深度/高度：%d\n", BinaryTreeDepth(node1));BTNode* find = BinaryTreeFind(node1, 5);printf("二叉树寻找值为x的结点：%d\n", find->data);printf("层序遍历：");LevelOrder(node1);printf("\n");//判断是否为完全二叉树printf("%s\n", BinaryTreeComplete(node1) == true ? "是完全二叉树" : "不是完全二叉树");//二叉树的销毁BinaryTreeDestory(&node1);
}int main()
{test01();return 0;
}