fork download
copy 
  1. //13 Queue and Tree BFS With No Recursion
  2. //   Key is the function DFS
  3. //2011-06-18
  4.  
  5. #include <iostream>
  6. using namespace std;
  7.  
  8. struct node{
  9. 	int data;
  10. 	node *left;
  11. 	node *right; 
  12. };
  13.  
  14. int level_cutoff = 2;
  15. int counter = 0; 
  16.  
  17. /*        PART 1 : STACK         */
  18. /*        See Example 6 Stack    */
  19. struct stack_node{
  20. 	node *data;
  21. 	struct stack_node *next;
  22. };
  23.  
  24. // return the new element if succeed, otherwise NULL
  25. stack_node* push(stack_node **stack, node *data){
  26. 	stack_node *newHead = new stack_node;
  27. 	if (!newHead) return 0; // memory allocation fails
  28.  
  29. 	newHead->data = data;
  30. 	newHead->next = *stack;
  31. 	*stack = newHead;
  32.  
  33. 	return newHead; // success	
  34. }
  35.  
  36. // return 0 if the stack is empty, otherwise 1
  37. int pop(stack_node **stack, node **data)
  38. {
  39. 	if (!*stack) return 0;
  40.  
  41. 	stack_node *top = *stack;
  42. 	*data = top->data;
  43.  
  44. 	*stack = (*stack)->next;
  45. 	delete top;
  46. 	return 1;
  47. }
  48.  
  49.  
  50. /*        PART 2 : TREE         */
  51. node *createNode(){
  52. 	node *n = new node;
  53. 	if (!n) return NULL;
  54. 	n->left = NULL;
  55. 	n->right = NULL;
  56.  
  57. 	//cout << counter <<"\n";
  58. 	n->data = counter++; 
  59. 	return n;
  60. }
  61.  
  62. void addChildren(node *n, int level){
  63. 	if (level >= level_cutoff) return;
  64. 	node *l = createNode();
  65. 	if(l) {
  66. 		n->left = l;
  67. 	}
  68. 	node *r = createNode();	
  69. 	if(r) {
  70. 		n->right = r;
  71. 	} 
  72. 	addChildren(l, level+1);
  73. 	addChildren(r, level+1);
  74. }
  75.  
  76. void printTree(node *n, int level){
  77. 	if(!n) return; 
  78.  
  79. 	cout.width(level*4); cout.fill(' ');
  80. 	cout << n->data << "\n" ;
  81. 	printTree(n->left, level+1); 
  82. 	printTree(n->right, level+1); 	 
  83. }
  84.  
  85. void DFS(node *n){
  86. 	stack_node *stack = new stack_node;
  87. 	push(&stack, n);
  88.  
  89. 	node *cursor;
  90.  
  91. 	while(pop(&stack, &cursor)){
  92. 		if (cursor){		
  93. 			cout << cursor->data << " ";
  94. 			if(cursor->left) push(&stack, cursor->left);
  95. 			if(cursor->right) push(&stack, cursor->right);	
  96. 		}
  97. 	}
  98. }
  99.  
  100. int main(){
  101. 	node *root = createNode();
  102. 	addChildren(root,0);
  103.  
  104. 	cout << "\nTree is \n";
  105. 	printTree(root,0);
  106.  
  107. 	cout << "\nDepth first traversal (preorder traversal)\n";
  108. 	DFS(root);  
  109.  
  110. 	return 1;
  111. }
  112.  
Success #stdin #stdout 0s 2856KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Tree is 
0
   1
       3
       4
   2
       5
       6

Depth first traversal (preorder traversal)
0 2 6 5 1 4 3
https://ideone.com/6ys59
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!