Kafka IntelliJ IDEA JavaSE NTFS权限 摩尔投票法 Opencv windows wcf xpath razor parameters tags Pure CSS Vanilla JS vue开发 sketch up教程 ppt视频教程下载 git视频 less官网 idea全文搜索快捷键 kali重启网卡 kafka启动命令 kubernetes架构 python中get函数 python中不等于 javafinally 如何安装java环境 java怎么编译 网站数据分析工具 r语言和python 主板排名天梯图 风火云 七宗罪游戏下载 flash基础 生存猎人属性 js正则匹配字符串 文章查重软件 c4d挤压 怎么看淘龄 oracle表分区
当前位置: 首页 > 学习教程  > 编程语言

构建有序树

2021/1/13 20:27:34 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

构建有序树思路代码实现运行结果思路 假设有一颗已经构建好的有序二叉树了,你有一个新节点n需要添加到树中。而构建一棵有序树,那就是从根节点开始,你要做的是找一个合适的位置放置新节点。 新节点n->data与树中某节点node->data比大…

构建有序树

    • 思路
    • 代码实现
    • 运行结果

思路

假设有一颗已经构建好的有序二叉树了,你有一个新节点n需要添加到树中。而构建一棵有序树,那就是从根节点开始,你要做的是找一个合适的位置放置新节点。

  1. 新节点n->data与树中某节点node->data比大小,若 n->data < node->data,往左走。否则往右走。
  2. 如果是往左找,若该node节点的左孩子是空的,那这个空就是我要插入的位置,若不为空,就接着比,跳转到左子树(node=node->left;),继续做第一步。
    3.如果往右找,同第二步,跳转(node=node->right)。

代码实现

  1. 有俩个结构体:第一个treeNode,表示树的节点,其中包含int类型的data域、指向自身类型的left(左孩子)和right(右孩子)。第二个Tree,表示树类型,其中包含一个指向treeNode类型的root(根节点)。
typedef int ElementType;
struct treeNode{
    ElementType data;
    treeNode *left,*right;
};
struct Tree{
    treeNode *root;
};
  1. 插入函数(构建函数)
/*
*插入节点函数,大数放右边,小数放左边*
*两个参数,第一个传入树指针,第二次传入要插入的值
*/
void insert(Tree *tree,int val){	
    if(tree==NULL){ //为空判断
        return ;
    }
    
    treeNode *node=new treeNode();//为插入的节点开辟空间
    node->data=val;				  //初始化
    node->left=NULL;
    node->right=NULL;
    
    if(tree->root==NULL){       //是空树
        tree->root=node;
    }else{                      //不是空树
        treeNode *temp=tree->root; //用于遍历树的变量
        while(temp){			//等价于temp!=NULL
            if(temp->data<val){	//val大,往右走
                if(temp->right==NULL){	//右孩子为空,直接插入
                    temp->right=node;
                    return;	           //退出
                }else{
                    temp=temp->right;	//否则继续往右子树比
                }
            }
            else{
                if(temp->left==NULL){	//左孩子为空,直接插入
                    temp->left=node;
                    return ;
                }else{
                    temp=temp->left;	//否则继续往左子树比
                }
            }
        }
    }
}

3.遍历函数(为了方便,使用中序遍历,输出结果为有序数列)

void midVisit(treeNode *node){
    if(node==NULL){
        return ;
    }
    else{

        midVisit(node->left);
        cout<<node->data<<" ";
        midVisit(node->right);
    }
}

4.主函数(测试函数)

int main()
{
    int n,val;
    cout<<"输入规模n : ";
    cin>>n;
    Tree *tree=new Tree();
    tree->root=NULL;
    cout<<"输入n个整数 :";
    for(int i=0;i<n;i++){
        cin>>val;
        insert(tree,val);
    }
    cout<<endl<<"结果为:";
    midVisit(tree->root);
    return 0;
}

运行结果

结果截图


本文链接: http://www.dtmao.cc/news_show_600324.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?