二叉排序树怎么构造_建立二叉排序树_怎么画二叉排序树

二叉树是数据结构中的重要内容之一，这里把自己做的一个练习题目写出来，方便回顾和交流。建立二叉排序树程序使用C语言实现，使用的IDE是Visual Studio 2010。

随机生成N个整数，N>20，建立二叉排序树；

以树的形式输出建立好的二叉排序树

删除第十个输入的数据，并以树的形式输出以后的二叉排序树

首先，定义一个二叉树的结构体：

//定义二叉排序树节点结构
typedef struct BiTNode
{
    char data;  //存储数据
    struct BiTNode *lchild, *rchild;  //左右孩子指针
}BiTNode, *BiTree;

BiTree T;  //定义二叉排序树T 

因为生成二叉树需要调用，插入函数就先写在这里。

void Insert(BiTree &BST,BiTNode *s)
{
    BiTree t;
    t = SearchBST(BST, s->data);
    //若s的关键字不在T中出现，则插入
    if (!t)
    {
        if (BST == NULL) BST = s;   //空树时作为根节点
        else if (s->data<BST->data)
            Insert(BST->lchild, s);  //将s插入T的左子树
        else
            Insert(BST->rchild, s);  //将s插入T的右子树
    }
}

采用头插法，即从根部开始调用Insert()函数实现。

BiTree Create(int n, int *num)
{   //建立n个关键字的二叉排序树
    //用Insert函数插入，再返回根结点T
    int i;      
    BiTree s;       
    T = NULL;  //空树
    for (i = 0; i<n; i++)
    {
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = num[i];
        s->lchild = NULL;
        s->rchild = NULL;
        Insert(T, s);   //插入
    }
    return T;
}

//查找二叉树中元素
BiTree SearchBST(BiTree BST, int key)
{  //在根指针T中递归查找关键字等于key的数据元素
   //如果如果成功返回该元素结点的指针，否则返回空指针
    BiTree s;
    if (BST == NULL) return NULL;
    if (BST->data == key) s = BST;
    else if (BST->data>key)  
    //key小于当前节点的关键字，则查找左子树
        s = SearchBST(BST->lchild, key);    
    else
        s = SearchBST(BST->rchild, key);
    return s;
}

//前序遍历二叉树
void prorder(BiTree &BT)
{
    if (BT != NULL)
    {
        printf("%3d ", BT->data);  //访问结点
        prorder(BT->lchild);
        prorder(BT->rchild);
    }
}

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-32053-1.html