Javaで二叉木の非再帰の前序、中序、後序遍歴アルゴリズムを実現する
4533 ワード
2 ,
package BinaryTree;
public class TreePoint {
public String name;
private TreePoint leftNode;
private TreePoint rightNode;
private TreePoint parent;
private boolean visit=false;
public TreePoint(String name){
this.name = name;
}
public TreePoint(String name,TreePoint leftNode,TreePoint rightNode){
this.name = name;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
public TreePoint getLeftNode(){
if(leftNode!= null&&leftNode.isVisited()){
return null;
}
return leftNode;
}
public void setLeftNode(TreePoint leftNode){
this.leftNode = leftNode;
}
public TreePoint getRightNode(){
if(rightNode!= null&&rightNode.isVisited()){
return null;
}
return rightNode;
}
public void setRightNode(TreePoint rightNode){
this.rightNode= rightNode;
}
public boolean isVisited(){
return visit;
}
public void setVisit(boolean visit){
this.visit = visit;
}
public TreePoint getParent(){
return parent;
}
public void setParent(TreePoint parent){
this.parent = parent;
}
public String toString(){
setVisit(true);
return name;
}
}
package BinaryTree;
import java.util.Stack;
public class TreeTest {
private static TreePoint root=null;
public static void TreeInit(){
TreePoint A = new TreePoint("A");
root = A;
TreePoint B = new TreePoint("B");
TreePoint C = new TreePoint("C");
A.setLeftNode(B);
A.setRightNode(C);
B.setParent(A);
C.setParent(A);
TreePoint D = new TreePoint("D");
TreePoint E = new TreePoint("E");
B.setLeftNode(D);
B.setRightNode(E);
D.setParent(B);
E.setParent(B);
TreePoint F = new TreePoint("F");
TreePoint G = new TreePoint("G");
C.setLeftNode(F);
C.setRightNode(G);
F.setParent(C);
G.setParent(C);
TreePoint H = new TreePoint("H");
TreePoint I = new TreePoint("I");
E.setLeftNode(H);
E.setRightNode(I);
H.setParent(E);
I.setParent(E);
TreePoint J = new TreePoint("J");
G.setRightNode(J);
J.setParent(G);
}
public static void check(TreePoint root,String SortName){
if(root==null){
System.out.println(" ");
System.exit(0);
}
System.out.println(SortName);
}
public void testFirst(){
check(root," ");
TreePoint next = root;
while(next!=null){
if(!next.isVisited()){
System.out.print(next+" ");
}
TreePoint flag = next.getLeftNode();
if(flag==null){
flag = next.getRightNode();
if(flag == null){
next = next.getParent();
continue;
}
next = flag;
continue;
}
next = flag;
}
}
public void testMiddle(){
check(root," ");
TreePoint next = root;
while(next!=null){
TreePoint flag = next.getLeftNode();
if(flag==null){ // ,
if(!next.isVisited()){
System.out.print(next+" ");
}
flag=next.getRightNode();
if(flag==null){
next = next.getParent();
}else{
next = flag;
}
}else{
next = flag;
}
}
}
public void testLast(){
check(root," ");
TreePoint next = root;
while(next!= null){
TreePoint flag = next.getLeftNode();
if(flag==null){
flag = next.getRightNode();
if(flag==null){
if(!next.isVisited()){
System.out.print(next+" ");
}
next = next.getParent();
}else{
next = flag;
}
}else{
next = flag;
}
}
}
public void Middle(){
Stack s = new Stack();
check(root," ");
TreePoint next=root;
while(next!=null||!s.isEmpty()){
if(next!=null){
s.push(next);
next = next.getLeftNode();
}else{
next = (TreePoint) s.pop();
System.out.print(next+" ");
next = next.getRightNode();
}
}
}
public void Last(){
Stack s = new Stack();
TreePoint next = root;
while(next!=null||!s.isEmpty()){
while(next!=null){
s.push(next);
next = next.getLeftNode();
}
next = s.pop();
if(next.getRightNode()==null){
System.out.print(next+" ");
}else{
next = next.getRightNode();
}
}
}
public static void main(String args[]){
TreeTest tt = new TreeTest();
tt.TreeInit();
// tt.testFirst();
// tt.testMiddle();
// tt.testLast();
// tt.Middle();
tt.Last();
}
}