第6章树主要内容6
1树的定义和基本术语6
2树的链式存储结构6
3树的顺序存储结构6
4K叉树6
5树知识点总结6
1树和森林6
2森林与二叉树的等价转换6
3树的抽象数据类型6
4树的周游6
1树的定义和基本术语6
1树和森林树(tree)是包括n个结点的有限集合T（n≥1），使得：有且仅有一个特定的称为根(root)的结点
除根以外的其它结点被分成m个(m≥0)不相交的有限集合T1，T2，…，Tm，而每一个集合又都是树
其中树T1，T2，…，Tm称作这个根的子树(subtree)
1树和森林图6
1树形表示法ABCDEFGHIJKL6
1树和森林树的逻辑结构可以这样描述：树是包含n个结点的有穷集合K(n>0)，且在K上定义了一个满足以下条件的二元关系R={r}：有且仅有一个结点k0K∈，它对于关系r来说没有前驱
结点k0称作树的根
除结点k0外，K中的每个结点对于关系r来说都有且仅有一个前驱
除结点k0外的任何结点kK∈，都存在一个结点序列k0，k1，…，ks，使得k0就是树根，且ks=k，其中有序对R∈（1≤i≤s）
这样的结点序列称为从根k0到结点k的一条路径
树形结构的各种表示法树的逻辑结构是：结点集合K={A，B，C，D，E，F，G，H，I，J}K上的关系N={，，，，，，，，}树结构中的概念在一棵树中，若存在结点k指向结点k’的连线，则称k是k’的父结点，而k’则是k的子结点，有向连线称作边
同一个父结点的子结点之间互称兄弟
树中没有父结点的结点称为根
没有子结点的结点称为树叶
结点的子树数目称为结点的度，树的度是树中各结点度的最大值，二叉树的度是2
树结构中的概念若树中存在结点序列k0，k1，…，ks，使得，，…，都是树中的边，则称从结点k0到结点ks存在一条路径
若有一条由k到达k
