第6章 树和二叉树YL-2011一、树的定义和基本术语二、二叉树三、二叉树的遍历四、线索二叉树五、树和森林六、赫夫曼树及其应用主要内容YL-2011一、树的定义和基本术语1、树的定义（教材P118）树是n（n0）个结点的有限集合。n=0时称为空树。在任意一颗非空树中：（1）有且仅有一个特定的结点被称为根（Root）的结点；（2）当n1时，其余结点被分成m（m0）个互不相交的有限集T1，T2，.，Tm，其中每一集合本身又是一棵树，并且成为根的子树（SubTree）。树的定义是一个递归YL-2011ABC DE F G H I JM K L树根例如:T1T2T3YL-2011结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DH I JM2、基本术语（教材P120）YL-2011孩子:结点子树的根双亲结点、兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：AB C DE F G H I JM K L 假设某结点在第L层,则其子树的根就在第L+1层树中叶子结点所在的最大层次第1层第2层第3层第4层YL-2
