二元樹

// ConsoleApplication2.cpp : 定義主控台應用程式的進入點。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

class treenode
{
public:
    int data;
    treenode *l, *r;
    treenode(int in){
        data = in;
        this->l = NULL;
        this->r = NULL;
    }
};

class Btree
{
public:
    treenode *root;
    Btree(){ root = NULL; }
    void Add_TreeNode(int);
    void in_order(treenode *pos);
    void pre_order(treenode *pos);
    void post_order(treenode *pos);
    void delnode(int value);
};

void Btree::Add_TreeNode(int value)
{
    //cout << "root:" << root << endl;
    if (root == NULL)
    {
        root = new treenode(value);
        cout << "root value=" << root->data << endl;
    }
    else
    {
        //cout << "rootvalue" << root->data << endl;
        //cout << "rootl:" << root->l << endl;
        treenode *pos = root;
        while (true)
        {
            /*
            cout << "posl:" << pos->l << endl;
            cout << "posr:" << pos->r << endl;
            cout << "pos=" << pos << endl;
            */
            if (value < pos->data)
            {
                if (pos->l != NULL)
                {
                    pos = pos->l;
                }
                else
                {
                    pos->l = new treenode(value);
                    cout << "add " << value << " at " << pos->l << endl;
                    return;
                }
            }
            else
            {
                if (pos->r != NULL)
                {
                    pos = pos->r;
                }
                else
                {
                    pos->r = new treenode(value);
                    cout << "add " << value << " at " << pos->r << endl;
                    return;
                }
            }
        }
    }
}

void Btree::in_order(treenode *pos)
{
    if (pos != NULL)
    {
        in_order(pos->l);
        cout << "[" << pos->data << "]";
        in_order(pos->r);
    }
}
void  Btree::pre_order(treenode *pos)
{
    if (pos != NULL)
    {
        cout << "[" << pos->data << "]";
        pre_order(pos->l);
        pre_order(pos->r);
    }
}

void  Btree::post_order(treenode *pos)
{
    if (pos != NULL)
    {
        post_order(pos->l);
        post_order(pos->r);
        cout << "[" << pos->data << "]";
    }
}

void Btree:: delnode(int value)
{
    cout << "pop " << value << endl;
    treenode *pos = root,*del=pos;
    if (root == NULL)
    {
        cout << "empty tree\n";
        return;
    }
    while (true)
    {
        if (del == NULL)
        {
            cout << "can't find this value\n";
            return;
        }
        else if (del->data != value)
        {
            pos = del;
            if (value>del->data)
                del = del->r;
            else
                del = del->l;
        }
        else
        {
            if (del->l == NULL&&del->r == NULL)
            {
                cout << "delete" << del->data << endl;
                delete del;
            if (value > pos->data)
                pos->r = NULL;
            else
                pos->l = NULL;
            return;
            }

        }
    }
}

int main()
{
    Btree tr1;
    const int listnum = 6;
    int list[listnum] = {8,17,31,9,98,12};
    for (int i = 0; i < listnum; i++)
        tr1.Add_TreeNode(list[i]);
    cout << "inorder:";
    tr1.in_order(tr1.root);
    cout << "\npreorder:";
    tr1.pre_order(tr1.root);
    cout << "\npostorder:";
    tr1.post_order(tr1.root);
    cout << endl;

    tr1.delnode(9);
    return 0;
}