二叉查找树-DFS与BFS的实现

Tree.cpp

#include <iostream>
#include <cstddef>
#include <queue>
#include <string>
#include <cstdlib>
#include <stack>
using namespace std;
class Node {
public:
    int data;
    Node *left, *right;
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};
class Solution {
public:
    Node* insert(Node* root, int data) {
        if (root == NULL) {
            return new Node(data);
        } else {
            Node* cur;
            if (data <= root->data) {
                cur = insert(root->left, data);
                root->left = cur;
            } else {
                cur = insert(root->right, data);
                root->right = cur;
            }
            return root;
        }
    }
    void BFS(Node * root) {
        //Write your code here
        if (root != NULL) {
            queue<Node *> q;
            q.push(root);
            Node *tree;
            while (! q.empty())
            {
                tree = (Node *)q.front();
                q.pop();
                cout << tree->data << endl;
                if (tree->right != NULL) {
                    q.push(tree->right);
                }
                if (tree->left != NULL) {
                    q.push(tree->left);
                }

            }
        }
    }

    void DFS(Node *root) {
        if (root != NULL) {
            stack<Node *> stack;
            stack.push(root);
            Node *node;
            while (!stack.empty()) {
                node = stack.top();
                cout << node->data << endl;
                stack.pop();
                if (node->right) {
                    stack.push(node->right);
                }
                if (node->left) {
                    stack.push(node->left);
                }
            }
        }
        
    }

};//End of Solution
int main() {
    Solution myTree;
    Node* root = NULL;
    int T, data;
    cin >> T;
    while (T-- > 0) {
        cin >> data;
        root = myTree.insert(root, data);
    }
    cout << "BFS:" << endl;
    myTree.BFS(root);
    cout << "DFS:" << endl;
    myTree.DFS(root);
    system("pause");
    return 0;
}