树转换二叉树
的逆过程。
1)双亲链表存储结构
2)孩子链表存储结构
3)双亲孩子链表存储结构
4)孩子兄弟链表存储结构(重点掌握)
结点类
public class CSTreeNode {
public Object data;
//结点的数据域 publicCSTreeNode firstChild, nextsibling; //左孩子、右兄弟 }
1)先根遍历
先根遍历序列: ABEFCDGHIJK
public void preRootTraverse(CSTreeNode T) {
if(T != null) {
System.out.print(T.data);
preRootTraverse(T.firstChild); //先根遍历树中根节点的第一个子树
preRootTraverse(T.nextsibling); //先根遍历树中根节点的其他子树
}
}
2)后根遍历
后根遍历序列: EFBCIJKHGDA
public void postRootTraverse(CSTreeNode t) {
if(T != null) {
postRootTraverse(T.firstChild); //后根遍历树中根节点的第一个子树
System.out.print(T.data); //访问数的根节点
postRootTraverse(T.nextsibling); //后根遍历树中根节点的其他子树
}
}
3)层次遍历
ABCDEFGHIJK
public void levelTraverse(CSTreeNode T) {
if(T != null) {
LinkQueue L = new LinkQueue(); //构建队列
L.offer(T); //根节点入队列
while(!L.isEmpty()) {
for(T = L.poll() ; T != null ; T = T.nextisibling) {
System.out.print(T.data + " ");
if(T.firstChild != null) { //第一个孩子结点非空入队列
L.offer(T.firstchild);
}
}
}
}
}
1)先根遍历
先跟遍历顺序是: ABCEDFGHIJKL
2)后根遍历
后根遍历序列是: BECDAGFIKLJH
4)层次遍历
层次遍历序列: ABCDEFGHIJKL