树说白了也是图的一种特殊形式,在计算机中都是很重要的数据结构.比如压缩算法采用结构的就是哈夫曼树.一些排序算法如堆排序,也是基于树的.二分查找也可以理解成基于树的,是二叉排序树.
1、自由树与森林
就是一个连通的,无环的无向图.称一个可能不连通的无向无环图为森林.
自由树如下:
森林如下:
树和森林都不能有环.
此图因为有环，所以只能叫图,不是树也不是森林.
2、一些性质
令G=(V,E)是一个无向图,下面性质都是等价的
1、G是自由树
2、G中任何两顶点由唯一简单路径相连.
3、G是连通的,但是从图中移除任意一条边得到的图均不连通.
4、G是连通的,且边数等于顶点数减一.
5、G是无环的,且边数等于定点数减一.
6、G是无环的,但是如果向E中添加任何一条边,均会造成图包含一个环.
3、有根树和有序树
有根树是一颗自由树,其顶点中存在一个与其他顶点不同的顶点.此顶点称为树的根.如图:
祖先:就是排在前面的结点,如上图中的3是8和12的祖先,8是6和5的祖先.
后代:就是排在后面的结点,如上图8是3的后代,也是7的后代,7是8的爷爷结点.3是8的父节点,8,12称为兄弟结点.
叶结点:没有孩子的结点称为叶结点,也就是度为0的结点.
树的高度从最后的叶结点计数0向上数到根节点，称为树的高度如上图,从结点9(高度0)开始向上数到7,经过结点5(高度1)，结点8(高度2),结点3(高度3),到根结点7(高度4)
树的深度,从根节点算起深度为0，一直到最后的叶结点深度即为树的深度.如图
根节点7(深度0),结点3(深度1),结点8(深度2),结点5(深度3),结点9(深度4)
4、二叉树与位置树
二叉树定义:一个根节点,一颗称为左子树的二叉树,以及一颗称为右子树的二叉树.二叉树可以为空,即不包含任何结点的二叉树.
满二叉树:在二叉树中不缺失叶结点的树称为满二叉树如图
完全二叉树:
可以理解成从一颗满二叉树的右边叶结点缺少几个叶结点的树.如图
树的基本性质就聊到这里，当然这些只是树的性质中的九牛一毛.以后在基于树的算法中在详谈.下次咱们就开始计数与概率论了.
预览时标签不可点收录于话题#个上一篇下一篇