概念
树是n(n>=0)个结点的有限集合
-
结点: 包括一个数据元素及若干其指向的元素的信息
-
结点的度: 一个结点的子树个数
-
结点的层次: 根结点的层次为1,结点的直接后继层次加1
-
分支结点: 度不为0的结点
-
叶结点: 度为0的结点
-
树的度: 树中所有结点度的最大值
-
树的高度(深度): 树中结点层次的最大值
-
森林: m(m>=0)颗互不相交的树组成
-
有序树: 结点的孩子结点之间是有顺序的
二叉树
树的度小于3的有序树
-
满二叉树:深度为k,有2k-1个结点的二叉树
-
完全二叉树: 深度为k,除第k层其余层的结点都满,且第k层的结点集中在左侧
用二叉列表存放二叉树
typedef struct Node
{
DataType data;
struct Node *LChild;
struct Node *RChild;
}BiTNode,*BiTree;