树的基本概念

  • 时间:
  • 浏览:
  • 来源:互联网

  • 概念
    • 树:
    • 树的分类:
    • 树的应用:
    • 专业术语
    • 树的存储

概念

树:

1.有且只有一个称之为的节点;
2.有若干个互不相交的子树,子树本身也是一种树。
通俗定义:

  1. 树是由节点和边组成;
  2. 每个节点只有一个父节点,但可以有多个子节点(根节点除外,他没有父节点)。

抽象数据类型树的定义:

ADT Tree
{
	数据对象D:D是具有相同特性的数据元素的集合。
	数据关系R:若R是空集,则称为空树;
			若D仅含一个数据元素,则R为空集,否则R = {H},
			H是二元关系:父子节点关系。(一个递归的过程)
	基本操作P:
	  InitTree(&T);
	  操作结果:构造空树T。
	  DestroyTree(&T);
	  初始条件:树T存在。
	  操作结果:销毁树T。
	  TreeDepth(&T);
	  初始条件:树T存在。
	  操作结果:返回T的深度。
	  Root(&T);
	  初始条件:树T存在。
	  操作结果:返回T的根。
	  Parent(&T,cur_e);
	  初始条件:树T存在,cur_e是T中某个节点。
	  操作结果:若cur_e是T的非根节点,则返回它的双亲,否则函数值为空。
	  LeftChild(&T,cur_e);
	  初始条件:树T存在,cur_e是T中某个节点。
	  操作结果:若cur_e是T的非叶子节点,则返回它的最左孩子,否则返回“空”。
	  RightSibling(&T,cur_e);
	  初始条件:树T存在,cur_e是T中某个节点。
	  操作结果:若cur_e有右()兄弟,则返回它的右兄弟,否则返回“空”。
	  **注:上面两个函数可以用来把一个普通树转化为二叉树。**
	  TraverseTree(T,Visit());
	  初始条件:树T存在,Visit是对节点操作的应用函数。
	  操作结果:按某种次序(先序、中序、后序)对T的每个节点调用函数
	  visit()一次且至多一次。一旦visit()失败,则操作失败。
	  
}ADT Tree

树的分类:

1.一般树:任意一个节点的子节点的个数不受限制。
2.二叉树:任意一个节点的子节点最多2个,且子节点的位置不可更改。
(有序树)
二叉树分类:
一般二叉树:
满二叉树;
完全二叉树。

3.森林:n个互不相交的树的集合。

树的应用:

1.树是数据库中数据组织的一种重要形式。
2.操作系统子进程和父进程的关系本身就是一棵树。
3.面向对象语言中类的继承关系本身也是一棵树。
4.赫夫曼树

专业术语

1.节点(结点)
2.父节点
3.子节点
4.子孙
5.堂兄弟
6.深度(高度)
7.叶子节点
8.度
9.森林

树的存储

1.顺序存储:用一个数组
2.链式存储:比较常用。
等二叉树再说。

本文链接http://metronic.net.cn/metronic/show-53441.html