Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stack>
- struct BTNode
- {
- BTNode(int d)
- {
- data = d;
- }
- int data;
- BTNode* right;
- BTNode* left;
- };
- void DFS(BTNode* root)
- {
- BTNode* tmp = root;
- std::stack<BTNode*> stck;
- stck.push(tmp);
- //Until the stack is not empty, it means there are nodes to traverse
- while(stck.empty() == false)
- {
- while (tmp->left != 0)
- {
- tmp = tmp->left;
- stck.push(tmp);
- }
- while(true)
- {
- tmp = stck.top();
- stck.pop();
- std::cout << tmp->data;
- if(tmp->right != 0)
- {
- tmp = tmp->right;
- stck.push(tmp);
- break;
- }
- }
- }
- void CreateTreeExample(BTNode* root)
- {
- BTNode* b1= new BTNode(1);
- BTNode* b2= new BTNode(2);
- BTNode* b3= new BTNode(3);
- BTNode* b4= new BTNode(4);
- BTNode* b5= new BTNode(5);
- BTNode* b6= new BTNode(6);
- BTNode* b7= new BTNode(7);
- BTNode* b8= new BTNode(8);
- BTNode* b9= new BTNode(9);
- b2->left = b1;
- b2->right = b4;
- b6->left = b2;
- b4->left = b3;
- b4->right = b5;
- b7->left = b6;
- b7->right = b8;
- b8->right = b9;
- root = b7;
- }
- //To test the algorithm, make a simple binary tree by calling the method:
- // 7
- // / \
- // 6 8
- // / \
- // 2 9
- // / \
- // 1 4
- // / \
- // 3 5
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement