数据结构-树(1)

这是一篇讲述概念的博客,但是如果你能看完,那么恭喜你,你已经知道什么是树了

定义:有且只有一个称为根的节点,有若干个互不相交的子树,这些子树本身也是一棵树。通俗来讲树就是由节点和边组成,一个节点只能有一个父节点,但是可以有多个子节点。根节点没有父节点。

专业术语:

  • 度:节点拥有的子树的个数。如1的度为3;4的度为0
  • 路径:从一个节点顺着边走到另一个节点,所经过的节点的顺序就叫做路径
  • 叶节点:没有子节点的节点称为叶子节点(度为零),简称叶节点,也叫终端节点如4,5,6,7
  • 非叶节点(非终端节点):度不为0
  • 双亲:父节点
  • 子孙:以该节点为根节点的所有节点,如:除了1之外都是1的子孙
  • 兄弟:有相同的的父节点,如:5,6
  • 堂兄弟:父节点是兄弟,如:5和7,6和7
  • 深度:从根节点到最底层节点的层数称为深度,根节点是第一层,深度也叫最大层次,或者高。如:该树深度为3

如果只有一个节点,根节点就是叶子节点,例中就是非叶子,并不是说根节点一定是非叶子节点,并无必然关系。

树的分类

一般的树:对子节点个数没有限制

二叉树(二叉树是一种有序的树):子节点个数最多为两个(有序指的是二叉树的左右子树不可以调换顺序,哪怕只有一个子树,也是有左右之分的,对与二叉树来说下面的两棵树并不相同)


            满二叉树:对于一个k层的二叉树,它有2^k-1个节点,则它就是一个满二叉树。也就是说,在不增加层数的前提下,无法添加新的节点的二叉树。

            

完全二叉树:如果只是删除了满二叉树最底层,最右边的连续若干个节点的二叉树,就是完全二叉树。完全二叉树的特例是满二叉树(因为二叉树有序的缘故,下图中的第一棵树并不是一个完全二叉树)

森林:n个互不相交的树的集合

树的存储

二叉树的存储

  • 连续存储【完全二叉树】
  • 链式存储【用到链表的知识】

一般树的存

  • 连续存储:先转换成一个完全二叉树,然后把非线性的树用线性方式存储(先中后序三种规则)
    为什么要转换成完全二叉树呢?当你只保存红色的节点时,你究竟是以1,2,3,4,5,6的顺序来存储呢,还是以1,2,4,5,6,3的顺序来存储呢。对于二叉树来说,它是一个非线性结构,所以当你要把它以线性方式保存时,哪个节点在前哪个节点在后本身就是不一样的。同时对于一个非完全二叉树,如果我们只用线性方式保存它的有效节点,我们便无法确定这个树的结构究竟是什么样的,也就是说你无法把你存储的线性数据再还原成一个二叉树,比如当你用线性方式存储了1,2,3,4,5.你并不能看出4是3的兄弟?还是子节点?而那些补充上来的节点可以保证原先树的结构在存储后不会消失。
  • 以完全二叉树存储的优点:转化成完全二叉树会但浪费空间,但是它有两个很重要的优点1.知道节点的个数就可以知道树有几层2.已知任何一个节点,你可以知道它的父节点是谁,他有没有子节点,它的子节点是谁
  • 链式存储:每一个节点两个指针域,分别指向左孩子和右孩子
    优点和缺点:它不需要多余的节点,虽然空指针域也会有浪费,但是是一种线性浪费,如果有n个节点它只会有n+1个空指针域,因为n个节点一共有2n个指针域,而除了根节点外的每个节点都要有一个指针域来指向它所以空指针域为2n-(n-1)个。缺点是我们无法找到一个节点的父节点,除非我们再添加一个指针域来指向它的父节点

 

这篇博客就到这里了,在下一篇博客内我会来具体讲述一下如何存储一棵树

有问题欢迎大家提问哦0。0 可以直接评论😂 也可以QQ🤣

数据结构-树(1)》有27个想法

Tzingtao C进行回复 取消回复

邮箱地址不会被公开。 必填项已用*标注