数据结构Java8二叉树与树

{ postorder(p.left); postorder(p.right); System.out.print(p.data.toString()+\ //后访问当前结点元素 } }

大家知道，函数在调用时，会自动进行栈的push，调用返回时，则会自动进行栈的pop。函数递归调用无非是对一个栈进行返回的push与pop，既然递归方式可以实现二叉树的遍历，那么借用“栈”采用非递归方式，也能实现遍历。但是，这时的栈操作（push、pop等）是由用户进行的，因而实现起来会复杂一些，而且也不容易理解，但有助于我们对树结构的遍历有一个深刻、清晰的理解。

4) 先序遍历非递归算法

// 8. 二叉树孩子优先遍历的非递归算法

public void preorderTraverse() // 先根次序遍历二叉树的非递归算法 { System.out.print(\先根次序遍历（非递归）： \ Stack> stack = new Stack>(); // 创建空栈 BinaryNode p = this.root; while (p != null || !stack.isEmpty()) // p非空或栈非空时 if (p != null) { System.out.print(p.data + \访问结点 stack.push(p); // p结点入栈 p = p.left; // 进入左子树 } else // p为空且栈非空时 { // System.out.print(\∧ \ p = stack.pop(); // p指向出栈结点 p = p.right; // 进入右子树 } System.out.println(); }

5) 中序遍历非递归算法

public void inorderTraverse() // 中根次序遍历二叉树的非递归算法 { System.out.print(\中根次序遍历（非递归）： \ Stack> stack = new Stack>(); // 创建一个空栈 BinaryNode p = this.root; while (p != null || !stack.isEmpty()) // p非空或栈非空时 if (p != null) {

}

stack.push(p); // p结点入栈 p = p.left; // 进入左子树 } else // p为空且栈非空时 { p = stack.pop(); // p指向出栈结点 System.out.print(p.data + \访问结点 p = p.right; // 进入右子树 }

System.out.println();

6) 后序遍历非递归算法

遍历左子树是根结点需要入栈保存，左子树为空时，第一次访问栈顶根元素，寻找其右子树，右子树访问结束第二次访问这个根元素，由于这个根元素左右子树都已访问完成，第二访问可以出栈。 第一种方法：

public void postorderTraverse() // 后根次序遍历二叉树的非递归算法 { System.out.print(\后根次序遍历（非递归）： \ Stack> s = new Stack>(); BinaryNode curr = this.root; BinaryNode pre = null; while(curr!=null||!s.empty()){ while(curr!=null){ s.push(curr); curr = curr.left; } curr=s.peek(); if(curr.right==null||curr.right==pre){ System.out.print(curr.data + \访问结点 pre = curr; s.pop(); curr = null; } else curr=curr.right; } System.out.println(); }

第二种方法：

public void postorderTraverse() // 后根次序遍历二叉树的非递归算法 { System.out.print(\后根次序遍历（非递归）： \ Stack> s = new Stack>();

}

BinaryNode p = this.root; BinaryNode q; boolean flag;

while(p!=null||!s.empty()){ while(p!=null){ s.push(p); p=p.left; } q=null;flag=true; while(flag&&!s.empty()){ p=s.peek(); if(p.right==q){//右子树为空或刚刚处理过 s.pop(); System.out.print(p.data.toString()); if(p==root) return; q=p; }else{ p=p.right; flag=false; } } }

System.out.println();

7) 后序遍历非递归算法的应用

由于后序遍历先左右子树，后根的方式，所以可以利用后序遍历寻找指定结点的路径。 public void getPath(Stack> s,T key){ String path=key.toString(); while(!s.empty()){ path=s.pop().toString()+\ } System.out.println(path); }

public void postorderTraverse(T key) // 中根次序遍历二叉树的非递归算法 { System.out.print(\后根次序遍历（非递归）： \ Stack> s = new Stack>(); BinaryNode curr = this.root; BinaryNode pre = null; while(curr!=null||!s.empty()){ while(curr!=null){ if(curr.data.equals(key)){

// }

getPath(s,key); } s.push(curr); curr = curr.left; } if(curr!=null&&curr.data.equals(key)){ getPath(s,key); } curr=s.peek(); if(curr.right==null||curr.right==pre){ System.out.print(curr.data + \访问结点 pre = curr; s.pop(); curr = null; } else curr=curr.right; }

System.out.println();

8) 层次遍历的非递归算法

按层次遍历：从上到下、从左到右访问各结点 //用队列B1286 怎样从顶部开始逐层打印二叉树结点数据？

设置一个队列，然后只要队列不为空，将对首元素的左右孩子加入队列（如果左右孩子不为空），然后将队列的首元素出对即可，如下图所示： 二叉树如下图所示：

那么，整个过程如下：