[C语言]树和二叉树
分类:
文章
•
2022-10-26 18:29:04
树
由一个或多个节点组成的有限集合,有且仅有一个节点称为根(root),当节点数大于1时,其余节点分为m个互不相交的有限集合,每个集合本身又是一颗树,被称作这个根的子树
树的结构特点
- 非线性结构,至多有一个直接前驱,但可能有多个直接后继
- 树的定义具有递归性,树中还有树
- 树可以为空,即节点个数为0
上图中树的节点数:13
树的度:3
树的深度:4
若干术语:
- 根:即根节点(没有前驱)
- 叶子:即终端节点(没有后继)
- 森林:指m棵不相交的树的集合
- 有序树:节点各字数从左至右有序,不能互换
- 无序树:节点各子树可以互换位置
- 节点的度:节点挂接的子树数(直接后继的数量)
- 树的度:所有节点度的最大值
- 树的深度(高度):指所有节点中最大的层数
二叉树
定义:n(n>=0)个节点的有限集合,由一个根节点以及两棵互不相交的,分别称为左子树和右子树的二叉树组成
基本特征:
- 每个节点最多有两棵子树(不存在度大于2的节点)
- 左子树和右子树次序不能颠倒(有序树)
性质:
- 在二叉树第i层至多由2^(i-1)个结点(i>0)
- 深度为K的二叉树,至多有2 ^ k-1个节点(有2^k-1个结点的二叉树称为满二叉树)
完全二叉树:除最后一层外其他节点都为满节点,且最后一层只有右边缺少若干节点
对于完全二叉树,若从上至下,从左至右编号,则编号为i的结点,其左孩子编号必为2i,其右孩子编号必为2i+1,其双亲编号必为i/2(i=1为根节点时除外)
如何确定一棵二叉树
通过中序遍历和先序遍历可以确定一棵树
通过中序遍历和后序遍历可以确定一棵树
通过先序遍历和后序遍历不能确定一棵树