Как распечатать дерево по порядку, используя поиск по стопке и глубине?

Question

import java.util.LinkedList;
import java.util.Queue;

class Node {
public int iData; // data item (key)
public double dData; // data item
public Node leftChild; // this node's left child
public Node rightChild; // this node's right child
public int level;
public boolean flag;

public void displayNode() // display ourself
{
    System.out.print('{');
    System.out.print(level);
    System.out.print(", ");
    System.out.print(iData);
    System.out.print(", ");
    System.out.print(dData);
    System.out.print("} ");
    System.out.println(" ");
}
} // end class Node
// //////////////////////////////////////////////////////////////

class Tree {
private Node root; // first node of tree

// -------------------------------------------------------------
public Tree() // constructor
{
root = null;
} // no nodes in tree yet
// -------------------------------------------------------------

public void insert(int id, double dd) {
Node newNode = new Node(); // make new node
newNode.iData = id; // insert data
newNode.dData = dd;
if (root == null) // no node in root
    root = newNode;
else // root occupied
{
    Node current = root; // start at root
    Node parent;
    while (true) // (exits internally)
    {
        parent = current;
        if (id < current.iData) // go left?
        {
            current = current.leftChild;
            if (current == null) // if end of the line,
            { // insert on left
                parent.leftChild = newNode;
                return;
            }
        } // end if go left
        else // or go right?
        {
            current = current.rightChild;
            if (current == null) // if end of the line
            { // insert on right
                parent.rightChild = newNode;
                return;
            }
        } // end else go right
    } // end while
} // end else not root
} // end insert()
// -------------------------------------------------------------

public void breadthFirstDisplay() {
    Queue newQueue = new LinkedList();
    int level = 0;
    newQueue.add(root);
    int temp = root.iData;
    while (!newQueue.isEmpty()) {
        Node theNode = (Node) newQueue.remove();
        if (temp > theNode.iData)
            level++;
        theNode.level = level;
        theNode.displayNode();
        temp = theNode.iData;
        if (theNode.leftChild != null) {
            newQueue.add(theNode.leftChild);
        }
        if (theNode.rightChild != null) {
            newQueue.add(theNode.rightChild);
        }
    }
}

public void depthFirstStackDisplay() {

}
// -------------------------------------------------------------
} // end class Tree
// //////////////////////////////////////////////////////////////

class TreeApp {
public static void main(String[] args){
Tree theTree = new Tree();

theTree.insert(5, 1.5);
theTree.insert(4, 1.2);
theTree.insert(6, 1.7);
theTree.insert(9, 1.5);
theTree.insert(1, 1.2);
theTree.insert(2, 1.7);
theTree.insert(3, 1.5);
theTree.insert(7, 1.2);
theTree.insert(8, 1.7);

theTree.breadthFirstDisplay();
theTree.depthFirstStackDisplay();

}// -------------------------------------------------------------
} // end class TreeApp
// //////////////////////////////////////////////////////////////

Я хочу написать функцию поиска по глубине, чтобы результат составил 1,2,3,4,5,6,7,8,9

Логический флаг установлен в классе Node, и я хочу, чтобы функция была похожа на поиск в ширину.

Я не могу найти соответствующий источник, чтобы помочь мне завершить его.

Answer 1

Вы можете попробовать этот алгоритм для печати первого обхода глубины (обход в соответствии с вашей задачей). Он будет использовать стек.

1) Создайте пустой стек S.

2) Инициализировать текущий узел как root

3) Нажмите текущий узел на S и установите current = current->left, пока current не станет NULL

4) Если ток равен NULL и стек не пуст

 a) Pop the top item from stack.

 b) Print the popped item, set current = popped_item->right 

 c) Go to step 3.

5) Если current равен NULL и стек пуст, то все готово.

Я не знаю много о Java, но вы можете воспользоваться помощью этого кода C:

    /* Iterative function for inorder tree traversal */
void inOrder(struct Node *root)
{
  /* set current to root of binary tree */
  struct Node *current = root;
  struct sNode *s = NULL;  /* Initialize stack s */
  bool done = 0;

  while (!done)
  {
    /* Reach the left most Node of the current Node */
    if(current !=  NULL)
    {
      /* place pointer to a tree node on the stack before traversing
        the node's left subtree */
      push(&s, current);                                              
      current = current->leftChild; 
    }

    /* backtrack from the empty subtree and visit the Node
       at the top of the stack; however, if the stack is empty,
      you are done */
    else                                                             
    {
      if (!isEmpty(s))
      {
        current = pop(&s);
        printf("%d ", current->idata);

        /* we have visited the node and its left subtree.
          Now, it's right subtree's turn */
        current = current->rightChild;
      }
      else
        done = 1;
    }
  } /* end of while */ 
}