二叉树.txt

建立一棵二叉树

//程序名称：AVL平衡二叉树构建程序  
//文件名称：avl.cpp                   
//作    者：CityWildWolf                         
//建立时间：2007-5-29                          
//修改时间：                                            
//程序说明：                                           
//                                                                
//                                                                  
/**//////////////////////////////////////////////////////////////////////


#include <iostream>

#define NODELEFT -1                //指示插入的位置为工作指针的左孩子
#define NODERIGHT 1                //指示插入的位置为工作指针的右孩子

using namespace std;



//二叉树数据结构
struct   AvlBitree
...{
    
    int   value;                   //结点值 
    int blanceRank;                //结点平衡因子
    struct   AvlBitree   *right;   //左孩子  
    struct   AvlBitree   *left;    //右孩子 
};  

//函数原型
int PrintMenu();
AvlBitree* BuildTree(AvlBitree *);
AvlBitree* CreatNode(int );
void InsertNode(AvlBitree *,AvlBitree *);
void Traveser(AvlBitree *r);
 

//主函数，程序入口
int main()
...{
    //定义一个根结点
    AvlBitree *root = NULL;
    //在屏幕打印菜单，让用户选择建立、遍历、查找功能
    int userChoseMenu;
    while (userChoseMenu = PrintMenu())
    ...{
        //
        switch (userChoseMenu)
        ...{
            case 1 : 
                cout << "你选择了1，开始建AVL！" << endl;
                root = BuildTree(root);
                break;
            case 2 :
                cout << "你选择了2，给AVL加结点！" << endl;
                break;
            case 3 :
                cout << "你选择了3，遍历输出AVL。" << endl;
                Traveser(root);
                //cout << root->value;
                break;
            case 4 :
                cout << "你选择了4！" << endl;
                break;
            default :
                cout << "你选择了其他！" << endl;
                break;
        }
    }
    
    //程序结束，退出程序
    //
    return 0;
}

//在屏幕打印菜单函数
int PrintMenu()
...{
    int userChose;
    cout << "-----------------------" << endl;
    cout << "1. Creat a New AVL Tree" << endl;
    cout << "2. Add New Node To AVL " << endl;
    cout << "3. Travesers the AVL   " << endl;
    cout << "4. Find The Node In AVL" << endl;
    cout << "-----------------------" << endl;
    cout << "Enter Your Chose:";
    cin >> userChose;
    return userChose;
}


//新建二叉树函数
AvlBitree* BuildTree(AvlBitree *r)
...{
    //如果传入根结点不为空，则树已构建过，退出函数 
    if (r != NULL)
    ...{
        cout << "AVL Tree has been built!";
        return NULL;
    }
    
    //根结点为空则开始构建
    //AvlBitree *p = *r;
    cout << "请输入结点值，输入零则结束" << endl;
    int nodeValue;
    cin >> nodeValue;
    while  (nodeValue)
    ...{
        //建立新结点
        AvlBitree *node = CreatNode(nodeValue);
        //如果根为空，则将此结点设置为根结点 
        if (r == NULL)
        ...{
            r = node;
        }
        //否则将此结点作为非根结点插入 
        else
        ...{
            InsertNode(r,node);
        }
        //输入新值
        cin >> nodeValue;
    }
    return r;
    
}

//插入结点函数
void InsertNode(AvlBitree *r,AvlBitree *p)
...{
    //插入当前结点 
    //r为根结点，p为新插入结点
    //定义一个q作为当前工作指针，定义一个指针t指向q的父结点 
    AvlBitree *t,*q;
    //t,q都指向根结点 
    t = q = r;
    //定一个哨兵flag，当flag=1时，在右孩子处加入结点，当flag=-1时在左孩子处加入 
    int flag;
    //开始循环查找p应该插入的位置，当工作指针q指向空时，此位置为插入位置 
    while (q != NULL)
    ...{
        if(p->value > q->value)
        ...{
            //右移
            t = q;
            q = q->right;
            cout << "Right once" << endl;
            flag = NODERIGHT;
        }
        else if (p->value < q->value)
        ...{
            //左移
            t = q;
            q = q->left;
            cout << "Left once" << endl;
            flag = NODELEFT;
        }
        else
        ...{
            return;
        }
    }
    //插入该结点
    //如果该插入的位置为t的左孩子 
    if (flag == NODERIGHT)
    ...{
        t->right = p;
    }
    //如果该插入的位置为t的右孩子
    else if(flag == NODELEFT)
    ...{
        t->left = p;
    }    
}



//递归先跟遍历二叉树
void Traveser(AvlBitree *r)
...{     
     if(r->left) Traveser(r->left);
     if(r) cout << r->value << endl;
     if(r->right) Traveser(r->right);     
}

//建立新结点
AvlBitree* CreatNode(int nodeValue)
...{
    AvlBitree *node; 
    node = (AvlBitree *)malloc(sizeof(AvlBitree));
    node->value = nodeValue;
    node->blanceRank = 0;
    node->left = NULL;
    node->right = NULL;
    return node;
}