树和森林

树的存储结构

双亲表示

用一组连续的空间来存储每个结点,同时增加一个伪指针来指向双亲的位置

孩子表示法

将每一个结点的孩子都当长一个线性表,有n个节点就有n个孩子链

孩子兄弟法

又称为 二叉树表示法

左儿子,右兄弟

typedef struct CSNode{
	ElemType data;
	struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;

根据上面的思想,可以将任意树都转成二叉树的形式,然后当作二叉树来处理.

树	森林	对应二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

总结和规律

1. F是森林,B是由F变成的二叉树,若F有个非终端结点,则B中右指针域为空的结点有 ()
2. 一棵树有2011个结点,其叶子节点为116,该树对应的二叉树中无右孩子结点的个数为 1896
3. 将森林转换成对应的二叉树,中叶节点的个数为 T中左孩子指针为空的结点个数