二叉树的练习

这篇具有很好参考价值的文章主要介绍了二叉树的练习。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

单值二叉树

单值二叉树,可以使用等式的传递性来解决,根的值和左右子树的值相比较,看是否相等。再比较左右子树。递归求出是否为单值二叉树。
代码如下:

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

检查两颗树是否相同

先比比较根,在比较左右子树。

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 _isSymmetric(struct TreeNode* RootLeft,struct TreeNode* RootRight)
{
    if(RootLeft == NULL&&RootRight == NULL)
    {
        return true;
    }
    if(RootLeft == NULL ||RootRight == NULL)
    {
        return false;
    }
    if(RootLeft->val != RootRight ->val)
    {
        return false;
    }
    return _isSymmetric(RootLeft->left,RootRight->right) && 
    _isSymmetric(RootLeft->right,RootRight->left);
}
bool isSymmetric(struct TreeNode* root){
    return _isSymmetric(root->left,root->right);
}

二叉树的前序遍历

前序遍历到数组中,注意下标的传值要使用传址调用

int BTreeSize(struct TreeNode* root)
{
  if(root == NULL)
  {
    return 0;
  }
  int lcount = BTreeSize(root->left);
  int rcount = BTreeSize(root-> right);
  return lcount + rcount + 1;
  
}
void _preorderTraversal(struct TreeNode* root,int* a,int* i)
{
  if(root==NULL)
  {
    return;
  }
  a[(*i)++] = root->val;
  _preorderTraversal(root->left,a,i);
  _preorderTraversal(root->right,a,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = BTreeSize(root);
    //malloc一个数组
    int* a = (int*)malloc(sizeof(int)*(*returnSize));
    //执行前序遍历
    //下标
    int i  = 0;
    _preorderTraversal(root,a,&i);
    return a;
}

二叉树的中序遍历

调换这几条语句的顺序
a[(*i)++] = root->val; _preorderTraversal(root->left,a,i); _preorderTraversal(root->right,a,i);
函数名要保证和对应的遍历相同

 int BTreeSize(struct TreeNode* root)
{
  if(root == NULL)
  {
    return 0;
  }
  int lcount = BTreeSize(root->left);
  int rcount = BTreeSize(root-> right);
  return lcount + rcount + 1;
  
}
void _inorderTraversal(struct TreeNode* root,int* a,int* i)
{
  if(root==NULL)
  {
    return;
  }
 
  _inorderTraversal(root->left,a,i);
   a[(*i)++] = root->val;
  _inorderTraversal(root->right,a,i);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = BTreeSize(root);
    //malloc一个数组
    int* a = (int*)malloc(sizeof(int)*(*returnSize));
    //执行前序遍历
    //下标
    int i  = 0;
    _inorderTraversal(root,a,&i);
    return a;  
}

二叉树的后序遍历

与上题相同

  int BTreeSize(struct TreeNode* root)
{
  if(root == NULL)
  {
    return 0;
  }
  int lcount = BTreeSize(root->left);
  int rcount = BTreeSize(root-> right);
  return lcount + rcount + 1;
  
}
void _postorderTraversal(struct TreeNode* root,int* a,int* i)
{
  if(root==NULL)
  {
    return;
  }
 
  _postorderTraversal(root->left,a,i);
  _postorderTraversal(root->right,a,i);
   a[(*i)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
     *returnSize = BTreeSize(root);
    //malloc一个数组
    int* a = (int*)malloc(sizeof(int)*(*returnSize));
    //执行前序遍历
    //下标
    int i  = 0;
    _postorderTraversal(root,a,&i);
    return a;  
}

另一颗树的子树

二叉树的练习

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))
    {
        return true;
    }
    
    return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

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

#include <stdio.h>
#include <stdlib.h>
typedef struct BTNode
{
	char data;
	struct BTNode* left;
	struct BTNode* right;
}BTNode;

BTNode* BuyNode(char x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc failed!\n");
		return NULL;
	}
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}
BTNode* BinaryTreeCreate(char* a,int* pi)
{
    if(a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
	//创建根节点
	BTNode* root = BuyNode(a[*pi]);
	(*pi)++;
	root->left = BinaryTreeCreate(a,pi);
	root->right = BinaryTreeCreate(a,pi);
	return root;
}
void InOrder(BTNode* root)
{
    if(root==NULL)
    {
        return;
    }
    InOrder(root->left);
    printf("%c ",root->data);
    InOrder(root->right);
}
int main() {
    int* a = (int*)malloc(sizeof(int)*100);
	scanf("%s",a);
	int pi = 0;
	BTNode* root = BinaryTreeCreate(a,&pi);
	InOrder(root);
}

判断二叉树是否是完全二叉树

二叉树的练习

//判断是否为完全二叉树
bool BTreeComplete(BT* root)
{
	//新建一个队列
	Que q;
	QueueInit(&q);
	//把root入队列
	QueuePush(&q, root);
	//队列不为空时继续遍历
	while (!QueueEmpty(&q))
	{
		//出队列
		BT* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		//带入左右子树
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	while (!QueueEmpty(&q))
	{
		BT* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)   //遇到不为空证明不是完全二叉树
		{
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true;  //程序执行到这一步时,证明为完全二叉树
}

层序遍历

二叉树的练习

//二叉树的层序遍历
void LevelOrder(BT* root)
{
	//新建一个队列
	Que q;
	QueueInit(&q);
	//把root入队列
	QueuePush(&q, root);
	//队列不为空时继续遍历
	while (!QueueEmpty(&q))
	{
		//出队列
		BT* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		//带入左右子树
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	QueueDestory(&q);
}

k层节点数

// 二叉树第k层节点个数
int BTreeLevelKSize(BT* root, int k)
{
	assert(k > 0);
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1; 
	}
	int left = BTreeLevelKSize(root->left, k - 1);
	int right = BTreeLevelKSize(root->right, k - 1);
	return left + right;
}

二叉树的销毁

递归展开图
二叉树的练习文章来源地址https://www.toymoban.com/news/detail-514468.html

void BTDestory(BT* root)
{
	if (root == NULL)
	{
		return;
	}
	//先销毁左树,然后销毁右树,然后再销毁根
	BTDestory(root->left);
	BTDestory(root->right);
	free(root);
}

二叉树的整体

#include "Tree.h"
#include "Queue.h"
int BTreeLeafSize(BT* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
	
}
int BTreeSize(BT* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int lcount = BTreeSize(root->left);
	int rcount = BTreeSize(root->right);
	return lcount + rcount + 1;
}
int BTreeHeight(BT* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftheight = BTreeHeight(root->left);
	int rightheight = BTreeHeight(root->right);
	//return leftheight > rightheight ? leftheight + 1: rightheight + 1;0
	return 1 + (leftheight > rightheight ? leftheight : rightheight);
}

BT* BTreeFind(BT* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BT* left = BTreeFind(root->left, x);
	if (left)
	{
		return left;
	}
	BT* right = BTreeFind(root->right, x);
	if (right)
	{
		return right;
	}
	return NULL;
}

BT* BuyNode(BTDataType x)
{
	BT* node = (BT*)malloc(sizeof(BT));
	if (node == NULL)
	{
		perror("malloc failed!\n");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
BT* BTCreate()
{
	BT* node1 = BuyNode(1);
	BT* node2 = BuyNode(2);
	BT* node3 = BuyNode(3);
	BT* node4= BuyNode(4);
	BT* node5= BuyNode(5);
	BT* node6 = BuyNode(6);
	//BT* node7 = BuyNode(7);


	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;
}

//二叉树的遍历
//先序遍历
void Prevorder(BT* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->data);
	Prevorder(root->left);
	Prevorder(root->right);
}
//中序遍历
void Inorder(BT* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	Inorder(root->left);
	printf("%d ", root->data);
	Inorder(root->right);
}
//后序遍历
void Postorder(BT* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	Postorder(root->left);
	Postorder(root->right);
	printf("%d ", root->data);
}

// 二叉树第k层节点个数
int BTreeLevelKSize(BT* root, int k)
{
	assert(k > 0);
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1; 
	}
	int left = BTreeLevelKSize(root->left, k - 1);
	int right = BTreeLevelKSize(root->right, k - 1);
	return left + right;
}
//二叉树的层序遍历
void LevelOrder(BT* root)
{
	//新建一个队列
	Que q;
	QueueInit(&q);
	//把root入队列
	QueuePush(&q, root);
	//队列不为空时继续遍历
	while (!QueueEmpty(&q))
	{
		//出队列
		BT* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		//带入左右子树
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	QueueDestory(&q);
}

//判断是否为完全二叉树
bool BTreeComplete(BT* root)
{
	//新建一个队列
	Que q;
	QueueInit(&q);
	//把root入队列
	QueuePush(&q, root);
	//队列不为空时继续遍历
	while (!QueueEmpty(&q))
	{
		//出队列
		BT* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		//带入左右子树
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	while (!QueueEmpty(&q))
	{
		BT* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)   //遇到不为空证明不是完全二叉树
		{
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true;  //程序执行到这一步时,证明为完全二叉树
}
void BTDestory(BT* root)
{
	if (root == NULL)
	{
		return;
	}
	//先销毁左树,然后销毁右树,然后再销毁根
	BTDestory(root->left);
	BTDestory(root->right);
	free(root);
}

到了这里,关于二叉树的练习的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五)

      目录 一,单值二叉树 题目详情: 解法:父子比较法 解题思路: 思路实现: 源代码: 二,相同的树 题目详情: 解法:比较法 解题思路: 思路实现: 源代码: 三,翻转二叉树 解法:替换法 解题思路: 思路实现: 源代码: 题目详情: 如果 二叉树 每个节点都具有 相

    2024年02月07日
    浏览(68)
  • 二叉树的练习

    单值二叉树,可以使用等式的传递性来解决,根的值和左右子树的值相比较,看是否相等。再比较左右子树。递归求出是否为单值二叉树。 代码如下: 先比比较根,在比较左右子树。 先比较根的左右子树的根。在比较左子树的左和右子树的右,左子树的右和右子树的左 前序

    2024年02月11日
    浏览(30)
  • 二叉树的遍历+基础练习

    前面完全二叉树适合存放数据,又因为它在内存中连续存储,因此用顺序表来实现它,并介绍了堆排序及TOP-K问题。 今天我们了解一下二叉树的遍历问题,并完成几道二叉树基础练习 目录 二叉树的遍历 先序 访问顺序: 图示:  中序 访问顺序: 图示: 后序 访问顺序: 图示

    2024年02月09日
    浏览(40)
  • PTA练习4.2 平衡二叉树的根 (25 分)

    题干 将给定的一系列数字插入初始为空的AVL树,请你输出最后生成的AVL树的根结点的值。 输入格式: 输入的第一行给出一个正整数N(≤20),随后一行给出N个不同的整数,其间以空格分隔。 输出格式: 在一行中输出顺序插入上述整数到一棵初始为空的AVL树后,该树的根结点

    2023年04月08日
    浏览(33)
  • 算法练习第13天|递归实现 144.二叉树的前序遍历(opens new window)145.二叉树的后序遍历(opens new window)94.二叉树的中序遍历

    二叉树的存储方式:链式存储和顺序存储。链式存储用指针,顺序存储用数组。其结构如下图所示。 链式存储: 顺序存储: 顺序存储时,若父节点下表为i,则其左孩子下标为 2*i + 1,右孩子下标为2*i + 2. 二叉树主要有两种遍历方式: 深度优先遍历:先往深走,遇到叶子节点

    2024年02月22日
    浏览(51)
  • 每天一道算法练习题--Day15 && 第一章 --算法专题 --- -----------二叉树的遍历

    二叉树作为一个基础的数据结构,遍历算法作为一个基础的算法,两者结合当然是经典的组合了。很多题目都会有 ta 的身影,有直接问二叉树的遍历的,有间接问的。比如要你找到树中满足条件的节点,就是间接考察树的遍历,因为你要找到树中满足条件的点,就需要进行遍

    2024年02月01日
    浏览(48)
  • 二叉树OJ题目合集(单值、对称、平衡、构建加遍历)

    目录 前言: 一:单值二叉树 二:二叉树遍历 核心点 (1)前序 (2)中序 (3)后序 三:判断两颗树是否相同 四:判断二叉树是否对称 五:判断一颗树是否为另一颗树的子树 六:平衡二叉树 七:二叉树的构建加遍历 这一部分适合已经 适用于已经掌握二叉树基础的同学(遍历,求节

    2024年02月02日
    浏览(37)
  • 二叉树的概念|满二叉树与完全二叉树|二叉树的性质|二叉树的存储结构

    在数据结构中树的用途其实并不大,用得更多的其实是二叉树。所以在本章我们将详细讲解二叉树。 一颗二叉树是结点的一个 有限集合 ,该集合: 或者为空 或者由一个根节点加上两颗(互不相交)别称为左子树和右子树的二叉树组成 如图我们可知, 二叉树的特点: 二叉

    2024年01月21日
    浏览(44)
  • 【二叉树part01】| 二叉树的递归遍历、二叉树的迭代遍历、二叉树的统一迭代遍历

    目录 ✿二叉树的递归遍历❀ ☞LeetCode144.前序遍历 ☞LeetCode145.二叉树的后序遍历  ☞LeetCode94.二叉树的中序遍历  ✿二叉树的迭代遍历❀  ☞LeetCode144.前序遍历  ☞LeetCode145.二叉树的后序遍历   ☞LeetCode94.二叉树的中序遍历  ✿二叉树的统一迭代遍历❀   ☞LeetCode144.前序遍

    2024年02月09日
    浏览(38)
  • day16 二叉树的最大深度 n叉树的最大深度 二叉树的最小深度 完全二叉树的节点数

    题目链接:104 二叉树的最大深度 题意 二叉树的根节点是root,返回其最大深度(从根节点到最远叶子节点的最长路径上的节点数) 递归 根节点的的高度就是二叉树的最大深度  所以使用后序遍历求最大高度的方式求出最大深度 递归三部曲 1)确定递归函数的参数和返回值

    2024年02月02日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包