树和二叉树的基本知识

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

一、树的概念及结构

1.树的概念

树是一种 非线性 的数据结构,它是由 n n>=0 )个有限结点组成一个具有层次关系的集合。 把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的
有一个 特殊的结点,称为根结点 ,根节点没有前驱结点。
除根节点外, 其余结点被分成 M(M>0) 个互不相交的集合 T1 T2 …… Tm ,其中每一个集合 Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有 0 个或多个后继。
因此, 树是递归定义 的。
注意:树形结构中,子树之间不能有交集,否则就不是树形结构

2.相关概念

树和二叉树的基本知识,数据结构,数据结构,c语言

节点的度:一个节点含有的子树个数称为该节点的度。如上图:根节点A的度为5

叶节点/终端节点:度为0的节点称为叶节点。如上图:B、D、G、I、K、L、M、N、O均为叶节点

分支节点/非终端节点:度不为0的节点。如上图:C、E、F、H、J为分支节点

双亲节点或父节点 :若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图: A B 的父节点
孩子节点或子节点 :一个节点含有的子树的根节点称为该节点的子节点; 如上图: B A 的孩子节点
兄弟节点 :具有相同父节点的节点互称为兄弟节点; 如上图: B C 是兄弟节点
树的度 :一棵树中,最大的节点的度称为树的度; 如上图:树的度为5
节点的层次 :从根开始定义起,根为第 1 层,根的子节点为第 2 层,以此类推
树的高度或深度 :树中节点的最大层次; 如上图:树的高度为 4
节点的祖先 :从根到该节点所经分支上的所有节点;如上图: A 是所有节点的祖先
子孙 :以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是 A 的子孙
森林 m m>0 )棵互不相交的树的集合称为森林

3.树的表示

实际中树的表示方法有很多种,最常用的是链式存储结构的孩子兄弟表示法:

typedef int DataType;
struct Node
{
 struct Node* _firstChild; // 指向其第一个孩子结点
 struct Node* _Brother; // 指向其兄弟结点
 DataType _data; // 结点中的数据域
};

例如,上图的部分节点表示如下:

树和二叉树的基本知识,数据结构,数据结构,c语言

4.树的性质

①设度为i的节点个数为,则对于一颗度为m的树,其总节点个数N = 树和二叉树的基本知识,数据结构,数据结构,c语言

②所有节点的度之和树和二叉树的基本知识,数据结构,数据结构,c语言

二、二叉树的概念

1.概念

一棵二叉树是结点的一个有限集合,该集合 :
1. 或者为空
2. 或者 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
从定义可以看出,二叉树的度小于等于2,即不存在度大于2的节点。因此,任意一颗二叉树都是由以下几种情况复合而成的:
树和二叉树的基本知识,数据结构,数据结构,c语言
注意:二叉树≠度为2的树:二叉树的度可以为0/1/2,但度为2的树的度必须为2,即度为2的树必须存在度为2的节点,而二叉树没有此限制。

2.特殊的二叉树

满二叉树 :一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。
也就是说,如果一个二叉树的层数为K ,且结点总数是,则它就是满二叉树。
完全二叉树 :完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为 K的,有n 个结点的二叉树,当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 n 的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树
树和二叉树的基本知识,数据结构,数据结构,c语言

3.二叉树的性质

①若规定根节点的层数为 1 ,则一棵非空二叉树的 i 层上最多有 个结点
若规定根节点的层数为 1 ,则 深度为 h 的二叉树的最大结点数是
③由树的性质可知,树和二叉树的基本知识,数据结构,数据结构,c语言树和二叉树的基本知识,数据结构,数据结构,c语言,联立上式可得树和二叉树的基本知识,数据结构,数据结构,c语言
④若规定根节点的层数为 1 ,具有 n 个结点的满二叉树的深度 树和二叉树的基本知识,数据结构,数据结构,c语言

三、二叉树的存储结构

1.顺序存储

顺序存储就是使用一个数组来存储,顺序存储一般只适用于完全二叉树或近似于完全二叉树,否则会造成较大的空间浪费。现实使用中只有堆才会使用数组存储,关于堆的内容将在下篇博客【堆的实现及应用】讲解。

二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。

树和二叉树的基本知识,数据结构,数据结构,c语言

2.链式存储

二叉树的链式存储结构是指,用链表来表示一颗二叉树,即用链来指示元素的逻辑关系。通常链表中的每个节点由三个域组成:数据域、左指针域、右指针域。其中左右指针域分别给出该节点左孩子和右孩子所在链节点的地址。这种链式结构又叫做二叉链。

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType val;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

树和二叉树的基本知识,数据结构,数据结构,c语言

一颗二叉树可以分为三部分:根节点、左子树、右子树,而左右子树又都是一颗二叉树,可见二叉树的结构具有递归性,因此基于链式存储结构的二叉树算法多数也是递归的,这样代码的可读性更高、容易理解。

(1)二叉树的遍历

二叉树遍历是指按照某种特定规则依次访问二叉树的全部节点,每个节点只访问一次。

遍历是二叉树最重要的算法之一,也是其他算法的基础。

二叉树的遍历可分为四种:

①前序遍历:按照根节点、左子树、右子树的顺序遍历二叉树。如上图,遍历结果为1 2 4 6 5 3

②中序遍历:按照左子树、根节点、右子树的顺序遍历二叉树。如上图,遍历结果为4 6 2 5 1 3

③后序遍历:按照左子树、右子树、根节点的顺序遍历二叉树。如上图,遍历结果为6 4 5 2 3 1

④层序遍历:从根节点开始,自上而下、自左至右逐层访问二叉树的每个节点。如上图,遍历结果为1 2 3 4 5 6

其中,前三种遍历方式均属于递归遍历,第四种为非递归遍历。

下面以前序遍历为例演示递归遍历:

void PreOrder(BTNode* t)
{
	if (t == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", t->val);
	PreOrder(t->left);
	PreOrder(t->right);
}

层序遍历需要借助队列来实现,使用队列保存每个节点的孩子节点,通过不断地入队和出队以此来实现所有节点的访问:(注:有关队列的接口函数均与上篇博客中保持一致)

void LevelOrder(BTNode* t)
{
	Queue qu;
	QueueInit(&qu);
	QueuePush(&qu, t);
	while (!QueueEmpty(&qu))
	{
		BTNode* tmp = QueueFront(&qu);
		QueuePop(&qu);
		printf("%d ", tmp->val);

		if (tmp->left != NULL)
			QueuePush(&qu, tmp->left);
		if (tmp->right != NULL)
			QueuePush(&qu, tmp->right);
	}
}

(2)二叉树的创建和销毁

已知一颗二叉树的某种递归遍历序列,如何构建出对应的二叉树?下面以前序序列为例:(注:子树为空用‘#’表示)

//创建单个节点
BTNode* SingleNode(BTDataType x)
{
	BTNode* _new = (BTNode*)malloc(sizeof(BTNode));
	if (_new == NULL)
	{
		perror("malloc error");
		exit(-1);
	}
	_new->val = x;
	_new->left = NULL;
	_new->right = NULL;

	return _new;
}

//创建二叉树
BTNode* CreateBT(char* a, int* pi)  //pi为遍历序列a的下标,开始为0
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}

	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL)
	{
		perror("malloc error");
		exit(-1);
	}
	root->val = a[(*pi)++]-'0';  //注意数据类型
	
	root->left = CreateBT(a, pi);
	root->right = CreateBT(a, pi);

	return root;
}

二叉树的销毁:

void BTDestroy(BTNode** pt)
{
	BTNode* t = *pt;
	if (t == NULL)
		return;

	BTDestroy(&(t->left));
	BTDestroy(&(t->right));
	free(t);
	*pt = NULL;
}

(3)其他算法

下面列举了一些有关二叉树遍历的其他算法,可以加深对递归遍历和链式结构的理解。当然,这些算法题在各大OJ平台都可以搜到。

①计算二叉树的节点个数:

int TreeNodeSize(BTNode* t)
{
	if (t == NULL)
		return 0;

	return TreeNodeSize(t->left) + TreeNodeSize(t->right) + 1;
}

②计算二叉树叶子节点的个数:

int LeafSize(BTNode* t)
{
	if (t == NULL)
		return 0;
	if (t->left == NULL && t->right == NULL)
		return 1;

	return LeafSize(t->left) + LeafSize(t->right);
}

③计算二叉树的高度:

int TreeHeight(BTNode* t)
{
	if (t == NULL)
		return 0;

	int left = TreeHeight(t->left);
	int right = TreeHeight(t->right);
	return (left > right ? left : right) + 1;
}

④计算第k层的节点个数:

int Size_k(BTNode* t,int k)
{
	if (t == NULL)
		return 0;
	if (k == 1)
		return 1;

	return Size_k(t->left, k - 1) + Size_k(t->right, k - 1);
}

⑤查找值为x的节点:

BTNode* BTFind(BTNode* t, BTDataType x)
{
	if (t == NULL)
		return NULL;
	if (t->val == x)
		return t;

	BTNode* t1 = BTFind(t->left, x);
	if (t1 != NULL)
		return t1;
	else
		return BTFind(t->right, x);
}

⑥判断两棵树是否相同:

bool isSameTree(BTNode* p, BTNode* q) 
{
	if (p == NULL && q == NULL)  //在条件判别时,p==NULL等价于!p
		return true;
	if (p == NULL || q == NULL)
		return false;

	if (p->val != q->val)
		return false;

	bool left = isSameTree(p->left, q->left);
	bool right = isSameTree(p->right, q->right);

	return left && right;
}

⑦翻转二叉树:文章来源地址https://www.toymoban.com/news/detail-834520.html

BTNode* invertTree(BTNode* root) 
{
	if (root == NULL)
		return NULL;

	BTNode* _root = (BTNode*)malloc(sizeof(BTNode*));
	if (_root == NULL)
	{
		perror("malloc error");
		exit(-1);
	}
	_root->val = root->val;
	_root->left = invertTree(root->right);
	_root->right = invertTree(root->left);

	return _root;
}

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

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

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

相关文章

  • 【数据结构】树和二叉树的概念及结构

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

    2024年02月13日
    浏览(37)
  • 初级数据结构(五)——树和二叉树的概念

        文中代码源文件已上传:数据结构源码  -上一篇 初级数据结构(四)——队列        |        初级数据结构(六)——堆 下一篇-         自然界中的树由根部开始向上生长,随机长出分支,分支之上又可长出分支,层层递进,直至长出叶子则此分支结束。   

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

    目录 一,树的概念及结构         1,树的定义         2,树结点的分类及关系         3,树的表示 二,二叉树的概念及结构         1,二叉树的定义         2,特殊的二叉树         3,二叉树的性质         4,二叉树的存储结构 1,顺序存储

    2024年02月10日
    浏览(45)
  • 【数据结构】树和二叉树堆(基本概念介绍)

     🌈个人主页: 秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343 🔥 系列专栏: 《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482 ​​ 目录  前言  树的概念  树的常见名词 树与非树  二叉树 概念 满二叉树和完全二叉树 二叉树的存储结构 顺序存储 链式

    2024年02月01日
    浏览(35)
  • 【数据结构】树,二叉树,满二叉树,完全二叉树的定义和二叉树的基本操作

    🎊专栏【数据结构】 🍔喜欢的诗句:更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【勋章】 大一同学小吉,欢迎并且感谢大家指出我的问题🥰 目录 ⭐树 🏳️‍🌈定义  🏳️‍🌈注意 🍔树的基本术语 ⭐二叉树 🏳️‍🌈定义 🎆二叉树和树的区别 🏳️‍🌈二叉树

    2024年02月05日
    浏览(66)
  • 树和二叉树基础

    树是一种非线性的结构,也是由一个一个的 结点 构成。 节点的度:一个节点含有的子树的个数称为该节点的度;如上图:A的度为6 叶节点或终端节点:度为0的节点称为叶节点。 非终端节点或分支节点:度不为0的节点; 双亲节点或父节点:若一个节点含有子节点,则这个节

    2024年02月10日
    浏览(33)
  • 数据结构---树和二叉树

    树 属于1:n的形式,属于非线性结构 有且仅有一个根,其余的都是子树 而字树也有自己的根和子树,所以,树是一个递归的定义 ![在这里插入图片描述](https://img-blog.csdnimg.cn/677eb0f85d6945028e4fa02b208e06f4.png#pic_center 结点的度:结点拥有的子树的个数,或者是分支的个数,或者是

    2024年02月14日
    浏览(42)
  • 树和二叉树 --- 数据结构

    目录 1.树的概念及结构 1.1树的概念 1.2树的表示 1.3树在实际生活中的运用 2.二叉树的概念及结构  2.1概念 2.2特殊的二叉树 2.3二叉树的性质 2.4二叉树的存储结构 树是一种 非线性 的数据结构,它是由n (n=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为 它看起来

    2024年02月15日
    浏览(44)
  • 数据结构--树和二叉树

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

    2024年02月12日
    浏览(41)
  • 数据结构—树和二叉树

    5.1树和二叉树的定义 树形结构 (非线性结构):结点之间有分支,具有层次关系。 5.1.1树的定义 树(Tree)是n(n≥0)个结点的有限集。 若n=0,称为空树; 若n>0,则它满足如下两个条件: 有且仅有一个特定的称为根(Root)的结点; 其余结点可分为m(m≥0)个互不相交的

    2024年02月14日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包