树是一种非线性的数据结构,它是由n(n>=0)个有限节点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一个倒挂的树,也就是说它是根朝上,而叶子朝下。它具有的特点:
【注意】:树形结构中,子树间不能有交集,否则就不是树形结构
节点的度:一个节点含有子树的个数称为该节点的度;如下图:A的度为2 树的度:一棵树中,所有的节点度的最大值称为树的度;如下图:树的度为3 叶子节点或终端节点:度为0的节点称为叶子节点;如下图:G、H、I、J、F节点为叶子节点 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;如下图:A是B的父节点 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;如下图:B是A的孩子节点 根节点:一棵树中,没有双亲节点的节点;如下图:A 节点的层次:从根节点定义来,根为第1层,根的子节点为第2层,以此类推 树的高度:树中节点的最大层次;如下图:树的高度为4
树的以下概念只需了解,知道是什么意思即可: 非终端节点或分支节点:度不为0的节点;如下图:B、C、D、E节点为分支节点 兄弟节点:具有相同父节点的节点互称为兄弟节点;如下图:B、C是互为兄弟节点 堂兄弟节点:双亲在同一层的节点互为堂兄弟节点;如下图:D、E是互为堂兄弟节点 节点的祖先:从根到该节点所经分支上的所有节点;如下图:A是所有节点的祖先 子孙:以某个节点为根的子树中任一节点都称为该节点的的子孙。如下图:所有的接地那都是A的子孙 森林:由m(m>=0)棵互不相交的树组成的集合称为森林
树的结构相对线性表就比较复杂了,要存储不是起来就比较麻烦了,实际中树有很多种表示方式,如:双亲表示法,孩子表示法,孩子双亲表示法,孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法
线性结构与树形结构的对比
线性结构 | 树形结构 |
---|---|
第一个数据元素:无前驱 | 根节点:无双亲,唯一 |
最后一个数据元素:无后继 | 叶节点:无孩子,可以多个 |
中间元素:一个前驱,一个后继 | 中间节点:一个双亲多个孩子 |
文件系统管理(目录和文件)
二叉树是n(n>=0)个节点的有限集合,该集合或者空集(空二叉树),或者由一个根节点和两颗互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
从上图可以看出:
总结:对于任意的二叉树都是由以下几种情况复合而成的
大自然中的二叉树:
二叉树的存储结构分为:顺序存储和类似于链表的链式存储 二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方法有孩子表示法和孩子双亲表示法,具体如下:
在学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树的结构掌握还不够深入,为了降低学习成本,此处手动创建一颗二叉树,快速进入二叉树的学习。
注意:上诉代码并不是创建二叉树的方式。 回顾一下二叉树的概念:
从概念可以看出:二叉树的定义是递归式的,因此后续的基本操作中都是按照该概念实现的。
学习二叉树的结构,最简单的方式就是遍历,所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如:打印节点内容、节点内容加1)。 遍历是二叉树上最重要的操作之一,是二叉树上进行其它运算之基础。
前序遍历的顺序: 根节点-> 左子树 -> 右子树 遍历演示 :
代码 :
中序遍历的顺序: 左子树 -> 根结点 -> 右子树 遍历演示:
代码 :
后序遍历的顺序: 左子树 -> 右子树 -> 根结点
代码:
测试代码:
运行结果: