国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁(yè) > 學(xué)院 > 開發(fā)設(shè)計(jì) > 正文

二叉排序樹（建樹）

2019-11-14 10:10:11

字體：大中小

來(lái)源：轉(zhuǎn)載

供稿：網(wǎng)友

PRoblem Link：http://139.129.36.234/problem.php?id=1274

題目描述

二叉排序樹，也稱為二叉查找樹。先給你N個(gè)關(guān)鍵值各不相同的結(jié)點(diǎn)，要求那你按順序插入一個(gè)初始為空樹的二叉排序中，每次插入成功后，求相應(yīng)的父節(jié)點(diǎn)的關(guān)鍵字值，如果沒(méi)有父節(jié)點(diǎn)，則輸出-1.

輸入

第一行一個(gè)數(shù)字N(N<=100),表示待插入節(jié)點(diǎn)數(shù)。第二行，N個(gè)互不相同的正整數(shù)，表示要順序插入節(jié)點(diǎn)的關(guān)鍵字值，這些值不超過(guò)108

輸出

輸出一行N個(gè)數(shù)，分別表示每次插入節(jié)點(diǎn)后，該節(jié)點(diǎn)對(duì)于的父節(jié)點(diǎn)的關(guān)鍵字值。

樣例輸入

52 5 1 3 4樣例輸出
-1 2 2 5 3 提示
來(lái)源
北郵機(jī)試真題
AC code：
#include<iostream>#include<algorithm>#include<stdio.h>#include<map>#include<math.h>#include<string.h>#include<queue>#include<vector>#include<set>#define LL long long#define exp 1e-9#define MAXN 1000010using namespace std;typedef struct BTNode{	int data;	BTNode *lchild;	BTNode *rchild;}BTNode;void insertBT(BTNode *&bt,int x){	BTNode *pre,*p;	p=bt;	int dir=0;	if(p==NULL)	{		bt = (BTNode *)malloc(sizeof(BTNode));		bt->data=x;		bt->lchild=NULL;		bt->rchild=NULL;		printf("-1 ");	}	else	{		while(p!=NULL)		{			pre=p;			if(p->data>x)			{				p=p->lchild;			}			else			{				p=p->rchild;			}		}		p = (BTNode *)malloc(sizeof(BTNode));		p->data=x;		p->lchild=NULL;		p->rchild=NULL;		if(pre->data>x)		{			pre->lchild=p;		}		else		{			pre->rchild=p;		}		printf("%d ",pre->data);	}}int main(){//	freopen("D://in.txt","r",stdin);	int n,i,x;	scanf("%d",&n);	BTNode *bt=NULL;	for(i=1;i<=n;i++)	{		scanf("%d",&x);		insertBT(bt,x);	}	puts("");	return 0;}