The structure of a tree node should look like this, resembling the node of a linked list:

1: struct node {

2: int data;

3: struct node* left;

4: struct node* right;

` 5: };`

For BFT:

1: void bfs(node* head) {

` 2: queue<node*> q;`

` 3: q.push(head);`

4: while (!q.empty()) {

` 5: node* n = q.front();`

` 6: q.pop();`

7: cout << n->data << " ";

8: if (n->left != 0)

` 9: q.push(n->left);`

10: if (n->right != 0)

` 11: q.push(n->right);`

` 12: }`

` 13: cout << endl;`

` 14: }`

DFT simply exchanges the queue with a stack:

1: void dfs(node* head) {

` 2: stack<node*> q;`

` 3: q.push(head);`

4: while (!q.empty()) {

` 5: node* n = q.top();`

` 6: q.pop();`

7: cout << n->data << " ";

8: if (n->left != 0)

` 9: q.push(n->left);`

10: if (n->right != 0)

` 11: q.push(n->right);`

` 12: }`

` 13: cout << endl;`

` 14: }`

## No comments:

## Post a Comment