树与森林存储结构脑图思维导图
属于森林的遍历，结论和存储结构内容分解
树图思维导图提供 树与森林存储结构脑图 在线思维导图免费制作，点击“编辑”按钮，可对 树与森林存储结构脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：54393ec4f9950093622d43ae33670f17
思维导图大纲
树与森林存储结构及遍历思维导图模板大纲
树的存储结构
双亲表示法
静态链表，查双亲很方便，查孩子很不方便
孩子表示法
多重链表，找孩子方便找双亲复杂
孩子兄弟表示法
物理上存储为二叉树的样子，逻辑上是一棵普通的树，物理上的二叉树左孩子右兄弟
同时也是树和二叉树相互转化的方法
森林与二叉树的转换
左孩子右兄弟，用二叉链表存储森林
森林F，对应二叉树B，互相转化
F->B
F空B空
F非空则B的根即为森林中第一棵树T1的根，B的左子树LB是由T1中根结点的子树森林F1转换而来的二叉树，而右子树RB是从除了T1以外的森林F’转换而来的二叉树
B->F
B空则F空
B非空，则F中第一棵树T1的根即为二叉树B的根，T1中根节点的子树森林F1是由B的左子树LB转化而来的，而F中除了T1之外其余的树组成的森林F’是由B的右子树RB转换而来的
树与森林的遍历
总结
总结性内容
树的深度优先遍历
先根遍历
树非空，先访问根，再依次先根遍历各子树
后根遍历
树非空，先依次对各子树后根遍历，最后再访问根结点
树的广度优先遍历
层序遍历，和二叉树一样
森林的先序遍历
若森林非空，则
访问第一棵树的根节点
先序遍历第一棵树根节点的子树森林
先序遍历除了第一棵树的剩余的树构成的森林
森林的中序遍历
同上，顺序变成213
树和森林的结论
森林有n个非终端结点
立即推森林转换的二叉树中无右孩子的结点为n+1个
证明：各非终端结点必有孩子，n个孩子，这其中必有孩子是最右结点，无右兄弟
因此有n个结点无右兄弟，再加上最后一棵树的根节点一定无右兄弟，故有n+1个无右兄弟的结点
同理可证，树有n个分支结点
树所对应的二叉树中无右孩子的结点数为n+1个
证法同上，树的根对应的二叉树的根必没有右孩子
推论：树中叶结点数 = 二叉树中有右孩子的结点数 + 1
另外，树（森林）中叶结点个数 = 对应二叉树中左孩子指针为空的结点个数
森林有m个结点，n条边
立即推，森林中有m-n棵树
证明：如果把森林的各根结点连起来，连成一棵树，那么m个结点的树应该有m-1条边，如今有n条边，说明多连了m-n-1条边，说明有m-n个根结点！
求由孩子兄弟表示的树的高度
递归算法，出口为树为空，return 0;
递归主体为：h = max{height(root->left) + 1，root->right}
也就是本层的高度等于以当前结点为根的树的高度+1和自己同层右兄弟高度中的最大值！
注意结点高度是从下往上数
包含n个结点的树有多少种形态
树的二叉树表示中，根右指针一定空，故就看根的左子树n-1个节点能构成多少二叉树，符合卡特兰数
沪公网安备 31011502019485号
上海工商