数据结构 课件 树和森林1

《数据结构 课件 树和森林1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、树与森林树与二叉树转换森林的遍历二叉树的计数赫夫曼二叉树树与二叉树转换ACBED树ABCDE二叉树A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^对应存储存储解释解释将树转换成二叉树加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针转45°ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空将二叉树转换成树加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二

2、叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI森林转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树还原：将孤立的二叉树还原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ

3、树的先序遍历树的后序遍历森林的先序遍历森林的中序遍历三、树和森林的遍历⑴访问树的根结点；⑵从左至右依次先序遍历根的每棵子树。1、树的先序遍历beadfhigcjabe遍历序列：⑴访问树的根结点；⑵从左至右依次先序遍历根的每棵子树。1、树的先序遍历beadfhigcjabe遍历序列：f⑴访问树的根结点；⑵从左至右依次先序遍历根的每棵子树。1、树的先序遍历beadfhigcjabefg遍历序列：⑴访问树的根结点；⑵从左至右依次先序遍历根的每棵子树。1、树的先序遍历beadfhigcjabefg遍历序列：⑴访问树的根结点；⑵从左至右依次先序遍历根的每棵子树。1、树的先序遍历beadfhigcjab

4、efgc遍历序列：⑴访问树的根结点；⑵从左至右依次先序遍历根的每棵子树。1、树的先序遍历beadfhigcjabefgcdhi遍历序列：⑴访问树的根结点；⑵从左至右依次先序遍历根的每棵子树。1、树的先序遍历beadfhigcjabefgcdhij遍历序列：⑴访问树的根结点；⑵从左至右依次先序遍历根的每棵子树。1、树的先序遍历beadfhigcjabefgcdhij遍历序列：⑴访问树的根结点；⑵从左至右依次先序遍历根的每棵子树。1、树的先序遍历beadfhigcjabefgcdhij遍历序列：⑴访问树的根结点；⑵从左至右依次先序遍历根的每棵子树。1、树的先序遍历beadfhigcjabefgc

5、dhij遍历序列：问：树的先序遍历序列与对应二叉树的哪种遍历序列相同？1、树的先序遍历beadfhigcjabe遍历序列fgcdhij答：树的先序遍历序列与对应二叉树的先序遍历序列相同。树的先根次序遍历的递归算法templatevoidTree::PreOrder(TreeNode*current){//以当前指针current为根,先根次序遍历if(!current.IsEmpty()){//树非空visit(current);//访问根结点TreeNode*p=current;//暂存当前指针current=current->firstChild;//第

6、一棵子树while(current!=NULL){PreOrder(current);//递归先根遍历子树current=current->nextSibling;}current=p;//恢复当前指针}};思考:如何实现先序遍历某个文件目录?⑴从左至右，依次后序遍历根的每棵子树；⑵访问树的根结点。2、树的后序遍历beadfhigcje遍历序列：⑴从左至右，依次后序遍历根的每棵子树；⑵访问树的根结点。2、树的后序遍历beadfhigcjef遍历序列：⑴从左至右，依次后序遍历根的每棵子树；⑵访问树的根结点。2、树的后序遍历beadfhigcjefg遍历序列：⑴从左至右，依次后序遍历根的每棵子树

7、；⑵访问树的根结点。2、树的后序遍历beadfhigcjefgb遍历序列：⑴从左至右，依次后序遍历根的每棵子树；⑵访问树的根结点。2、树的后序遍历beadfhigcjefgbc遍历序列：⑴从左至右，依次后序遍历根的每棵子树；⑵访问树的根结点。2、树的后序遍历beadfhigcjefgbci遍历序列：⑴从左至右，依次后序遍历根的每棵子树；⑵访问树的根结点。2、树的后序遍历beadfhigcjefgbcij遍历序