justhomework/DataStructure/Code/ex09/BST.hpp

#include "bintree.hpp"
#include "stack.hpp"
#include <cmath>
#include <iostream>
#include <string>
#include <time.h>

class BST : binTree<int>
{
private:
    binNodeArray(int) p;

public:
    ~BST()
    {
    }
    BST(int num)
    {
        srand(time(NULL));
        int temp = rand() % 1440;
        _root->data = temp;
        _root->pos = "root";
        std::cout << _root->pos;
        printf("-%02d:%02d \n", temp / 60, temp % 60);

        for (int i = 0; i < num - 1; i++)
        {
            temp = rand() % 1440;
            p = root();
            std::string position;
            while (temp != -1)
            {
                if (temp < (p->data))
                {
                    if (hasLC(p))
                    {
                        p = p->lc;
                        position.append("0");
                    }

                    else
                    {
                        position.append("0");
                        addLC(p, temp);
                        p->lc->pos = position;
                        std::cout << position;
                        printf("-%02d:%02d \n", temp / 60, temp % 60);
                        temp = -1;
                    }
                }
                else if (temp > (p->data))
                {
                    if (hasRC(p))
                    {
                        p = p->rc;
                        position.append("1");
                    }

                    else
                    {
                        position.append("1");
                        addRC(p, temp);
                        p->rc->pos = position;
                        std::cout << position;
                        printf("-%02d:%02d \n", temp / 60, temp % 60);
                        temp = -1;
                    }
                }
                else
                {
                    i--;
                    temp = -1;
                }
            }
        }
    }

    bool searchPath(binNodeArray(int) root, binNodeArray(int) target, Stack<binNodeArray(int)> *s)
    {
        if (root == NULL)
            return false;
        s->push(root);
        if (root->data == target->data)
            return true;

        bool flag = false;
        //先去左子树找
        if (root->lc != NULL)
            flag = searchPath(root->lc, target, s);
        //左子树找不到并且右子树不为空的情况下才去找
        if (!flag && root->rc != NULL)
            flag = searchPath(root->rc, target, s);
        //左右都找不到，弹出栈顶元素
        if (!flag)
            s->pop();
        return flag;
    }

    //层次遍历
    void trav_level()
    {
        Queue<binNodeArray(int)> q;
        int depth = 0;
        int old_depth = 0;
        q.enqueue(root());
        while (!q.empty())
        {
            binNodeArray(int) node = q.dequeue();

            old_depth = depth;
            depth = node->pos.size();
            if (old_depth != depth)
                printf("\n");

            // std::cout << node->pos;
            printf("%02d:%02d   ", node->data / 60, node->data % 60);

            if (hasLC(node))
                q.enqueue(node->lc);
            if (hasRC(node))
                q.enqueue(node->rc);
        }
    }

    void search_best(int target)
    {
        binNodeArray(int) node = root();
        int old_data = 0;
        Stack<binNodeArray(int)> S;
        while (1)
        {
            gotoLeftEnd(node, S);

            if (S.empty())
                break;
            node = S.pop();

            if (target > old_data && target <= node->data)
            {
                if (abs(old_data - target) < abs(node->data - target))
                {
                    // std::cout << node->pos;
                    printf("%02d:%02d \n", old_data / 60, old_data % 60);
                }
                else
                {
                    // std::cout << node->pos;
                    printf("%02d:%02d \n", node->data / 60, node->data % 60);
                }
                return;
            }

            old_data = node->data;

            node = node->rc;
        }
        printf("未找到\n");
    }

    //先序遍历
    void trav_pre()
    {
        pre(root());
    }

    //后序遍历
    void trav_post()
    {
        post(root());
    }

    //中序遍历
    void trav_in()
    {
        in(root());
    }

protected:
    void pre(binNodeArray(int) node)
    {
        if (!node)
            return;

        Stack<binNodeArray(int)> S;
        while (1)
        {
            visitAlongL(node, S);
            if (S.empty())
                break;
            node = S.pop();
        }
    }
    void visitAlongL(binNodeArray(int) x, Stack<binNodeArray(int)> &S)
    {
        while (x)
        {
            std::cout << x->pos;
            printf("-%02d:%02d \n", x->data / 60, x->data % 60);
            S.push(x->rc);
            x = x->lc;
        }
    }

    void post(binNodeArray(int) node)
    {
        if (!node)
            return;

        pre(node->lc);
        pre(node->rc);

        std::cout << node->pos;
        printf("-%02d:%02d \n", node->data / 60, node->data % 60);
    }

    void in(binNodeArray(int) node)
    {
        if (!node)
            return;
        Stack<binNodeArray(int)> S;
        while (1)
        {
            gotoLeftEnd(node, S);

            if (S.empty())
                break;
            node = S.pop();

            std::cout << node->pos;
            printf("-%02d:%02d \n", node->data / 60, node->data % 60);

            node = node->rc;
        }
    }

    void gotoLeftEnd(binNodeArray(int) x, Stack<binNodeArray(int)> &S)
    {
        while (x)
        {
            S.push(x);
            x = x->lc;
        }
    }

public:
    int height()
    {
        Queue<binNodeArray(int)> q;
        q.enqueue(root());
        int depth;
        while (!q.empty())
        {
            binNodeArray(int) node = q.dequeue();

            depth = node->pos.size();

            if (hasLC(node))
                q.enqueue(node->lc);
            if (hasRC(node))
                q.enqueue(node->rc);
        }

        return depth;
    }
    binNodeArray(int) find_ans(binNodeArray(int) a, binNodeArray(int) b)
    {
        binNodeArray(int) ans = a;
        binNodeArray(int) node;
        while (ans)
        {
            node = ans;
            Stack<binNodeArray(int)> S;
            while (1)
            {
                gotoLeftEnd(node, S);

                if (S.empty())
                    break;
                node = S.pop();

                if(node==b)
                    return ans;

                node = node->rc;
            }
            ans = ans->parent;
        }
        return NULL;
    }
};