Tag: DFS

typedef char Element;

struct Node 
{
  Node( Element inputData ) : data( inputData ) { 
    cout << "Construct " << data << endl; 
  }
  
  ~Node() { 
    cout << "Destruct " << data << endl;
    
    if( lchild != NULL ) {
      delete lchild;
      lchild = NULL;
    }
    
    if( rchild != NULL ) {
      delete rchild;
      rchild = NULL;
    }
  }

  Element data;
  Node *lchild;
  Node *rchild;
};

typedef Node* Tree;

// BFS
void breadthFirstSearch(Tree root)
{
  queue<Node *> nodeQueue;
  nodeQueue.push (root);
  Node *node;
  while (!nodeQueue.empty()) {
   node = nodeQueue.front();
   nodeQueue.pop ();
   cout << node->data;

   if (node->lchild) {
     nodeQueue.push(node->lchild);
   }

   if (node->rchild) {
     nodeQueue.push(node->rchild);
   }
  }
}

// DFS (iterative)
void depthFirstSearch(Tree root)
{
  stack<Node *> nodeStack;
  nodeStack.push (root);
  Node *node;
  while (!nodeStack.empty ()) {
   node = nodeStack.top();
   nodeStack.pop ();
   cout << node->data;

   if (node->rchild) {
     nodeStack.push(node->rchild);
   }

   if (node->lchild) {
     nodeStack.push(node->lchild);
   }
  }
}

// DFS (recursive)
void depthFirstSearchRecursive(Tree root)
{
  if (root) {
    cout << root->data;

    if (root->lchild) {
     depthFirstSearchRecursive(root->lchild);
    }

    if (root->rchild) {
     depthFirstSearchRecursive(root->rchild);
    }
  }
}

class TreeBuilder
{
public:
  TreeBuilder( Element data[] ) : index_( 0 ) {
   constructTree( root_, data );  
  }

  ~TreeBuilder() {
   destructTree( root_ );
  }

  Tree tree() const { return root_ ;}
 
private:
  void constructTree(Tree &root, Element data[])
  {
    Element e = data[index_++];
    if (e == '#') {
     root = NULL;
    }
    else {
     root = new Node (e);
     constructTree(root->lchild, data);
     constructTree(root->rchild, data);
    }
  }

  void destructTree(Tree root) {
    if( root != NULL ) {
      delete root;
      root = NULL;
    }
  }

private:
  int index_;
  Tree root_;
};

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

...

int main(int argc, char** argv) 
{
  Element data[15] = { 'A', 'B', 'D', '#', '#', 'E', '#', '#', 'C', 'F','#', '#', 'G', '#', '#' };	
  
  TreeBuilder builder( data );
  
  auto tree = builder.tree();

  cout << endl;

  cout << "BFS result：";
  breadthFirstSearch(tree);

  cout << endl;
  
  cout << "DFS (iterative) result：";
  depthFirstSearch(tree);

  cout << endl;

  cout << "DFS (recursive) result：";
  depthFirstSearchRecursive(tree);

  cout << endl;
  
  return 0;
}