1) 层次遍历
2)先根(序)遍历 DLR
3)中根(序)遍历 LDR
4)后根(序)遍历LRD
5)练习
先根序遍历:ABDEGCFH 中根序遍历:DBGEAFHC 后根序遍历:DGEBHFCA
先根序遍历:ABDEGJHCFIKL 中根序遍历:DBJGEHACKILF 后根序遍历:DJGHEBKLIFCA
先根序遍历:ABCDEFGHK 中根序遍历:BDCAEHGKF 后根序遍历:DCBHKGFEA
1)算法:先根(序)遍历 DLR
public void preRootTraverse(BiTreeNode T) {
if(T != null) {
System.out.print(T.data); //输出根元素
preRootTraverse(T.lchild); //先根遍历左子树
preRootTraverse(T.rchild); //先根遍历右子树
}
}
2)算法:中根(序)遍历 LDR
public void inRootTraverse(BiTreeNode T) {
if(T != null) {
inRootTraverse(T.lchild); //中根遍历处理左子树
System.out.print(T.data); //访问根节点
inRootTraverse(T.rchild); //中根遍历处理右子树
}
}
3)算法:后根(序)遍历LRD
public void postRootTraverse(BiTreeNode T) {
if(T != null) {
postRootTraverse(T.lchild); //后根遍历左子树
postRootTraverse(T.rchild); //后根遍历右子树
System.out.print(T.data); //访问根结点
}
}
4)动画演示:后根遍历
1)分析:先根(序)遍历 DLR
2)算法:先根(序)遍历 DLR【重点】
public void preRootTraverse() {
BiTreeNode T = root;
if( T != null ) {
LinkStack S = new LinkStack(); // 创建栈记录没有访问过的右子树
S.push(T); // 将根节点压入栈顶
while(!S.isEmpty()) { // 栈中只要有数据,表示继续遍历
T = S.pop(); // 弹出栈顶数据
System.out.print(T.data); // 结点被访问
while(T != null) { // T指针,访问每一个左孩子
if(T.lchild != null) { // 输出左孩子
System.out.print(T.lchild.data);
}
if(T.rchild != null) { // 将右孩子压栈
T.push(T.rchild);
}
T = T.lchild; // 访问下一个左孩子
}
}
}
}
3)分析:中根(序)遍历 LDR
4)算法:中根(序)遍历 LDR
public void inRootTraverse() {
BiTreeNode T = root;
if(T != null) {
LinkStack S = new LinkStack();
S.push(T); //将根节点压入到栈顶
while( !S.isEmpty() ) { //栈中有数据,表示遍历未完成
//1 将所有的左孩子压栈
while(S.peek() != null) { //栈顶的元素不为空,注意:不是弹栈
// 获得栈顶,
BiTreeNode temp = (BiTreeNode)S.peek();
// 并将左孩子压入栈顶
S.push(temp.lchild);
}
S.pop(); //将栈顶的空元素弹出
//2 依次弹出栈,访问当前节点,如果有右孩子继续压栈
if(! S.isEmpty()) {
T = (BiTreeNode)S.pop();
System.out.print(T.data); //访问栈顶
S.push(T.rchild);
}
}
}
}
5)分析:后根(序)遍历LRD
6)算法:后根(序)遍历LRD
public void postRootTraverse() {
BiTreeNode T = root;
if( T != null) {
LinkStack S = new LinkStack();
S.push(T);
// 声明两个变量
Boolean flag; //用于记录是否被访问
BiTreeNode p; //用于记录上一次处理的结点
while(! S.isEmpty() ) {
//1 将所有的左孩子压栈
while(S.peek() != null) { //栈顶的元素不为空,注意:不是弹栈
// 获得栈顶,
BiTreeNode temp = (BiTreeNode)S.peek();
// 并将左孩子压入栈顶
S.push(temp.lchild);
}
S.pop(); //将栈顶的空元素弹出
while( !S.isEmpty() ) {
T = (BiTreeNode) S.peek();
if(T.rchild == null || T.rchild == p) { // 没有右孩子 或 已经访问过
System.out.print(T.data);
S.pop(); //弹出
p = T; //记录刚才访问过的
flag = true; //没有新元素,继续访问
} else {
S.push(T.rchlid);
flag = false; //新右子树添加
}
if(!flag) {
break; //如果有右子树,需要重新开始
}
}
}
}
}