【数据结构】二叉树的链式结构,二叉树的遍历,求节点个数以及高度

2024-09-02 15:20

本文主要是介绍【数据结构】二叉树的链式结构,二叉树的遍历,求节点个数以及高度,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1. 二叉树链式结构的概念

2. 二叉树的遍历

2.1 前序遍历

2.2 中序遍历

2.3 后序遍历

2.4 层序遍历

3. 二叉树的节点个数以及高度

3.1 二叉树节点个数

3.2 二叉树叶子节点个数

3.3 二叉树的高度

3.4 二叉树第k层节点个数

3.5 二叉树查找值为x的节点

4.  二叉树的创建和销毁

4.1 二叉树的销毁

4.2 通过前序遍历的数组构建二叉树

4.3 判断是否是完全二叉树

5. 编程题

5.1 相同的树

5.2 单值二叉树

5.3 对称二叉树

5.4 二叉树的前序遍历

5.5 另一棵树的子树

6. 选择题


1. 二叉树链式结构的概念

由空树,根节点,根的左子树,根的右子树组成。


2. 二叉树的遍历

2.1 前序遍历

访问根结点的操作发生在遍历其左右子树之前(根左右)。当根节点为NULL时返回。

1 2 3 N N N 4 5 N N 6 N N(空可以省略)

1. 先访问根节点,然后访问根的左子树。

2. 如果根的左子树不为空就把左子树的第一个节点作为根继续往下。

3. 左子树访问完后就访问右子树。

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

2.2 中序遍历

访问根结点的操作发生在遍历其左右子树之中(左根右)。当根节点为NULL时返回。

N 3 N 2 N 1 N 5 N 4 N 6 N(N可以省略) 

1. 先访问根节点的左子树。

2. 将左子树的第一个节点作为根节点继续访问根的左子树。

3. 当左子树为空就返回访问根,然后访问根的右子树。

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

2.3 后序遍历

访问根结点的操作发生在遍历其左右子树之后

N N 3 N 2 N N 5 N N 6 4 1

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

2.4 层序遍历

1. 要借助队列。

2. 每个队列节点里面的数据是二叉树节点的指针。

3. 第一步,一开始,当二叉树根节点不为空就入队列。

4. 第二步,当队列不为空就不断出队列,并带入队头数据的左右节点,前提是他们不为空。

void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);//一开始,当二叉树根节点不为空就入队列。if (root != NULL) QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if(front->left != NULL) QueuePush(&q, front->left);if(front->right != NULL) QueuePush(&q, front->right);}printf("\n");QueueDestroy(&q);
}

3. 二叉树的节点个数以及高度

3.1 二叉树节点个数

1. 返回右子树的节点个数和左子树的节点个数并加上自己。

2. 遇到空节点返回0。

int BinaryTreeSize(BTNode* root)
{//遇到空节点返回0。if (root == NULL) return 0;//返回右子树的节点个数和左子树的节点个数并加上自己。return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;	 
}

3.2 二叉树叶子节点个数

1. 找自己的左子树和右子树。

2. 找到叶子就返回1。

int BinaryTreeLeafSize(BTNode* root)
{//空节点返回0if (root == NULL) return 0;//找到叶子就返回1。if (root->left == NULL && root->right == NULL) return 1;//找自己的左子树和右子树。return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

3.3 二叉树的高度

1. 遇到空节点返回0。

2. 返回左右子树较大值,并加1也就是加上自己。

int BTHeight(BTNode* root)
{//遇到空节点返回0。if (root == NULL) return 0;//返回左右子树较大值,并加1也就是加上自己。int lefthigh = BTHeight(root->left);int righthigh = BTHeight(root->right);return max(lefthigh, righthigh) + 1;
}

3.4 二叉树第k层节点个数

思路:对于第一层是找第k层,对于第二层是找k-1层,对于第k层就是找当前层,不断让子树去找,每下去一层k就减一,当k==1时就是第k层。

1. k必须大于0。

2. 遇到空节点返回0。

3. 当k == 1返回1。

4. 继续找左右子树。

int BinaryTreeLevelKSize(BTNode* root, int k)
{//1. k必须大于0。assert(k > 0);//2. 遇到空节点返回0。if (root == NULL) return 0;//3. 当k == 1返回1。if (k == 1) return 1;//4. 继续找左右子树。return BinaryTreeLevelKSize(root->left, k-1) + BinaryTreeLevelKSize(root->right, k-1);
}

3.5 二叉树查找值为x的节点

1. 遇到值相等就返回该节点,遇到空节点就返回空。

2. 先判断根节点的值是否等于x,如果等于就返回根节点,不等于就找自己的左右子树。

3. 记录左右子树的结果,谁找到了就返回,都没找到就返回空。

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

4.  二叉树的创建和销毁

4.1 二叉树的销毁

1. 利用后序的思想,先释放左子树再释放右子树最后释放自己。

2. 在函数外置空,调用的人自己置空。

void BinaryTreeDestory(BTNode* root)
{if (root == NULL) return;BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);
}

4.2 通过前序遍历的数组构建二叉树

链接:二叉树遍历_牛客题霸_牛客网

1. 用%s接收字符串。

2. 利用前序思想构建二叉树,将当前数组下标对应的值作为根的值构建节点,然后数组下标加一,再然后就去构建他的左子树和右子树。

3. 遇到#代表是空,下标加一然后返回空。

#include <stdio.h>typedef char BTDataType;
typedef struct BTNode
{BTDataType data;struct BTNode* left;struct BTNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc");return NULL;}node->data = x;node->left = node->right = NULL;return node;
}BTNode* Insert(char* arr, int* pi)
{if(arr[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = BuyNode(arr[*pi]);(*pi)++;root->left = Insert(arr, pi);root->right = Insert(arr, pi);return root;
}void InOrder(BTNode* root)
{if(root == NULL) return;InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}int main() 
{char arr[100];scanf("%s", arr);int i = 0;BTNode* root = Insert(arr, &i);InOrder(root);return 0;
}

4.3 判断是否是完全二叉树

1. 完全二叉树每一层都是连续的

2. 利用层序遍历的思想,将二叉树节点作为数据插入队列,遇到数据为空就结束遍历。

3. 判断队列剩下的数据有无非空,全都是空证明是连续的,有非空证明不连续。

bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if(root != NULL) 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)){ if (QueueFront(&q) != NULL){QueueDestroy(&q);return false;}QueuePop(&q);}QueueDestroy(&q);return true;
}

5. 编程题

5.1 相同的树

链接:. - 力扣(LeetCode)

思路:分治子问题。

1. 根节点值相等就比较他们的左子树和右子树。

2. 根节点值不相等直接返回false。

3. 接下来比结构,同时走到空意味着前面的结构和值是相等的,一个为空一个不为空证明结构不相等。 

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{if(p == NULL && q == NULL) return true;if(p == NULL || q == NULL) return false;if(p->val != q->val) return false;return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

5.2 单值二叉树

链接:. - 力扣(LeetCode) 

思路:

1. 将根节点和自己的左右孩子比较,注意左右孩子可能为空。

2. 相等则往下交给自己的左右子树。

bool isUnivalTree(struct TreeNode* root) 
{if(root == NULL) return true;if(root->left != NULL && root->val != root->left->val) return false;if(root->right != NULL && root->val != root->right->val) return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}

5.3 对称二叉树

链接: . - 力扣(LeetCode)

思路:

1. 根节点的左右子树要形成镜像对称。

2. 需要写一个子函数去比较左右子树是否对称。

3. 左子树的左边和右子树的右边对应,左子树的右边和右子树的左边对应。

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{if(p == NULL && q == NULL) return true;if(p == NULL || q == NULL) return false;if(p->val != q->val) return false;return isSameTree(p->left, q->right) && isSameTree(p->right, q->left);
}bool isSymmetric(struct TreeNode* root) 
{return isSameTree(root->left, root->right);    
}

5.4 二叉树的前序遍历

链接: . - 力扣(LeetCode)

思路:

1. 题目给个returnSize代表节点的个数。需要自己求。

2. 利用求的节点个数开空间。

3. 再写一个子函数进行前序遍历,将根值放入数组中,下标要传址。

void _preorderTraversal(struct TreeNode* root, int* ret, int* i)
{if(root == NULL) return;ret[(*i)++] = root->val;_preorderTraversal(root->left, ret, i);_preorderTraversal(root->right, ret, i);
}int Size(struct TreeNode* root)
{if(root == NULL) return 0;else return 1 + Size(root->left) + Size(root->right);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{*returnSize = Size(root);int* tmp = (int*)malloc(sizeof(int)*(*returnSize));int i = 0; _preorderTraversal(root, tmp, &i);return tmp;
}

5.5 另一棵树的子树

链接: . - 力扣(LeetCode)

思路:

1. 遍历root,将root每个节点和subroot比较。

2. 注意,遍历到空意味着前面的比较都不相等。subroot也不可能为空。

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{if(p == NULL && q == NULL) return true;if(p == NULL || q == NULL) return false;if(p->val != q->val) return false;return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{if(root == NULL) return false;if(isSameTree(root, subRoot) == true) return true;return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot); 
}

6. 选择题

1.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH 。则该完全二叉树的前序序列为()

A. ABDHECFG

B. ABCDEFGH

C. HDBEAFCG

D. HDEBFGCA

答:A

2.二叉树的先序遍历和中序遍历如下:先序遍历:EFHIGJK; 中序遍历:HFIEJKG.则二叉树根结点为()

A. E

B. F

C. G

D. H

答:A

3.设一课二叉树的中序遍历序列:badce,后序遍历序列:bdeca,则二叉树前序遍历序列为____。

A. adbce

B. decab

C. debac

D. abcde

答:D

4.某二叉树的后序遍历序列与中序遍历序列相同,均为 ABCDEF ,则按层次输出(同一层从左到右)的序列为

A. FEDCBA

B. CBAFED

C. DEFCBA

D. ABCDEF 

答:A

这篇关于【数据结构】二叉树的链式结构,二叉树的遍历,求节点个数以及高度的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1130329

相关文章

使用Java实现通用树形结构构建工具类

《使用Java实现通用树形结构构建工具类》这篇文章主要为大家详细介绍了如何使用Java实现通用树形结构构建工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录完整代码一、设计思想与核心功能二、核心实现原理1. 数据结构准备阶段2. 循环依赖检测算法3. 树形结构构建4. 搜索子

利用Python开发Markdown表格结构转换为Excel工具

《利用Python开发Markdown表格结构转换为Excel工具》在数据管理和文档编写过程中,我们经常使用Markdown来记录表格数据,但它没有Excel使用方便,所以本文将使用Python编写一... 目录1.完整代码2. 项目概述3. 代码解析3.1 依赖库3.2 GUI 设计3.3 解析 Mark

mysql通过frm和ibd文件恢复表_mysql5.7根据.frm和.ibd文件恢复表结构和数据

《mysql通过frm和ibd文件恢复表_mysql5.7根据.frm和.ibd文件恢复表结构和数据》文章主要介绍了如何从.frm和.ibd文件恢复MySQLInnoDB表结构和数据,需要的朋友可以参... 目录一、恢复表结构二、恢复表数据补充方法一、恢复表结构(从 .frm 文件)方法 1:使用 mysq

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》:本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句(1)条件语句的定义(2)条件语句的语法(a)单分支 if(b)双分支 if-else(

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

使用Navicat工具比对两个数据库所有表结构的差异案例详解

《使用Navicat工具比对两个数据库所有表结构的差异案例详解》:本文主要介绍如何使用Navicat工具对比两个数据库test_old和test_new,并生成相应的DDLSQL语句,以便将te... 目录概要案例一、如图两个数据库test_old和test_new进行比较:二、开始比较总结概要公司存在多

java获取图片的大小、宽度、高度方式

《java获取图片的大小、宽度、高度方式》文章介绍了如何将File对象转换为MultipartFile对象的过程,并分享了个人经验,希望能为读者提供参考... 目China编程录Java获取图片的大小、宽度、高度File对象(该对象里面是图片)MultipartFile对象(该对象里面是图片)总结java获取图片

vue基于ElementUI动态设置表格高度的3种方法

《vue基于ElementUI动态设置表格高度的3种方法》ElementUI+vue动态设置表格高度的几种方法,抛砖引玉,还有其它方法动态设置表格高度,大家可以开动脑筋... 方法一、css + js的形式这个方法需要在表格外层设置一个div,原理是将表格的高度设置成外层div的高度,所以外层的div需要

C++中使用vector存储并遍历数据的基本步骤

《C++中使用vector存储并遍历数据的基本步骤》C++标准模板库(STL)提供了多种容器类型,包括顺序容器、关联容器、无序关联容器和容器适配器,每种容器都有其特定的用途和特性,:本文主要介绍C... 目录(1)容器及简要描述‌php顺序容器‌‌关联容器‌‌无序关联容器‌(基于哈希表):‌容器适配器‌:(

Java中switch-case结构的使用方法举例详解

《Java中switch-case结构的使用方法举例详解》:本文主要介绍Java中switch-case结构使用的相关资料,switch-case结构是Java中处理多个分支条件的一种有效方式,它... 目录前言一、switch-case结构的基本语法二、使用示例三、注意事项四、总结前言对于Java初学者