第六章树和二叉树dsjiaoxue@126
1树的定义和基本术语6
3遍历二叉树和线索二叉树6
4树和森林6
5树和等价问题6
6哈夫曼树及其应用6
8树的计数本章小结习题第六章树和二叉树dsjiaoxue@126
com定义：树(tree)是n(n≥0)个结点的有限集，在任一棵非空树中：1）有且仅有一个特定的称为树根(root)的结点；2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)
例如：特点：1）在非空树中至少有一个结点—根2）树中各子树是互不相交的集合6
1树的定义和基本术语第六章树和二叉树dsjiaoxue@126
com例如:A(a)ABCDEFGHIJMKL(b)只有根结点的树根子树有子树的树第六章树和二叉树dsjiaoxue@126
comADTTree{数据对象D：D是具有相同特性的数据元素的集合
数据关系R：若D为空集，则称为空树；若D中仅含一个数据元素，则关系R为空集；否则R={H}，H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}≠⌽，则存在D-{root}的一个划分D1,D2,D3,…,Dm(m>0),即对于任意的j≠k(1≤j,k≤m)有Dj∩Dk=⌽，且对任意的i=1,2,…,m
惟一存在数据元素xi∈Di,有∈H；抽象数据类型树的定义如下：第六章树和二叉树dsjiaoxue@126
com树：无向树（无环的无向连通图）有向树（若不考虑孤的方向时是一棵无向树）根树（有且只有一个入度为0的结点根），其余结点入度为1
书上讲的为根树基本术语：(3)对应于D-{root}的以上划分，H-{,,…,}有惟一的一个划分H1,H2,H3,…,Hm(m>0),即对于任意的j≠k(1≤
