Question

如何将一般二叉树变为二叉排序树 c语言

Answer 1

#include <stdio.h>
#include <string.h>
#include <stdlib.h>/* 定义结构体 */
typedef  int TypeData;
typedef struct stBiTreeNode 
{
    TypeData data;
    struct stBiTreeNode *lchild, *rchild;
}BITREENODE;/* 
* 函数功能：判断要插入的数据是否存在 
* 函数参数：root 根节点
            data 要查询的数据
            lastNode 如果没有找到，则返回查找最后一个节点
* 返回值： 0 存在 1 不存在 2 树是空树
*/int isDataAlreadyExist(BITREENODE* root, TypeData data,BITREENODE** lastNode)
{
    BITREENODE* temp = root;

    /* 如果根节点是空的，则直接返回 */
    if(!temp)
    {
        return 2;
    }

    while(1)
    {
        /* 如果存在直接返回 */
        if(temp->data == data)
        {
            return 0;
        }

        if(temp->data < data)
        {
            if(temp->rchild == NULL)
            {
                /* 把最后一个节点的地址返回出去 */
                (*lastNode) = temp;
                return 1;
            }
            temp = temp->rchild;
        }
        else
        {
            if(temp->lchild == NULL)
            {
                /* 把最后一个节点的地址返回出去 */
                (*lastNode) = temp;
                return 1;
            }
            temp = temp->lchild;
        }

    }
}/* 在二叉排序树中插入数据 */BITREENODE* createSortBiTree(BITREENODE* root,TypeData data)
{
    int ret = 0;
    BITREENODE* pLastNode = NULL;

    /* 判断要插入的数据是否存在 */
    ret = isDataAlreadyExist(root,data,&pLastNode);

    /* 如果已经存在了 */
    if(ret == 0)
    {
        return root;
    }

    /* 如果没有找到，就把这个插入 */
    if(ret == 1)
    {
        BITREENODE* pNewNode = (BITREENODE*)malloc(sizeof(BITREENODE));
        pNewNode->data = data;
        pNewNode->lchild = pNewNode->rchild = NULL;

        /* 插入到右孩子 */
        if(pLastNode->data < data)
        {
            pLastNode->rchild = pNewNode;
        }
        /* 插入到左孩子 */
        else if(pLastNode->data > data)
        {
            pLastNode->lchild = pNewNode;
        }

    }

    /* 根节点是空的,则新建一个根节点*/
    if(ret == 2)
    {
        BITREENODE* pNewNode = (BITREENODE*)malloc(sizeof(BITREENODE));
        pNewNode->data = data;
        pNewNode->lchild = pNewNode->rchild = NULL;

        root = pNewNode;
    }
    return root;
}/* 中序遍历该二叉排序树 */int inOrderBiTree(BITREENODE* root)
{
    if(root)
    {       
        inOrderBiTree(root->lchild);
        printf("%d ",root->data);
        inOrderBiTree(root->rchild);
    }
    return 0;
}

int main()
{
    BITREENODE* root = NULL;

    /* 在二叉排序树种插入数据 */
    root = createSortBiTree(root,20);
    root = createSortBiTree(root,30);
    root = createSortBiTree(root,10);
    root = createSortBiTree(root,25);

    inOrderBiTree(root);

    printf("\n");
    return 0;
}