ツリー非再帰ループアルゴリズム
16897 ワード
ツリー非再帰ループアルゴリズム
1.前段遍歴
2.中順遍歴
3.後段遍歴
1.前段遍歴
/**
*
*/
@Override
public void preOrderByStack() {
System.out.print(" :");
if (root==null){
System.out.println(" !!!");
}else {
LinkedList<BinaryNode> list = new LinkedList<BinaryNode>();
Queue<BinaryNode> stack = new LinkedList<>();
BinaryNode current = root;
while (current!=null || !stack.isEmpty()){
while (current!=null){
list.add(current);
((LinkedList<BinaryNode>) stack).push(current);
current = current.left;
}
if(!stack.isEmpty()){
current =((LinkedList<BinaryNode>) stack).pop();
current =current.right;
}
}
for(BinaryNode binaryNode : list){
System.out.print(binaryNode.value+" ");
}
System.out.println();
}
}
2.中順遍歴
/**
* ( )
*/
@Override
public void inOrderByStack() {
System.out.print(" :");
//
Deque<BinaryNode> stack = new LinkedList<BinaryNode>();
BinaryNode current =root;
while (current!=null || !stack.isEmpty()){
while (current!=null){
stack.push(current);
current=current.left;
}
if(!stack.isEmpty()){
current=stack.pop();
System.out.print(current.value+" ");
current=current.right;
}
}
System.out.println();
}
3.後段遍歴
/**
*
*/
@Override
public void postOrderByStack() {
System.out.print(" :");
ArrayList<BinaryNode> list = new ArrayList<BinaryNode>();
if(root!=null){
Deque<BinaryNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()){
BinaryNode current = stack.pop();
list.add(0,current);
if(current.left!=null){
stack.push(current.left);
}
if(current.right!=null){
stack.push(current.right);
}
}
Iterator<BinaryNode> iterator = list.iterator();
while (iterator.hasNext()){
System.out.print(iterator.next().value+" ");
}
System.out.println();
}
}