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

C++实现将一个已知的二叉树转化为二叉排序树~

通过以下代码获取文件大小，然后分配相应大小的内存，一次性读取文件到此内存就可以加快读取速度了。具体代码如下： #include #include int main () { FILE * pFile; long lSize; char * buffer; size_t result; /* 若要一个byte不漏地读入整个文件，只能采用二进制方式打开 */ pFile = fopen ("test.txt", "rb" ); if (pFile==NULL) { fputs ("File error",stderr); exit (1); } /* 获取文件大小 */ fseek (pFile , 0 , SEEK_END); lSize = ftell (pFile); rewind (pFile); /* 分配内存存储整个文件 */ buffer = (char*) malloc (sizeof(char)*lSize); if (buffer == NULL) { fputs ("Memory error",stderr); exit (2); } /* 将文件拷贝到buffer中 */ result = fread (buffer,1,lSize,pFile); if (result != lSize) { fputs ("Reading error",stderr); exit (3); } /* 现在整个文件已经在buffer中，可由标准输出打印内容 */ printf("%s", buffer); /* 结束演示，关闭文件并释放内存 */ fclose (pFile); free (buffer); return 0; }

typed RcdType TElemType;
void Insert_BST( BiTree &T, KeyType e )
{ // 在以T为根指针的二叉排序树中插入记录e
s=new BiTNode; // 生成新的结点
s->data=e; s->lchild=NULL; s->rchild=NULL; //新插入结点必为叶
if(!T) T=s; // 插入的结点为根结点
else {
p=T;
while( p) // 查找插入位置
if(e .keydata .key)
{ f=p; p=p->lchild; } // 应插入在左子树中
else
{ f=p; p=p->rchild; } // 应插入在右子树中
if(e.keydata.key) f->lchild=s;//插入为f所指结点的左子树根
else f->rchild = s; // 插入为f所指结点的右子树根
} //else
} // Insert_BST
void BSTSort( SqList &L )
{ // 利用二叉排序树对顺序表L进行排序
BiTree T=NULL; // 初始化二叉排序树为空树
for(i=1;i<L.length;++i)
Insert_BST( T,L.r[i]); // 按顺序表L构造二叉排序树
i=0;
InOrder(T，Output(T,L,i)); // 中序遍历二叉排序树
//通过函数指针引用Output，将排序记录由小到大输出至L.r[i]
} // BSTSort
其中函数Output的具体实现如下：
void Output(BiTree T, SqList &L, int &i )
{ L.r[++i]=T->data; }

完成。

#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("
");
    return 0;
}

---

长岛县19871961891： 如何将一般二叉树变为二叉排序树 c语言 - ？
撒耐复方： #include /* 定义结构体 */ typedef int TypeData; typedef struct stBiTreeNode { TypeData data; struct stBiTreeNode *lchild, *rchild; }BITREENODE;/* * 函数功能:判断要插入的数据是否存在 * 函数参数:root 根节点 data 要查询的数据 lastNode 如果...

长岛县19871961891： C++实现将一个已知的二叉树转化为二叉排序树 - ？
撒耐复方： //建立二叉排序树void InsertBST(STreeNode *t,int key){ if(t==NULL) { t=new STreeNode; t->left_child=t->right_child=NULL; ...

长岛县19871961891： 把已经建立的二叉树转换成二叉排序树的算法实现(C++) - ？
撒耐复方： typed RcdType TElemType; void Insert_BST( BiTree &T, KeyType e ) { // 在以T为根指针的二叉排序树中插入记录e s=new BiTNode; // 生成新的结点 s->data=e; s->lchild=NULL; s->rchild=NULL; //新插入结点必为叶 if(!T) T=s; // 插入的结点为...

长岛县19871961891： C++实现将一个已知的二叉树转化为二叉排序树 - ？
撒耐复方： 通过以下代码获取文件大小,然后分配相应大小的内存,一次性读取文件到此内存就可以加快读取速度了.具体代码如下: #include#includeint main () { FILE * pFile; long lSize; char * buffer; size_t result; /* 若要一个byte不漏地读入整个文件,...

长岛县19871961891： 用C语言实现二叉排序树的构造 - ？
撒耐复方： #include <stdio.h>#include <stdlib.h> typedef struct bnode { int data; struct bnode *left , *right ; } btree ; void insert(btree **b , btree *s) { if(*b==NULL) *b = s ; else if((*b)->data == s->data) return ; else if(s->data > (*b)->data) insert(&(*b)->right , s); else...

长岛县19871961891： 试编写一个算法 将升序的二叉排序树变为降序的二叉排序树 - ？
撒耐复方： 将一棵根为root的升序二叉排序树转为降序二叉排序树,算法思路是:(1) 如果树root为空,算法结束;(2) 将root的左子树转为降序二叉排序树,将root的右子树转为降序二叉排序树;(3) 将root的左右孩子进行交换,即左孩子变为右孩子...

长岛县19871961891： 二叉排序树的实现(c语言)？
撒耐复方： /*二叉树的基本运算与实现*/#include <stdio.h>#include <malloc.h>#define MAXNODE 256typedef int datatype;typedef struct BiTNode{ datatype data; struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;typedef struct{ BiTree link; int flag;}stacktype; void ...

长岛县19871961891： 实现二叉排序树建立和检索算法(C语言)【急求】 - ？
撒耐复方： #include <stdlib.h>#include <time.h>#include <stdio.h>#define INFMT ＂%d＂#define OUTFMT ＂%d ＂/* #define NULL 0L */#define BOOL int#define TRUE 1#define FALSE 0#define LEN 10000 typedef int ElemType; typedef struct BSTNode { ...

长岛县19871961891： 用C语言实现二叉排序树的查找、插入和删除 - ？
撒耐复方： #include <stdio.h>#include <conio.h> #include <stdlib.h> typedef struct BitNode { char data; struct BitNode *lchild,*rchild; }BitNode,*BiTree; void CreateBiTree(BiTree &); //生成一个二叉树 void FirstOrder(BiTree); //先序递归遍历二叉树 void ...

长岛县19871961891： 实现二叉排序树的生成,完成二叉排序树的遍历、查找. 要求: - ？
撒耐复方： 利用c语言,代码如下仅供参考: 说明:为了保证输入的数据按要求构造出想要的、唯一确定的二叉树的形状,这里输入要求利用广义表的形式,虽然会显得繁琐一点,但足以保证严谨性.否则只是单纯一串数字,树形就能千变万化,不一定的...