|
|
知识路径： > 计算机系统基础知识 > 计算机软件知识 > 数据结构与算法知识 > 树 > 树 > 二叉树 >
|
|
相关知识点：8个
|
|
|
|
|
|
|
.树的双亲表示法：用一组地址连续的单元存储树的节点，并在每个节点中附设一个指示器，指示其双亲节点在该存储结构中的位置。显然这种表示对于求指定节点的双亲或祖先都十分方便，但对于求指定节点的孩子及后代则需要遍历整个数组。
|
|
|
|
.树的孩子表示法：在存储结构中用指针指示出节点的每个孩子，由于树中每个节点的子树数目不尽相同，因此在采用链式存储结构时可以考虑多重链表。
|
|
|
|
.树的孩子兄弟表示法：又称二叉链表表示法。在链表的节点中设置两个指针域分别指向该节点的第一个孩子和下一个兄弟。利用这种存储结构便于实现树的各种操作。
|
|
|
|
|
|
（1）树的遍历。树的遍历分为先根遍历和后根遍历两种。
|
|
|
|
.先根遍历：先访问树的根节点，然后依次先根遍历根的各棵子树。对树的先根遍历等同于对转换所得的二叉树进行先序遍历。
|
|
|
|
.后根遍历：先依次后根遍历树根的各棵子树，然后访问树根节点。树的后根遍历等同于对转换所得的二叉树进行中序遍历。
|
|
|
|
（2）森林的遍历。森林的遍历分为前序遍历和后序遍历两种。
|
|
|
|
.前序遍历森林：若森林非空，访问森林中第一棵树的根节点，前序遍历第一棵子树根节点的子树森林，再前序遍历除第一棵树之外剩余的树所构成的森林。
|
|
|
|
.后序遍历森林：若森林非空，后序遍历森林中第一棵树的子树森林，访问第一棵树的根节点，后序遍历除第一棵树之外剩余的树所构成的森林。
|
|
|
|
|
|
（1）树、森林转换为二叉树。利用树的孩子兄弟表示法可导出树与二叉树的对应关系，在树的孩子兄弟表示法中，从物理结构上看与二叉树的二叉链表表示法相同，因此就可以用这种同一存储结构的不同解释将一棵树转换为一棵二叉树。
|
|
|
|
将一个森林转换为一棵二叉树的方法是：先将森林中的每一棵树转换为二叉树，再将第一棵树的根作为转换后的二叉树的根，第一棵树的左子树作为转换后二叉树根的左子树，第二棵树作为转换后二叉树根的右子树，第三棵树作为转换后二叉树根的右子树的右子树，以此类推，森林就可以转换为一棵二叉树。
|
|
|
|
（2）二叉树转换为树和森林。若二叉树非空，则二叉树根及其左子树为第一棵树的二叉树形式，二叉树根的右子树又可以看作一个由森林转换后的二叉树，应用同样的方法，直到最后产生一棵没有右子树的二叉树为止，这样就得到了一个森林。为了进一步得到树，可用树的二叉链表表示的逆方法，即节点的右子树的根、右子树的右子树的根……找出原本是同一个双亲的兄弟。二叉树转换为树或森林是唯一的。
|
|
|
