二叉搜索树（BST）的建立和 前序和中序遍历

文件:	BST_operation.zip
大小:	3KB
下载:	下载

//这里我要建立一棵二叉排序树
//实现插入，删除的功能
//再用前根序遍历，中序遍历，后续遍历
//下一步增加AVL树的功能

//bobzhang.wiki.zoho.com  ， kernelchina.cublog.cn
//编译：gcc -o bst_operation tree_operation.c stack_lib.c
//因为我们都是在linux工作的， 所以这里的风格完全用的kernel代码的风格，尤其
//是INIT_NODE() 宏，DECLARE_BST_TREE()等等， 都是kernel代码的风格
//从我们工作的实践来看，这种风格确实是非常可读性非常好
//BobZhang

 

//还有我们也可以考虑 既然有bst_node_t ，为什么还要定义bst_tree_t ?
//事实上，不定义bst_tree_t 完全可以，只是我们说的时候，都是往树里面插入节点
//从这个角度来说，我觉得int bst_insert(bst_tree_t *tree, bst_node_t *node)  就更好
//否则写成： int bst_insert(bst_node_t *root, bst_node_t *node)
//虽然root节点就代表一棵树，但是还是不直观
//所以专门定义一个bst_tree_t 类型


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "stack_lib.h"    //我自己实现的栈，可以查阅 http://blog.chinaunix.net/u/22617/showart.php?id=1387160 


typedef struct bst_node
{    //标准的二叉链表

    void *data_p;                //数据项指针，兼容所有类型，测试例子用的int型

    struct bst_node *left;        //左孩子

    struct bst_node *right;        //右孩子

}bst_node_t;

//这样包起来，好处多多， 实现起来非常自然

typedef struct bst_tree
{
    bst_node_t *root;
}bst_tree_t;

#define INIT_BST_NODE(node,ptr) \
        node->data_p = ptr;            \
        node->left = NULL;            \
        node->right= NULL;


//声明一个节点

#define DECLARE_BST_NODE(name,ptr) \
    bst_node_t *name = (bst_node_t *)malloc(sizeof(bst_node_t));\
    assert(name);        \
    INIT_BST_NODE(name,ptr);
    

//声明一个二叉树

#define DECLARE_BST_TREE(bstree_name) \
    bst_tree_t *bstree_name = (bst_tree_t *)malloc(sizeof(bst_tree_t)); \
    INIT_BST_TREE(bstree_name); \


//一棵空树

static inline int INIT_BST_TREE(bst_tree_t *tree)
{
    //这个和链表的操作是多少有些差异的

    tree->root = NULL;

    return 0;
}


int bst_insert(bst_tree_t *tree, bst_node_t *node) ;
int inorder_traverse(bst_node_t *root) ;


//要在二叉树中插入节点

//一开始其实就是遍历，左走右走， 直到找到一个叶节点，如果item 值大于叶节点值，就生成一个节点作为该叶节点的有节点，

//否则就是左节点


int bst_insert(bst_tree_t *tree, bst_node_t *node)
{
    //p是t的父节点

    bst_node_t * p = NULL;
    bst_node_t * t = tree->root;
    
    if(!t) {
        //原来是空树

        printf("old is empty tree\n");
        tree->root = node;
        return 0;
    }
    
    
    //开始遍历二叉树

    while(t) {

        p =t ;
        if (*(int *)(node->data_p) < *(int *)(t->data_p))
            t = t->left;
        else
            t = t->right;
    }
    

    //判断t到底是p的左节点还是有节点？
    if (*(int *)(node->data_p) < *(int *)(p->data_p))
        p->left = node;
    else
        p->right = node;
        

    return 0;
}

//递归实现中序遍历

//递归的基本情况：根节点为空

//递归情况：遍历左右子树


int inorder_traverse(bst_node_t *root)
{
    //空二叉树的情况,递归的基本情况

    if(!root)
        return 0;
    
    //不为空

    inorder_traverse(root->left);
    printf("%d\n",*(int *)(root->data_p));
    inorder_traverse(root->right);
    
    return 0;
}


//非递归实现前根序遍历二叉树

int preorder_traverse(bst_tree_t *tree)
{
    DECLARE_STACK(RCHILD_STACK);
    node_t * node = NULL;
    int ret = 0;

    bst_node_t * tmp_btnode = tree->root;
//肯定可以用while()循环来代替goto ，但是那样我觉得理解起来没有goto LOOP这样更直接，自然
//不要跟我讨论goto 容易混乱的弊病，kernel 代码里面可都是goto 居多，尤其是跳转来handle error
LOOP:

        //入栈就是右子树的地址，因为node_t 里面的data_p 是 void *

        while(tmp_btnode)
        {
            DECLARE_NODE(right_node,tmp_btnode->right);

            printf("Node value = %d\n",*(int *)(tmp_btnode->data_p));
            //右子树入栈

            push(RCHILD_STACK,right_node);
            tmp_btnode = tmp_btnode->left;
        }


        ret = pop(RCHILD_STACK,&node); //弹出右子树

        if(!ret)
        { //说明不是空栈

            tmp_btnode = (bst_node_t *)(node->data_p);
            free(node); //必须释放这个节点

            goto LOOP;
        }

        free_stack(RCHILD_STACK); //现在栈没有用了，要释放


        return 0;
    }


//递归实现前根序遍历

int preorder_traverse2(bst_node_t *root)
{
    if(!root)
        return -1;
    
    printf("%d\n",*(int *)(root->data_p));
    preorder_traverse2(root->left);
    preorder_traverse2(root->right);
    
    return 0;
}
int main(void)
{
    int v1 = 10;
    int v2 = 20;
    int v3 = 30;
    int v4 = 40;
    int v5 = 50;
    int v6 = 60;
    int v7 = 70;
    
    DECLARE_BST_NODE(node1,&v1);
    DECLARE_BST_NODE(node2,&v2);
    DECLARE_BST_NODE(node3,&v3);
    DECLARE_BST_NODE(node4,&v4);
    DECLARE_BST_NODE(node5,&v5);
    DECLARE_BST_NODE(node6,&v6);
    DECLARE_BST_NODE(node7,&v7);
    
    DECLARE_BST_TREE(bst_tree);    //现在是一颗空树

    
    
    //插入建立一个二叉排序表

    bst_insert(bst_tree,node5);
    bst_insert(bst_tree,node2);
    bst_insert(bst_tree,node7);
    bst_insert(bst_tree,node1);
    bst_insert(bst_tree,node4);
    bst_insert(bst_tree,node6);
    bst_insert(bst_tree,node3);
    
    
    //再中根序遍历此而查表

    printf("in order traverse \n");
    inorder_traverse(bst_tree->root);
    
    printf("pre order traverse \n");
    preorder_traverse(bst_tree);
    
    printf("pre order traverse ,recurse \n");
    preorder_traverse2(bst_tree->root);    
    
    return 0;
}

 

 

输出结果：

old is empty tree
in order traverse
10
20
30
40
50
60
70
pre order traverse
Node value = 50
Node value = 20
Node value = 10
Node value = 40
Node value = 30
Node value = 70
Node value = 60
this is empty stack
pre order traverse ,recurse
50
20
10
40
30
70
60

 

 

 

再给一个别人的 程序， 虽然里面有AVL字样， 但是实际上和我上面的程序是一样的， 是用c++实现的：

 

//程序名称：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;

}

//插入结点函数

//r：树的根节点

//p:待插入节点

void InsertNode(AvlBitree *r,AvlBitree *p)
{
    //定一个哨兵flag，当flag=1时，在右孩子处加入结点，当flag=-1时在左孩子处加入

    int flag;
    
    //插入当前结点

    //r为根结点，p为新插入结点

    //定义一个q作为当前工作指针，定义一个指针t指向q的父结点

    AvlBitree *t,*q;
    //t,q都指向根结点

    t = q = r;
    
    //开始循环查找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;
}