树与二叉树概念

树与二叉树概念 树

树形结构是一类重要的非线性数据结构。树是以分支关系定义的层次结构

1.树的定义：树是n(n>=0)个结点的有限集。

2.结点：就是图的顶点。

3.枝：就是图的边。

4.根 ：一颗树可以想象成从某一个顶点开始进行分枝，那么这个顶点就是“根”。一颗树的每一个节点都可以作为根。

5.叶：在一颗树上选定根后，如节点0作为根。由根开始不断分枝，途中所有无法再分枝的节点成为叶。

6.度：一个节点拥有的子树数称为节点的度。

7.层/深度/高度 ：在一颗树中选定根后，按照每个点离根的距离，可以将树中的点分为多个层级。

8.双亲/孩子/兄弟 ：在一颗树中选定根后，相邻的两点，靠近根的是双亲，远一点的是孩子。

9.祖先/后代：在一颗树中选定根后，一个点的双亲、双亲的双亲、……都是此点的祖先，根节点是所有子节点的祖先，注意双亲也属于祖先。因此，祖先是一个集合概念。

10.森林：很多颗树的集合称为森林。森林中，树与树之间互不相交。

​ ①树中所有点都是连通的；

​ ②树中任意2点之间只有唯一一条路径；

​ ③树是无环的连通图；

​ ④森林是无环的非连通图。

二叉树

1.二叉树的特点：

​ 每个结点至多只有两颗子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

2.性质：

​ <1>在二叉树的第i层上至多有2^(i-1)个结点

​ <2>深度为k的二叉树的最大结点数为2^k -1

​ <3>任何一颗二叉树T，如果其终端结点树为n0，度为2的结点数为n2，则有n0=n1+1

​ <4>具有n个结点的完全二叉树深度为[log2 n]+1

3.满二叉树：一颗深度为k，且有2^k -1个结点的二叉树

4.完全二叉树：深度为k，有n个结点的二叉树，当且仅当每个结点都与深度为k的满二叉树中从1至n的结点一一对应

遍历二叉树

1.先序遍历

​ 访问根结点–>先序遍历左子树–>先序遍历右子树

2.中序遍历

​ 中序遍历左子树–>访问根结点–>中序遍历右子树

3.后序遍历

​ 后序遍历右子树–>后序遍历左子树–>访问根结点

例：

按照先序遍历输出顺序为：ABDEHIJKCFG

按照中序遍历输出顺序为：DBHEJIKAFCG

按照后序遍历输出顺序为：DHJKIEBFGCA

4.遍历的性质：

​ 已知前序遍历和中序遍历，可以唯一的确定一个二叉树；
​ 已知后序遍历和中序遍历，可以唯一的确定一个二叉树；

线索二叉树

我们在二叉树上加上两个指针域，为区分左子树和前驱、右子树和后驱，加上两个标志域作以区分

LTag：1 lchild指示结点前驱 RTag：1 rchild指示结点后驱

​ 0 lchild指示结点左孩子 0 rchild指示结点右孩子

这种结构的二叉链表作为二叉树的存储结构，叫做线索链表

指向前驱后继的指针叫做线索

加上线索的二叉树称为线索二叉树