【数据结构】树与二叉树总结（一）

【数据结构】树与二叉树的总结（一）

1.AVL树：动态平衡二叉树（树表的查找）
2.哈夫曼树：二叉树的应用
3.树，树与二叉树的转换
4.*分裂树
5.S=(K,R) 注：K为结点，R为关系

一.树

定义：

n（n>=0）个结点构成的有限集合。当n=0时，称为空树，对于任意一棵非 空树，有以下性质：

A.树中有一个称为“根（Root）”的特殊结点，用r表示

B.其余结点可以分为m个互不相交的有限集T1,T2,T3…Tm，其中每一个结合本 身又是一棵树，称为原来树的“子树”（subTree）

说明：
1.子树是不相交的
2.除了根结点以外，每个结点有且仅有一个父结点
3.一个N结点的二叉树有N-1条边

注释：树是保证结点连通的最小的接通方式

关于树的一些基本语言：

Top1:
a.结点的度：结点子树的个数。
b.树的度：树所有结点中最大的个数。
c.叶结点（leaf）：度为0的结点。
d.父结点（parent）：有子树的结点是其子树根结点的父结点。
e.子节点（child）：