【C++】二叉树和堆的链式结构（下）

本篇博客给大家带来的是用C++语言来实现堆链式结构和二叉树的实现！

🐟🐟文章专栏：数据结构

🚀🚀若有问题评论区下讨论，我会及时回答

❤❤欢迎大家点赞、收藏、分享！

今日思想：你现在的懒惰将来你会买单的！

续接上文【C++】二叉树和堆的链式结构（上）-CSDN博客

没有看过上篇文章的朋友们一定要看，不然知识连接不上，我们来接着实现二叉树和堆的链式结构算法！

一、二叉树叶子结点个数

叶子结点是没有右孩子和左孩子的结点，俗称光棍。下面也会涉及一些专业知识大家可以看看这篇文章：【C++】树和二叉树的实现（上）-CSDN博客

叶子结点个数 = 左子树叶子结点个数 + 右子树叶子结点个数。

代码实例：

//Tree.h
//二叉树叶子结点个数
int BinaryTreeLeafsize(BTNode* root);

//Tree.c
//二叉树叶子结点个数
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层结点个数

假设我们求第3层的结点的个数，我们让K每层减一，当K=1时就是第三层结点的个数（如上图）。

代码实例：

//Tree.h
//二叉树第K层结点个数
int BinaryTreeleveIksize(BTNode* root, int k);

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

三、二叉树的高度/深度

二叉树的高度/深度= 1（根结点的那层）+max(左子树的高度，右子树高度)。

注意：不知道左右子树的高度。

代码实例：

//Tree.h
//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);

//Tree.c
//二叉树的深度/高度
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);
}

四、查找值为x的结点

代码实例：

//Tree.h
//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

//Tree.c
//二叉树查找值为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;
}

五、二叉树的销毁

直接上代码，思路过于简单就不水文了。

代码实例：

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

六、层序遍历

层序遍历是一层一层的遍历。

遍历顺序：A->B->C->D->E->F

思路：借助数据结构——队列，根结点入队列，循环遍历队列是否为空，不为空取队头出队头，将队头结点的左右孩子入队列（不为空）。

注意：不懂队列的朋友可以看看这篇博客：【C++】数据结构队列的实现_c++ 队列初始化-CSDN博客

代码实例：

//Tree.h
//层序遍历
void LeveIorder(BTNode* root);

//Tree.c
//层序遍历--队列
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);}}QueueDestroy(&q);
}

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

大家不知道完全二叉树可以看看这篇博客：【C++】树和二叉树的实现（上）-CSDN博客

非完全二叉树：取到空结点后，队列中只剩下的结点一定存在非空结点。

完全二叉树：取到空结点后，队列中剩下的结点不可能存在非空结点。

代码实例：

//Tree.h
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

//Tree.c
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头，出队头BTNode* top = QueueFront(&q);QueuePop(&q);if (top==NULL){break;}//队头结点的左右孩子入队列QueuePop(&q, top->left);QueuePop(&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;
}

八、完整代码

//Tree.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义链式结构二叉树
typedef char 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 BinaryTreeleveIksize(BTNode* root, int k);
//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);
//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
//二叉树的销毁
void BinaryTreeDestory(BTNode** root);
//层序遍历
void LeveIorder(BTNode* root);
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

//Tree.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
#include"Queue.h"
//前序遍历-根左右
void preOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c ", root->data);preOrder(root->left);preOrder(root->right);
}
//中序遍历——左根右
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}postOrder(root->left);printf("%c ", root->data);postOrder(root->right);
}
//后序遍历——左右根
void postOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}postOrder(root->left);postOrder(root->right);printf("%c ", 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 BinaryTreeleveIksize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeleveIksize(root->right, k - 1) + BinaryTreeleveIksize(root->left, k - 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);
}
//二叉树查找值为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;
}
//二叉树的销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}
//层序遍历--队列
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);}}QueueDestroy(&q);
}
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头，出队头BTNode* top = QueueFront(&q);QueuePop(&q);if (top==NULL){break;}//队头结点的左右孩子入队列QueuePop(&q, top->left);QueuePop(&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;
}

//Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义结点的结构
typedef int 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 QueueDestroy(Queue* pq);
//入队——队尾
void QueuePush(Queue* pq, QDataType x);
//出队——队头
void QueuePop(Queue* pq); 
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType* QueueBack(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//队列有效元素个数
int QueueSize(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;
}//队列的销毁
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;
}//入队——队尾
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");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->phead);pq->phead = pq->ptail = NULL;}else{QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}//取队头数据
QDataType QueueFront(Queue* pq)
{assert(!QueueEmpty(pq));return pq->phead->data;
}//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(!QueueEmpty(pq));return pq->ptail->data;
}//队列有效元素个数
int QueueSize(Queue* pq)
{return pq->size;
}

完！！！