链式二叉树（数据结构）——C语言

news/2024/10/31 12:19:15/

1.链式二叉树

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

typedef int BTDataType;// ⼆叉链
typedef struct BinaryTreeNode{struct BinTreeNode* left; // 指向当前结点左孩⼦struct BinTreeNode* right; // 指向当前结点右孩⼦BTDataType val; // 当前结点值域}BTNode;

⼆叉树的创建⽅式⽐较复杂，为了讲述⼆叉树内容中，我们先⼿动创建⼀棵链式⼆叉树

BTNode* buynode(BTDataType x)
{BTNode*node= (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail!");exit(1);}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->left = NodeE;NodeC->right = NodeF;return NodeA;
}

⼆叉树分为空树和⾮空⼆叉树，⾮空⼆叉树由根结点、根结点的左⼦树、根结点 的右⼦树组成的，根结点的左⼦树和右⼦树分别⼜是由⼦树结点、⼦树结点的左⼦树、⼦树结点的右⼦树组成的，因此⼆叉树定义是递归式的,后序链式⼆叉树的操作中基本都是按照该概念实现的。

2.各种函数的实现

这里还是一样，先建立三个文件，Tree.h，Tree.c，tect.c，分别为头文件，函数实现文件，和测试文件，注意这里后面树的层序遍历，和判断是否为完全二叉树，这两个函数会用到队列的数据结构，所以还要用到之前写的Queue.c，Queue.h。

Tree.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include"Queue.h"typedef  char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;void PrevOrder(BTNode*root);
void InOrder(BTNode*root);
void PostOrder(BTNode*root);int BinaryTreeSize(BTNode* root);
int BinaryTreeLeafSize(BTNode* root);
int BinaryTreeLevelKSize(BTNode* root, int k);
int BinaryTreeDepth(BTNode* root);BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
void BinaryTreeLevelOrder(BTNode* root);
bool BinaryTreeComplete(BTNode* root);

2.1 前中后序遍历

2.1.1前序遍历void PrevOrder(BTNode*root)

void PrevOrder(BTNode*root)
{if (root == NULL){printf("NULL ");return ;}printf("%c ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}

这里利用递归，直到到空结点，就回退，首先打印根节点，然后找left结点，left节点再去找接下来的left结点直到left的空节点，每向下一次就打印一次，到空节点回退到上一层，再看right结点，到空节点回退到上一层，左右都回退后再返回上一层，重复到根节点为止。

结果：

2.1.2中序遍历void InOrder(BTNode* root)

void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}

这里和前序遍历逻辑一样，只是printf打印的时候，在left结点回退回来后，再打印。

结果：

2.1.3后序遍历void PostOrder(BTNode* root)

void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}

这里和前序遍历逻辑一样，只是printf打印的时候，在left结点和right结点都回退回来后，再打印。

结果：

2.2树节点的个数int BinaryTreeSize(BTNode* root)

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

这里计算结点个数，也是利用递归，return中的1是表示每次递归根节点，然后去寻找左右节点，直到空节点返回0，当左右结点的都为NULL，return返回1+0+0，也就是表示一个结点，再向上递归，直到回退到根节点那个函数里。

2.3叶子结点个数int BinaryTreeLeafSize(BTNode* root)

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

这里统计叶子结点的个数，（度为0的结点是叶子结点），根据这个性质，去寻找左右结点为空节点的结点，就是叶子结点，从根节点开始递归直到到空节点。

2.4第K层结点个数int BinaryTreeLevelKSize(BTNode* root, int 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);
}

找第K层，每向下一层就K-1，直到找到K==1，也就是找到了第K层，然后找到任意一个左右节点且K==1就返回1直到回退到根节点。

2.5寻找结点BTNode* BinaryTreeFind(BTNode* root, BTDataType x)

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode*leftleaf=BinaryTreeFind(root->left, x);if (leftleaf){return leftleaf;}BTNode*rightleaf=BinaryTreeFind(root->right, x);if (rightleaf){return rightleaf;}return NULL;
}

这里寻找，数据为x的节点，找到直接返回root，为空就返回NULL，注意这里返回的要用一个BTNode*leftleaf保存是否在根节点左边是否找到，BTNode*rightleaf保存是否在根节点右边是否找到，然后递归回退到根节点的那个函数，判断保存的是否为空，有一个就说明找到了，直接返回，反之，返回空。

2.6树的深度int BinaryTreeDepth(BTNode* root)

int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int maxleft =BinaryTreeDepth(root->left);int maxright =BinaryTreeDepth(root->right);return 1 +( maxleft > maxright ? maxleft : maxright);
}

这里也要记录左右结点的个数，返回更大的为深度，这里return中的1为是根节点的那一层，向下直到空结点，然后回退到根节点，比较左右深度大小，找到更大的为深度。

2.6层序遍历void BinaryTreeLevelOrder(BTNode* root)

void BinaryTreeLevelOrder(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);
}

这里要使用到队列这个数据结构，首先建一个队列，先将根节点放进队列中，然后判断队列是否为空，不为空，就出队，如果入队结点的左右结点，不为空就入队，直到队列为空，就完成了层序遍历。

结果：A B C D E F

2.7判断是否为完全二叉树bool BinaryTreeComplete(BTNode* root)

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);}while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);if (top != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

（完全二叉树：最后一个节点的上面所有层的结点的度都为2）这里和层序遍历相同，要用到队列，先建一个队，将根节点入队，以队列为空作为停止循环的条件，出队，如果判断该节点为空，直接跳出循环，不为空，将左右节点入队，这里不需要判断是否为空，空也直接入队，因为这里出队到空会直接跳出循环，跳出循环后，继续出队，如果找到为不为空，说明在空节点，后面还有数据结点，就不是完全二叉树，如果直到出队完，未找到数据结点，说明wield完全二叉树。

3.整体代码

注意：这里之前队列实现，用的数据类型为int，这里要改成BTNode类型，还要注意前置声明因为队列中要使用到定义的树的结构体，所以要用到前置声明。

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//typedef int DataType;
typedef struct BinaryTreeNode* DataType;typedef struct QueueNode
{DataType 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, DataType x);
//出队列--队头
void QueuePop(Queue* pq);//取队头数据
DataType QueueFront(Queue* pq);
//取队尾数据
DataType QueueBack(Queue* pq);//队列判空
bool QueueEmpty(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);

Queue.c

#include"Queue.h"
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}QueueNode* BuyNode(DataType x)
{QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}
void QueuePush(Queue* pq, DataType x)
{assert(pq);QueueNode*newnode= BuyNode(x);if (pq->phead ==NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;
}void QueuePop(Queue* pq)
{assert(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--;	
}DataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}DataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead==NULL;
}int QueueSize(Queue* pq)
{return pq->size;
}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;pq->size = 0;
}

Tree.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include"Queue.h"typedef  char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;void PrevOrder(BTNode*root);
void InOrder(BTNode*root);
void PostOrder(BTNode*root);int BinaryTreeSize(BTNode* root);
int BinaryTreeLeafSize(BTNode* root);
int BinaryTreeLevelKSize(BTNode* root, int k);
int BinaryTreeDepth(BTNode* root);BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
void BinaryTreeLevelOrder(BTNode* root);
bool BinaryTreeComplete(BTNode* root);

Tree.c

#include"Tree.h"void PrevOrder(BTNode*root)
{if (root == NULL){printf("NULL ");return ;}printf("%c ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%c ", root->data);InOrder(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);
}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);
}BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode*leftleaf=BinaryTreeFind(root->left, x);if (leftleaf){return leftleaf;}BTNode*rightleaf=BinaryTreeFind(root->right, x);if (rightleaf){return rightleaf;}return NULL;
}int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int maxleft =BinaryTreeDepth(root->left);int maxright =BinaryTreeDepth(root->right);return 1 +( maxleft > maxright ? maxleft : maxright);
}void BinaryTreeLevelOrder(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;}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;
}

tect.c

#include"Tree.h"
BTNode* buynode(BTDataType x)
{BTNode*node= (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail!");exit(1);}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->left = NodeE;NodeC->right = NodeF;return NodeA;
}void test()
{BTNode*root=CreatBinaryTree();PrevOrder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");int size = BinaryTreeSize(root);printf("size=%d\n", size);int leafsize=BinaryTreeLeafSize(root);printf("leafsize=%d\n",leafsize);int lk= BinaryTreeLevelKSize(root, 2);printf("第2层结点为：%d\n", lk);BTNode*ret=BinaryTreeFind(root, 'G');if (ret == NULL){printf("未找到\n");}else{printf("找到了\n");}int depth = BinaryTreeDepth(root);printf("depth=%d\n", depth);BinaryTreeLevelOrder(root);printf("\n");if (!BinaryTreeComplete(root)){printf("非完全二叉树");}else{printf("完全二叉树");}
}int main()
{test();return 0;
}


http://www.ppmy.cn/news/1543337.html

相关文章

Linux 命令行学习：数据流控制、文本处理、文件管理与自动化脚本 （第二天）

Linux 命令行学习：数据流控制、文本处理、文件管理与自动化脚本 （第二天）

目标&#xff1a;掌握更多命令行技巧和文本处理工具。 1. 管道和重定向 &#xff08;1&#xff09;输入输出重定向 输出重定向 (>)&#xff1a;将命令的输出写入到文件中&#xff0c;如果文件存在&#xff0c;则覆盖。 演示 &#xff1a; 输入重定向&#xff08;<&a…
阅读更多...
打造厨艺交流平台：Spring Boot开发全攻略

打造厨艺交流平台：Spring Boot开发全攻略

2 相关技术 2.1 Spring Boot框架简介 Spring Boot是由Pivotal团队提供的全新框架&#xff0c;其设计目的是用来简化新Spring应用的初始搭建以及开发过程。该框架使用了特定的方式来进行配置&#xff0c;从而使开发人员不再需要定义样板化的配置。通过这种方式&#xff0c;Sprin…
阅读更多...
便捷之选：微信小程序驱动的停车场管理系统

便捷之选：微信小程序驱动的停车场管理系统

作者介绍&#xff1a;✌️大厂全栈码农|毕设实战开发&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。 &#x1f345;获取源码联系方式请查看文末&#x1f345; 推荐订阅精彩专栏 &#x1f447;&#x1f3fb; 避免错过下次更新 Springboot项目精选实战案例 更多项目…
阅读更多...
YARN集群优化：专家不告诉你的事

YARN集群优化：专家不告诉你的事

标签概念 YARN中,可以通过给节点打标签(Node Labels)来实现物理隔离。每个节点可以关联一个或多个标签,每个标签代表了节点的某种特性或分组。在提交应用程序时,可以指定应用程序需要运行在具有特定标签的节点上,从而实现不同应用在集群节点间的物理隔离。 操作步骤 具体步骤…
阅读更多...
海外媒体发稿：如何打造媒体发稿策略

海外媒体发稿：如何打造媒体发稿策略

新闻媒体的发稿推广策略对于提升品牌知名度、吸引流量以及增加收入非常重要。本文将介绍一套在21天内打造爆款新闻媒体发稿推广策略的方法。 第一天至第七天&#xff1a;明确目标和定位 在这个阶段&#xff0c;你需要明确你的目标和定位&#xff0c;以便为你的新闻媒体建立一个…
阅读更多...
yarn 下载安装、下载依赖、通过 vscode 运行服务（Windows11）

yarn 下载安装、下载依赖、通过 vscode 运行服务（Windows11）

目录 yarn工具前置要求&#xff1a;安装node.js并配置好国内镜像源下载安装下载依赖特别的&#xff1a; 启动服务 yarn 工具 系统&#xff1a;Windows 11 前置要求&#xff1a;安装node.js并配置好国内镜像源 参考&#xff1a;本人写的《node.js下载、安装、设置国内镜像源…
阅读更多...
css 元素高度从0过度到auto的两种方案

css 元素高度从0过度到auto的两种方案

1.使用display: grid; 和 grid-template-rows: 0fr; <div class"item"><div class"grid"><div><ul class"ulAA" v-if"menuGroup.gongsijieshao.child.length > 0 "><li v-for"item in menuGroup.…
阅读更多...
node.js下载、安装、设置国内镜像源（永久）（Windows11）

node.js下载、安装、设置国内镜像源（永久）（Windows11）

目录 node-v20.18.0-x64工具下载安装设置国内镜像源&#xff08;永久&#xff09; node-v20.18.0-x64 工具 系统&#xff1a;Windows 11 下载 官网https://nodejs.org/zh-cn/download/package-manager 版本我是跟着老师选的node-v20.18.0-x64如图选择 Windows、x64、v20.18…
阅读更多...
最新文章

Copyright @ 2022~2023