树和二叉树基础

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

引言:

树是一种非线性的结构,也是由一个一个的结点构成。

树的一些基本概念:

树和二叉树基础,数据结构,C语言,算法,数据结构,c语言

节点的度:一个节点含有的子树的个数称为该节点的度;如上图:A的度为6

叶节点或终端节点:度为0的节点称为叶节点。

非终端节点或分支节点:度不为0的节点;

双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点。

孩子节点或子节点:如B是A的子节点。

兄弟节点:具有相同父节点的节点互称为兄弟节点

树的度:一棵树中,最大的节点的度称为树的度

节点的层次:从根开始定义,根为第一层,根的子节点是第二层,以此类推。

树的高度或深度:树中节点的最大层次,如上图:树的高度是4.(注意从1开始计数,同时也意味着空树就是0

树的表示

左孩子右兄弟表示法:

树和二叉树基础,数据结构,C语言,算法,数据结构,c语言

注意孩子结点表示的是第一个孩子节点,兄弟结点也是第一个兄弟结点。

这是最优的二叉树表示方法。

用此方法表示A的所有孩子结点:

树和二叉树基础,数据结构,C语言,算法,数据结构,c语言

二叉树概念及结构

概念:

  • 每个结点最多有两颗子树,即二叉树不存在度大于2 的节点。
  • 二叉树的子树有左右之分,其子树的次序不能颠倒。、

二叉树的定义

因为孩子最多有两个,所以直接定义左孩子,右孩子即可。

二叉树的前、中、后序

树和二叉树基础,数据结构,C语言,算法,数据结构,c语言

树和二叉树基础,数据结构,C语言,算法,数据结构,c语言

首先需要明确任何一个二叉树分为3个部分:

  1. 根节点
  2. 左子树
  3. 右子树

注意左子树和右子树都是一个整体,然后从这个整体中再细分根节点、左子树、右子树。

前序(先根):根 左子树 右子树

中序:左子树 根 右子树

后序:左子树 右子树 根

这个前中后的顺序是根据根的位置而决定的

树和二叉树基础,数据结构,C语言,算法,数据结构,c语言

下面是前、中、后序的原码(利用递归去求解)

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

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

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

特殊的二叉树

树和二叉树基础,数据结构,C语言,算法,数据结构,c语言

  1. 满二叉树:一个二叉树,如果每一个层的结点树都达到最大值,就称为满二叉树
  2. 完全二叉树:就是在满二叉树的基础上,前h-1层都是满的,但是最后一层不满,但是最后一层从左往右都是连续的。

二叉树的性质

  1. 如果规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1)个结点。
  2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点个数(也就是满二叉树的个数)是2^h-1
  3. 对任何一棵二叉树,如果度为0的叶节点的个数为n0,度为2的分支结点的个数为n2,则有n0 = n2+1.
  4. 若规定根节点的层数为1,具有n个结点的二叉树的深度h = LogN。

根据二叉树的性质进行解题

例题1:

树和二叉树基础,数据结构,C语言,算法,数据结构,c语言

由二叉树的性质3得到叶节点的个数是度为2的分支结点个数+1,所以直接199+1 = 200即可。

例题2:

树和二叉树基础,数据结构,C语言,算法,数据结构,c语言

选择题快速法:

直接假设n = 2,接着进行带入计算,与每个选项进行比较得到正确答案。

常规解法:

设未知数,度为0的结点个数有X0个,度为1的结点个数有X1个,度为2的结点个数有X2个.

就会得到X0+X1+X2 = 2n.

又因为X0和X2的关系X2+1 = X0.

又因为是一个完全二叉树所以度为1结点的个数要么是1要么是0,所以分两种情况,发现当X1 = 1时计算结果是小数,不符合题意,所以X1 = 0得出答案。

例题3:

树和二叉树基础,数据结构,C语言,算法,数据结构,c语言

解答:

假设这棵树的高度是h,假设最后一层缺了X个

树和二叉树基础,数据结构,C语言,算法,数据结构,c语言

本题也是将选择题的答案带到题目中进行比较,然后得出正确答案。

如何求一棵二叉树中结点的个数?

解法一:

采用循环遍历的思想

遍历这棵树的每一个结点,如果不是空,就size++,否则不进行++。

注意运用这种方法时,因为可能需要计算多颗树的结点,所以每次传参时,需要传一个新的size地址,在主函数中直接打印输出size的值

原码:
void TreeSize(BTNode* root,int* psize)//直接传地址
{
	if (root == NULL)
		return;
	else
	{
		(*psize)++;
		TreeSize(root->left, psize);
		TreeSize(root->right, psize);
	}
}

解法二:

采用分治的思想。

何为分治的思想,就是将一个比较复杂的问题进行一层一层的分解,直到分解到简单的层次。将大问题分解为小问题。

例如校长想要统计整个学校的人数,校长将这个任务分配给院长,院长再分配给每个班的班主任,每个班主任再分配给每个宿舍的宿舍长。

本题思路也是如此,统计整棵树的结点个数,将这颗树分为左子树和右子树,左子树再分为小的左子树和小的右子树,层层递归,直到最后一层加1。

原码:

int TreeSize(BTNode* root)
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
	/*if (root == NULL)
		return 0;
	else
	{
		return TreeSize(root->left) + TreeSize(root->right) + 1;
	}*/
}

如何求二叉树叶子节点的个数?

按照上面分支的思想,咱们举一反三~

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

TIP:

只需要给出中序+任何一个前序或者后序,就可以将一个完整的二叉树还原出来

原因:

前序和中序都是知道根节点是哪个,但是并不知道左子树和右子树。

如果有了中序后,并且已知根节点,那么在中序排列中,在根节点的左边就是左子树,在根节点的右边就是右子树,就可以轻松将树还原出来。

关于二叉树的一些经典例题

例题1:二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣(LeetCode)

题目描述:

树和二叉树基础,数据结构,C语言,算法,数据结构,c语言

注意事项:

利用递归的思想去进行前序遍历,注意在递归时,计数器一般需要传址,防止局部变量出生命周期就自动销毁。

假设计数器用全局变量,是不行的。

因为函数接口会被多次调用,全局变量会一直累加

原码:

//提前计算好树的结点的个数,方便创建动态数组的个数
int TreeSize(struct TreeNode* root)
{
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

void _PrevOrder(struct TreeNode* root,int* arr,int* pcnt)
{
    //前序递归遍历,将遍历的结点存储到动态数组中
    if(root == NULL)
        return;
    arr[*pcnt] = root->val;
    (*pcnt)++;
    _PrevOrder(root->left,arr,pcnt);
    _PrevOrder(root->right,arr,pcnt);
}


int* preorderTraversal(struct TreeNode* root, int* returnSize){

    int size = TreeSize(root);
    int* arr = (int*)malloc(sizeof(int) * size);
    int cnt = 0;
    //注意传地址,递归调用一般需要传址操作
    _PrevOrder(root,arr,&cnt);
    *returnSize = cnt;
    return arr;
}

例题二:二叉树的最大深度

104. 二叉树的最大深度 - 力扣(LeetCode)

题目描述:

树和二叉树基础,数据结构,C语言,算法,数据结构,c语言

解题思路:

同样采用分治的思想,求二叉树的最大深度,就是求左子树和右子树的最大深度,接着继续分治,求左子树中的小左子树和小右子树的最大深度,直到不可分解进行+1即可

原码:

int maxDepth(struct TreeNode* root){
    if(root == NULL)
        return 0;
    int leftmax = maxDepth(root->left) + 1;
    int rightmax = maxDepth(root->right) + 1;
    return leftmax > rightmax ? leftmax : rightmax;
}

例题3:判断平衡二叉树

110. 平衡二叉树 - 力扣(LeetCode)

题目描述:

树和二叉树基础,数据结构,C语言,算法,数据结构,c语言

解题思路:

本题要求二叉树的每一个结点都要满足左右两个子树的高度差的绝对值不超过1,所以先判断头结点的左右子树是否满足,如果头结点都不满足,那么直接就返回false

如果头结点满足,则继续向下递归左右子树的结点是否满足。文章来源地址https://www.toymoban.com/news/detail-689282.html

原码:

int MaxDepth(struct TreeNode* root)
{
    if(root == NULL)
        return 0;
    int leftDepth = MaxDepth(root->left);
    int rightDepth = MaxDepth(root->right);
    return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1;
}

bool isBalanced(struct TreeNode* root){
    if(root == NULL)
        return true;
    //先判断头结点,接着再判断子节点
    int leftDepth = MaxDepth(root->left);
    int rightDepth = MaxDepth(root->right);
    return  abs(leftDepth-rightDepth) < 2 && isBalanced(root->left) && isBalanced(root->right);
}

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

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

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

相关文章

  • 【数据结构】树和二叉树——堆

    目录 🍉一.树的概念及结构🍉 1.树的概念 2.树的相关术语 3.树的表示 4.树在实际中的应用 🍊二.二叉树的概念和结构🍊 1.二叉树的概念  2.特殊的二叉树 2.1.满二叉树 2..2.完全二叉树 3.二叉树的性质 4.二叉树的存储结构          4.1.顺序存储 4.2.链式存储 🍎三.堆的顺序结构

    2023年04月14日
    浏览(47)
  • 【数据结构】树和二叉树概念

    树是一种 非线性 的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 有一个 特殊的结点,称为根结点 ,根节点没有前驱结点 除根节点外, 其余结点被分成M(M0)个互不相交

    2024年02月09日
    浏览(40)
  • 【Java 数据结构】树和二叉树

    篮球哥温馨提示:编程的同时不要忘记锻炼哦! 目录 1、什么是树? 1.1 简单认识树  1.2 树的概念  1.3 树的表示形式 2、二叉树 2.1 二叉树的概念 2.2 特殊的二叉树 2.3 二叉树的性质 2.4 二叉树性质相关习题 3、实现二叉树的基本操作 3.1 了解二叉树的存储结构 3.2 简单构造一棵

    2024年01月16日
    浏览(45)
  • 【数据结构之树和二叉树】

    前言: 前篇学习了 数据结构的栈和队列,那么这篇继续学习树及其相关内容基础内容。 / 知识点汇总 / 概念 :树是一种非线性结构,是由有限个节点组成的具有层次关系的集合。倒立的树模样。 有一个特殊的结点,称为根节点,根节点没有前驱。 另外的子树有且只有一个

    2024年01月16日
    浏览(55)
  • 数据结构之树和二叉树

    目录 一、树简介 二、二叉树 1、简介 2、二叉树的性质 3、满二叉树和完全二叉树  三、二叉树的遍历 四、二叉树遍历代码实现 五、二叉搜索树(Binary Search Tree) 1、简介 2、二插搜索树的局限性 六、平衡二叉搜索树(AVL树) 七、红黑树(Red-Black Tree) 1、简介 2、性质 3、使

    2024年02月05日
    浏览(40)
  • 【数据结构】树和二叉树的概念及结构

      树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 有一个 特殊的结点,称为根结点 ,根节点没有前驱结点。 除根节点外, 其余结点被分成M(M0)个互不相

    2024年02月13日
    浏览(39)
  • 数据结构之树和二叉树定义

      数据结构是程序设计的重要基础,它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发,分析和研究计算机加工的数据的特性,以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法,为提高利用

    2024年01月21日
    浏览(50)
  • 【数据结构】——树和二叉树的相关习题

    1、设高度为h的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为(),最多为()。 A、h ;2 h -1 B、2h-1 ; 2 h -1 C、2h+1; 2 h-1 -1 D、h+1;2 h -1 解析: (B) 最少的情况下,除了根结点该层为1个结点以外,其余h-1层都有2个结点,得2(h-1),即2(h-1)+1=2h-1。

    2024年02月03日
    浏览(44)
  • 数据结构期末复习(4)串 树和二叉树

    在数据结构中,串是由零个或多个字符组成的有限序列。它是一种线性数据结构,常用于表示和处理文本、字符串等信息。 串的特点包括: 顺序性:串中的字符按照一定的先后顺序排列,每个字符都有一个唯一的位置。 有限性:串的长度是有限的,它由字符的个数决定。

    2024年01月17日
    浏览(47)
  • 数据结构从入门到精通——树和二叉树

    树和二叉树是计算机科学中常用的数据结构,它们在数据存储、搜索、排序等多个领域都有着广泛的应用。从简单的二叉树出发,我们可以逐步理解更复杂的树结构,如红黑树、AVL树等。 二叉树是一种每个节点最多有两个子节点的树结构,通常子节点被称为“左子节点”和“

    2024年03月15日
    浏览(101)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包