第六章 树和二叉树.doc

树和二叉树
树的类型定义
数据对象D:D是具有相同特性的数据元素的集合。
数据关系R:
若D为空集,则称为空树;
否则:
在D中存在唯一的称为根的数据元素root,
(2) 当n>1时,其余结点可分为m(m>0)个互不相交的有限集 T1, T2, …, Tm, 其中每一棵子集本身又是一棵符合本定义的树,称为根root的子树。
基本操作:
查找:
Root(T); Value(T, cur_e); Parent(T, cur_e);
LeftChild(T, cur_e); RightSibling(T, cur_e);
TreeEmpty(T); TreeDepth(T);
TraverseTree(T, Visit());
插入:
InitTree(&T); CreateTree(&T, definition);
Assign(T, cur_e, value);
InsertChild(&T, &p, i, c);
删除:
ClearTree(&T); DestroyTree(&T);
DeleteChild(&T, &p, i);
DestroyTree(&T);
有向树:
1) 有确定的根;
2) 树根和子树根之间为有向关系
有序树和无序树的区别在于:
子树之间是否存在次序关系?
和线性结构的比较
线性结构树结构
第一个数据元素根结点
(无前驱) (无前驱)
最后一个数据元素多个叶子结点
(无后继) (无后继)
其它数据元素树中其它结点
(一个前驱、一个后继) (一个前驱、多个后继)
基本术语
结点:数据元素+ 若干指向子树的分支
结点的度:分支的个数
树的度:树中所有结点的度的最大值
叶子结点:度为零的结点
分支结点:度大于零的结点
从根到结点的路径:
孩子结点、双亲结点、兄弟结点、
祖先结点、子孙结点
结点的层次:假设根结点的层次为1,
第l层的结点的子树根结点的层次为l+1
树的深度:树中叶子结点所在的最大层次
森林:是m(m≥0)棵互不相交的树的集合
任何一棵非空树是一个二元组
Tree = (root,F)
其中:
root被称为根结点,F被称为子树森林
二叉树的类型定义
二叉树或为空树;或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
二叉树的五种基本形态:
二叉树的主要基本操作:
查找:
Root(T); Value(T, e); Parent(T, e);
LeftChild(T, e); RightChild(T, e);
LeftSibling(T, e); RightSibling(T, e);
BiTreeEmpty(T); BiTreeDepth(T);
PreOrderTraverse(T, Visit());
InOrderTraverse(T, Visit());
PostOrderTraverse(T, Visit());
LevelOrderTraverse(T, Visit());
插入:
InitBiTree(&T); Assign(T, &e, value);
CreateBiTree(&T, definition);
InsertChild(T, p, LR, c);
删除:
ClearBiTree(&T); DestroyBiTree(&T);
DeleteChild(T, p, LR);
二叉树的重要特性:
性质 1 :
在二叉树的第 i 层上至多有2i-1个结点
(i≥1)
性质 2 :
深度为k的二叉树上至多含2k-1个结点
(k≥1)
性质 3 :
对任何一棵二叉树,若他含有n0个叶子结点、n2个度为2的结点,则必存在关系式:
n0 = n2+1
两类特殊的二叉树:
满二叉树:指的是深度为k且含有2k-1个结点的二叉树
完全二叉树:树中所含的n个结点和满二叉树中编号为1至n的结点一一对应
性质 4 :
具有n个结点的完全二叉树的深度为
ëlog2nû+1
性质 5 :
若对含n个结点的二叉树从上到下且从左至右进行1至n的编号,则对二叉树中任意一个编号为
i的结点:
(1) 若i=1,则该结点是二叉树的根,无双亲,
否则,编号为ëi/2û的结点为其双亲结点;
(2) 若2i>n,则该结点无左孩子,
否则,编号为2i的结点为其左孩子结点;
(3) 若2i+1>n,则该结点无右孩子结点,
否则,编号为2i+1的结点为其右孩子结点。
6.