POJ1577

一道二叉树的基础题目

思路：这题很简单，先把字符串push到堆栈中，然后依次insert到二叉树当中，最后递归前序遍历，就可以了。

直接上代码

#include <iostream>
#include <string>
#include <stack>

using namespace std;

struct Node {
    char val;
    Node *left;
    Node *right;

    Node(char c='*'): val(c), left(NULL), right(NULL) {}
};

class BinaryTree {
    public:
        BinaryTree(): root(NULL) {}
        void run() {
            stack<string> s;
            string str;
            while (cin >> str) {
                if (str[0] == '*' || str[0] == '$') {
                    buildTree(s);
                    preOrder();
                    if (str[0] == '$')
                        return;
                } else
                    s.push(str);
            }
        }

    private:
        void buildTree(stack<string> &s) {
            while (!s.empty()) {
                string str = s.top();
                s.pop();
                for (int i=0; i<str.size(); i++)
                    insert(str[i]);
            }
        }

        void preOrder() {
            preOrder(root);
            cout << endl;
            root = NULL;
        }

        void preOrder(Node *tree) {
            if (tree == NULL)
                return;
            cout << tree->val;
            preOrder(tree->left);
            preOrder(tree->right);
            delete tree;
        }

        void insert(const char c) {
            if (root == NULL)
                root = new Node(c);
            else {
                Node *ptr = root;
                Node *pre = NULL;
                while (ptr) {
                    if (ptr->val == c)
                        return;
                    else if (ptr->val > c) {
                        pre = ptr;
                        ptr = ptr->left;
                    } else {
                        pre = ptr;
                        ptr = ptr->right;
                    }
                }
                if (pre->val > c)
                    pre->left = new Node(c);
                else
                    pre->right = new Node(c);
            }
        }

        Node *root;
};

int main() {
    BinaryTree btree;
    btree.run();

    return 0;
}