dimanche 30 novembre 2014

how to print a tree in order by using stack and depth first search?


Vote count:

0





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
// //////////////////////////////////////////////////////////////


I want to write a function by depth first search so that the output is 1,2,3,4,5,6,7,8,9


Boolean flag is set in class Node and the i want that the function is similar to breadth first search.


I can't find relevant source to help me to complete it.



asked 38 secs ago







how to print a tree in order by using stack and depth first search?

Aucun commentaire:

Enregistrer un commentaire