树的概念

1055阅读 0评论2012-09-22 Jiker4836
分类:C/C++

如果将树中结点的各子树看成从左至右是有次序的,不能互换,则称该树为有序树,否则称为无序树。
森林是m(m>=0)棵互不相交的树的集合。
几点的层次从根开始定义起,根为第一层,根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度或者高度。
结点拥有的子树数称为结点的度。度为零的结点称为叶结点或终端结点;度不为零的结点称为非终端结点或者分支结点。除根结点之外,分支及诶单也称为内部结点。树的度是树内各结点的度的最大值。
根节点:无双亲,唯一
叶节点:无孩子,可以多个
中间结点:一个双亲多个孩子
 
二叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
 
二叉树特点:
1、每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点
2、左子树和右子树是有顺序的,次序不能任意颠倒。
3、即使树某结点只有一棵子树,也要区分它是左子树和右子树。
 
五种基本形态:
1、空二叉树
2、只有一个根结点
3、根节点只有左子树
4、根节点只有右子树
5、根节点既有左子树和右子树。
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         
上一篇:栈学习
下一篇:查找