二元樹的小範例

在網路上找到的，小改一下順便加上一些功能，該範例放進二元樹時已做過排序了：

#include <iostream>
#include <malloc.h>

using namespace std;

class LSBinaryTreeNode
{
public:
    int data;
    class LSBinaryTreeNode* left;
    class LSBinaryTreeNode* right;
    LSBinaryTreeNode()
    {
        data = -1;
        left = NULL;
        right = NULL;
    }
};
typedef class LSBinaryTreeNode lsbtNode;
typedef lsbtNode* lsbtNodePoint;

class LSBinaryTree
{
    lsbtNodePoint rootNode;
public:
    LSBinaryTree()
    {
        rootNode = NULL;
    }
    ~LSBinaryTree()
    {
        _DelAll(this->rootNode);
    }

    void add_Node_To_Tree(int value);
    int getLevel(); /*獲取此二元樹的Level/階度*/
    int getNodeCount();  /*獲取此二元樹的設定節點個數*/
    void ShowTheMin();
    bool Find(int num);
protected:
    int _getNodeCount(lsbtNodePoint p);
    int _getDepth(lsbtNodePoint p);
    void _ShowTheMin(lsbtNodePoint p);
    void _DelAll(lsbtNodePoint p);
    bool _Find(lsbtNodePoint p, int num);
};

void LSBinaryTree::add_Node_To_Tree(int value)
{
    lsbtNodePoint currentNode;
    lsbtNodePoint newnode;
    newnode = (lsbtNodePoint)malloc(sizeof(lsbtNode));
    newnode->data = value;
    newnode->left = NULL;
    newnode->right = NULL;
    if (this->rootNode == NULL)
    {
        rootNode = newnode;
    }
    else
    {
        currentNode = this->rootNode;
        while (true)
        {
            if (value <= currentNode->data) // 往左子樹
            {
                if (currentNode->left == NULL)
                {
                    currentNode->left = newnode;
                    return;
                }
                else
                {
                    currentNode = currentNode->left;    // 取左邊節點
                }
            }
            else     // 往右子樹
            {
                if (currentNode->right == NULL)
                {
                    currentNode->right = newnode;
                    return;
                }
                else
                {
                    currentNode = currentNode->right;   // 取右邊節點
                }
            }
        }
    }
}
int LSBinaryTree::getLevel()
{
    return _getDepth(this->rootNode);
}
int LSBinaryTree::getNodeCount()
{
    return _getNodeCount(this->rootNode);
}
void LSBinaryTree::ShowTheMin()
{
    return _ShowTheMin(this->rootNode);
}
bool LSBinaryTree::Find(int num)
{
    return _Find(this->rootNode, num);
}

int LSBinaryTree::_getNodeCount(lsbtNodePoint p)
{
    if (p != NULL)
    {
        return this->_getNodeCount(p->left) + this->_getNodeCount(p->right) + 1;
    }
    else
    {
        return 0;
    }
}
int LSBinaryTree::_getDepth(lsbtNodePoint p)
{
    if (p != NULL)
    {
        int ld = 1 + this->_getDepth(p->left);
        int rd = 1 + this->_getDepth(p->right);
        if (ld > rd)
        {
            return ld;
        }
        else
        {
            return rd;
        }
    }
    else
    {
        return 0;
    }
}

void LSBinaryTree::_ShowTheMin(lsbtNodePoint p)
{
    if (p)
    {
        _ShowTheMin(p->left);
        cout << p->data << endl;
        _ShowTheMin(p->right);
    }
}

void LSBinaryTree::_DelAll(lsbtNodePoint p)
{
    if (p)
    {
        _DelAll(p->left);   // 找最底的left
        free(p);            // 找到後ko它！
        _DelAll(p->right);  // the same
        free(p);
    }
}

bool LSBinaryTree::_Find(lsbtNodePoint p, int num)
{
    if (p)
    {
        if (num == p->data)
        {
            //cout << "Find!\n";
            return true;
        }
        else
        {
            if (num < p->data)  // 比node值小就search左邊
                _Find(p->left, num);
            else
                _Find(p->right, num);
        }
    }
    else
        return false;
}

void ch06_02(bool b)
{
    if (b)
    {
        int value = 0;
        LSBinaryTree btree;
        while (true)
        {
            cout << "請輸入節點值(輸入-1離開, 輸入-2查詢): ";
            cin >> value;
            if (value == -1)
                break;
            else if (value == -2)
            {
                cout << "查詢的數字為(-1為結束)：";
                cin >> value;
                if (value == -1)
                    break;
                else
                {
                    if (btree.Find(value) == false)
                        cout << "蝦米都沒有！\n";
                    else
                        cout << "Find\n";
                }
            }
            else
                btree.add_Node_To_Tree(value);
        }
        cout << ">>>你總共輸入 " << btree.getNodeCount() << " 個節點." << endl;
        cout << ">>>該二元樹階度為 " << btree.getLevel() << endl;
        btree.ShowTheMin();
    }
}

int main()
{
    ch06_02(true);
    return 0;
}