как преобразовать рекурсию обхода двоичного дерева поиска в нерекурсивный метод в java

Простите меня, если его спрашивали раньше, но я не мог найти подходящего ответа. У меня серьезная проблема с преобразованием бинарного обхода дерева поиска, написанного рекурсивным методом, в нерекурсивный метод. пожалуйста, помогите мне. Вот код, использующий рекурсивный метод в java.

// Класс BinarySt

public interface BinaryST {
public void insert(Integer nData);
public Integer remove(Integer nData);
public boolean isExist(Integer nData);

public String preOrder();
public String inOrder();
public String postOrder();

}

// Класс BinaryTreeNode

public class BinaryTreeNode {
Integer element;
BinaryTreeNode LChild;
BinaryTreeNode RChild;

BinaryTreeNode() {}
}

// BinarySearchTree реализует класс BinaryST

public class BinarySearchTree implements BinaryST{
protected StringBuffer s;
protected BinaryTreeNode root;

public BinarySearchTree() {}        
public BinarySearchTree(Integer nData)
{
    root = new BinaryTreeNode();
    root.element = nData;
}

public void insert(Integer nData)
{
    if( root==null ) {
        root = new BinaryTreeNode();
        root.element = nData;
        return;
    }

    boolean flag=true;
    BinaryTreeNode c=root;

    while(flag) {
        if( nData>=c.element ) {
            if( c.RChild==null ) {
                c.RChild = new BinaryTreeNode();
                c.RChild.element = nData;
                flag = false;
            }
            c = c.RChild;
        } 
        else {
            if( c.LChild==null ) {
                c.LChild = new BinaryTreeNode();
                c.LChild.element = nData;
                flag = false;
            }
            c = c.LChild;
        }
    }
}

public Integer remove(Integer nData)
{
    return new Integer(5);
}

public boolean isExist(Integer nData)
{
    return true;
}

public String preOrder()
{
    if( root==null ) {
        return new String( "null" );
    }

    s = new StringBuffer("");
    prOrder( root );

    return new String(s);
}

public String inOrder()
{
    if( root==null ) {
        return new String( "null" );
    }

    s = new StringBuffer("");
    iOrder( root );

    return new String(s);
}

public String postOrder()
{
    if( root==null ) {
        return new String( "null" );
    }

    s = new StringBuffer("");
    poOrder( root );

    return new String(s);
}

private void prOrder(BinaryTreeNode t) {
    if( t!=null ) {
        s.append( t.element.toString() + " " );
        prOrder( t.LChild );
        prOrder( t.RChild );
    }
}

private void iOrder(BinaryTreeNode t) {
    if( t!=null ) {
        iOrder( t.LChild );
        s.append( t.element.toString() + " " );
        iOrder( t.RChild );
    }
}

private void poOrder(BinaryTreeNode t) {
    if( t!=null ) {
        poOrder( t.LChild );
        poOrder( t.RChild );
        s.append( t.element.toString() + " " );
    }
}
}

// Класс бегуна

public class Runner {
public static void main(String[] args) {
    BinarySearchTree a = new BinarySearchTree();

    System.out.println( "Pre-Order : "+a.preOrder() );
    System.out.println( "In-Order  : "+a.inOrder() );
    System.out.println( "Post-Order: "+a.postOrder() );

    a.insert( (Integer) 100 );
    a.insert( (Integer) 50  );
    a.insert( (Integer) 150 );
    a.insert( (Integer) 25  );
    a.insert( (Integer) 75  );
    a.insert( (Integer) 125 );
    a.insert( (Integer) 175 );
    a.insert( (Integer) 60  );
    a.insert( (Integer) 160 );
    a.insert( (Integer) 200 );
    a.insert( (Integer) 155 );

    System.out.println( "Pre-Order : "+a.preOrder() );
    System.out.println( "In-Order  : "+a.inOrder() );
    System.out.println( "Post-Order: "+a.postOrder() );
}
}

java traversal recursive-datastructures non-recursive
person user3536823    schedule 18.04.2014    source источник
comment
Вам в основном понадобится стек.   -  person Louis Wasserman    schedule 19.04.2014
comment
возможный дубликат обхода двоичного дерева без рекурсии или рекурсивный и невозобновляемый обход дерева   -  person Ted Hopp    schedule 19.04.2014
comment
Как правило, чтобы преобразовать рекурсивный алгоритм в нерекурсивный, вам нужен какой-то стек или связанный список, чтобы отслеживать, где вы были. В некоторых случаях, например, для алгоритма обхода дерева вы можете использовать пространство, которое уже существует (или может быть выделено) в узлах, которые вы проходите.   -  person Hot Licks    schedule 19.04.2014
comment
со стеком он не работает, поэтому в нем много ошибок. пожалуйста, помогите мне   -  person user3536823    schedule 19.04.2014

Ответы (2)


arrow_upward
0
arrow_downward

Это код для предзаказа. Используйте это и конвертируйте в postorder и inorder

private void prOrder(BinaryTreeNode t) {
        if( t!=null ) {
            Stack<BinaryTreeNode> rootStack=new Stack<BinaryTreeNode>();
            BinaryTreeNode current=t;

            do{     
                s.append( current.element.toString() + " " );
                if(current.RChild!=null)
                    rootStack.add(current.RChild);
                if(current.LChild!=null)
                    rootStack.add(current.LChild);

                if(rootStack.isEmpty())
                    current=null;
                else
                    current=rootStack.pop();

            }while(current!=null);  

        }
    }
person Biswajit_86    schedule 27.04.2014

arrow_upward
0
arrow_downward

Рассмотрим узел двоичного дерева:

public class BinaryTreeNode {

private int data;
private BinaryTreeNode left;
private BinaryTreeNode right;

public BinaryTreeNode() {
}

public BinaryTreeNode(int data) {
    this.data=data;
}

public int getData() {
    return data;
}
public void setData(int data) {
    this.data = data;
}
public BinaryTreeNode getLeft() {
    return left;
}
public void setLeft(BinaryTreeNode left) {
    this.left = left;
}
public BinaryTreeNode getRight() {
    return right;
}
public void setRight(BinaryTreeNode right) {
    this.right = right;
}

}

Непрерывное отслеживание почтового заказа:

public static void nonRecursivePostOrder (корень BinaryTreeNode) {

    Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
    List<BinaryTreeNode> returnNodes = new LinkedList<BinaryTreeNode>();


      while (true) {
          if (root != null) {

              if (returnNodes.contains(root)) {
                  returnNodes.add(stack.pop());
                  root = null;
              } else {
                  stack.push(root);
                  root = root.getLeft();
              }

          } else {
              if (stack.isEmpty()) {
                  break;
              } else if (stack.peek().getRight() == null) {
                  root = stack.pop();
                  returnNodes.add(root);
                  if (root == stack.peek().getRight()) {
                      returnNodes.add(stack.pop());
                  }
              }

              if (!stack.isEmpty()) {
                  root = stack.peek().getRight();
              } else {
                  root = null;
              }
          }
      }

      for(BinaryTreeNode node : returnNodes)
          System.out.print(node.getData()+" ");

}

Неофициальный обход заказов:

public static void nonRecursiveInOrder (корень BinaryTreeNode) {

    if(root == null)return;

    Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();


    while (true) {

        if(root.getLeft()!=null){
            stack.push(root);               
            root = root.getLeft();
        }else if(root.getRight()!=null){
            System.out.print(root.getData()+" ");
            root = root.getRight();
        }else{
            System.out.print(root.getData()+" ");

            if(stack.isEmpty())
                break;

            root = stack.pop();
            System.out.print(root.getData()+" ");
            root = root.getRight();
        }



    }
}

Нерекурсивный обход перед заказом:

public static void nonRecursivePreOrder (корень BinaryTreeNode) {

    if(root == null)return;

    Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();


    while (true) {

        if(root.getLeft()!=null){
            stack.push(root);
            System.out.print(root.getData()+" ");
            root = root.getLeft();
        }else if(root.getRight()!=null){
            System.out.print(root.getData()+" ");
            root = root.getRight();
        }else{
            System.out.print(root.getData()+" ");

            if(stack.isEmpty())
                break;
            root = stack.pop();
            root = root.getRight();
        }



    }
}
person Sravan Chithari    schedule 08.11.2014