手机版
你好,游客 登录 注册
背景:
阅读新闻

二叉排序树输出父节点值

[日期:2019-03-21] 来源:Linux社区  作者:MirrorN [字体: ]

题目描述
二叉排序树,也称为二叉查找树。可以是一颗空树,也可以是一颗具有如下特性的非空二叉树: 1. 若左子树非空,则左子树上所有节点关键字值均不大于根节点的关键字值; 2. 若右子树非空,则右子树上所有节点关键字值均不小于根节点的关键字值; 3. 左、右子树本身也是一颗二叉排序树。 现在给你N个关键字值各不相同的节点,要求你按顺序插入一个初始为空树的二叉排序树中,每次插入后成功后,求相应的父亲节点的关键字值,如果没有父亲节点,则输出-1。

输入描述:
输入包含多组测试数据,每组测试数据两行。
第一行,一个数字N(N<=100),表示待插入的节点数。
第二行,N个互不相同的正整数,表示要顺序插入节点的关键字值,这些值不超过10^8。

输出描述:
输出共N行,每次插入节点后,该节点对应的父亲节点的关键字值。

示例1
输入
5
2 5 1 3 4

输出
-1
2
2
5
3

代码&分析
开始的时候还想着是不是要改一下树的结构,用线索树那样类似的结构,后来一想根本不用啊,直接不断的刷新保存最后的父节点的值就好了啊。

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
typedef struct node{
    int key;
    struct node * left;
    struct node * right;
}Node, * Tree;
int s;
int n;
int sav = -1;
void ins(Tree &T ,int data){
    if(!T){
        T = (Tree)malloc(sizeof(Node));
        cout<<sav<<endl;
        T->key = data;
        T->left = NULL;
        T->right = NULL;
    }
    if(data < T->key){
        sav = T->key;            //插入的同时保存父节点的数值
        ins(T->left, data);
    }
    if(data > T->key){
        sav = T->key;
        ins(T->right, data);
    }
}
int main(){
    while(cin>>n){
        Tree T = NULL;
        for(int i=0; i<n; i++){
            cin>>s;
            ins(T, s);
        }
    }
}

二叉排序树输出父节点值

Linux公社的RSS地址https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址https://www.linuxidc.com/Linux/2019-03/157627.htm

linux
相关资讯       二叉排序树 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款