【学习笔记】排序二叉树

点击量: 53 次

排序二叉树的基本思路:从根节点建立一棵二叉树,此根节点的值为第一个待排序元素的值,在之后的每一次判断中,把大于所选中根节点的元素放到该根节点的右子树,以此类推建立一颗排序二叉树,大小关系为:左孩子值<根节点值<右孩子值。显然,遍历方式为二叉树的中序遍历。

#include<iostream>
using namespace std;
typedef int ElemType;
typedef struct TreeNode{
    ElemType data;
    struct TreeNode *l, *r; //定义左右子树
}TreeNode, *BSTree;
void insert(BSTree *ST, int data) //增加节点,建立树
{
    BSTree p;
    if(*ST == NULL) //如果是第一个元素则从此元素开始建立树
    {
        p = new TreeNode;
        p->data = data;
        p->l = NULL;
        p->r = NULL;
        *ST = p; //别把p给free掉哦
    }
    else if(data<(*ST)->data) //放左边
    insert(&(*ST)->l, data);
    else if(data>(*ST)->data || data == (*ST)->data) //放右边~后面那个判断条件可以不写,我写上主要是避免有重复值的情况被吞掉
    insert(&(*ST)->r, data);
}
void view(BSTree *ST) //中序遍历输出
{
    if(!*ST) return; //这句不要忘了!!受害者←
    view(&(*ST)->l);
    cout<<(*ST)->data<<" ";
    view(&(*ST)->r);
}
int main(void)
{
    int data, n;
    BSTree ST = NULL; 
    cin>>n; //要排序的个数
    for(int i=0; i<n; i++) //从每一次输入中开始排序
    {
        cin>>data;
        insert(&ST, data);
    }
    view(&ST);
    return 0;
}
一串神奇的代码 
下一篇:一串神奇的代码


点击开始摧毁这篇水文,方向键控制,空格发弹,Esc退出


pao.gifchui.gifpen.gifpai.gifhan.pngxia.pnghuaji.pngwa.pngbi.pngxin.pngleng.pnghua.pngmeng.pngjingya.pngqian.pnghan1.pngquan.pngnu.pnggan.pngdaxiao.pngku.pngqu.png



Proudly published with Typecho))).

Living (*>ω<*)

Copyright @ 2019 Kira's Blog



哎呀,穷死了,求赞赏!

支付宝
微信
QQ
0:00