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

bob_zhang2004

文件:
BST_operation.zip
大小:
3KB
下载:
下载
//这里我要建立一棵二叉排序树
//实现插入，删除的功能
//再用前根序遍历，中序遍历，后续遍历
//下一步增加AVL树的功能
//bob.zhang2004@gmail.com
//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 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;
}


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/22617/showart_1386992.html