树 & 二叉树基本概念
文章中部分内容和思路来自《数据结构、算法与应用 c++语言描述》
简单树
1.定义
一棵树t是一个非空的有限元素集合,其中一个元素为根(root),其余元素(如果有的话)组成t的子树(subtree)
2.元素(节点)间的关系
比较简单(直观),一笔带过:
Joe和Ann,Mary,John是父子关系
Mary,Ann和John是兄弟关系
Joe和Chris祖孙关系
3.树术语
级:树根是一级(Joe),其孩子是2级(Ann,Mary,John),孩子的孩子是三级(Mark,Sue,Chris),以此类推。[特别说明:有人认为级从0开始编号]
高度/深度:一个树级的个数,图一所示简单树为三级树,高度为3
度:元素的度指其孩子的个数,如Joe的度为3,一棵树的度是其所有元素的度中的最大值,图一所示简单树的度为3
二叉树
1.定义
一颗二叉树(binary tree)t是有限个元素的集合(可以为空)。当二叉树非空时,其中有一个元素称为根,余下的元素(如果有的话)被划分为两颗二叉树,分别称为t的左子树和右子树
2.与简单树的区别
3.简单应用
4.二叉树特性
- 一颗二叉树有n个元素,n>0,则它有n-1条边
- 一颗二叉树高度为h,h>=0,则它至少有h个元素,至多有2<sup>h</sup>-1个元素
- 一颗二叉树有n个元素,n>0,他的高度最大为n,最小为log<sub>2</sub>(n+1)
5.满二叉树
高度为h的二叉树刚好有2<sup>h</sup>-1个元素则为满二叉树,如图
6.完全二叉树
对高度为h的满二叉树的元素,从第一层到最后一层,在每一层中从左到右编号,从1到2<sup>n</sup>-1如图11-6,假设从满二叉
树中删除k个编号为2<sup>n</sup>-i元素,1<=i<=k<2<sup>h</sup>,所得到的二叉树称为完全二叉树。[ps:这个定义貌似比较难理解QAQ,看看百度百科上的定义(若设二叉树的深度为h,除第
h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树)]如图:
特性:
假设完全二叉树的一元素编号为i,1<=i<=n。则以下关系成立:
- 如果i=1,则该元素为根,否则其父元素为i/2
- 如果2i>n,则该元素无左孩子,否则,其左孩子为2i
- 如果2i+1>n,则该元素无右孩子,否则,其右孩子为2i+1