输入包含多组测试数据,每组测试数据两行。 第一行,一个数字N(N<=100),表示待插入的节点数。 第二行,N个互不相同的正整数,表示要顺序插入节点的关键字值,这些值不超过10^8。
输出共N行,每次插入节点后,该节点对应的父亲节点的关键字值。
5 2 5 1 3 4
-1 2 2 5 3
#include <iostream> using namespace std; struct node{ int num; node *left=NULL; node *right=NULL; }; node* insert(node *t,int num,int store){ if(t==NULL){ cout<<store<<endl; t=new node(); t->num=num; return t; } if(num<t->num) t->left=insert(t->left,num,t->num); else t->right=insert(t->right,num,t->num); return t; } int main(){ int n; scanf("%d",&n); int st[n]; for(int i=0;i<n;i++) scanf("%d",&st[i]); node *t=new node(); t->num=st[0]; cout<<-1<<endl; for(int i=1;i<n;i++) t=insert(t,st[i],-1); return 0; }
#include<iostream> using namespace std; typedef struct Btree { int v; Btree * lchild,*rchild; Btree(int v):v(v){} }; Btree * insert(Btree * t,int v,int farther)//v为当前插入的节点 { if(t == NULL)//插入都在叶节点 { t = new Btree(v); cout << farther << endl; } else if(v < t->v) t->lchild = insert(t->lchild, v, t->v); else t->rchild = insert(t->rchild, v, t->v); return t; } int main(void) { int n; while(cin >> n) { Btree * t; for(int i = 0;i < n;i++) { int v; cin >> v; t = insert(t, v, -1);//从根开始,没有父亲节点输出-1 } } return 0; }
#include <iostream> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; /** * @brief * * @param T * @param key * @return TreeNode */ TreeNode *InsertBST(TreeNode *T,TreeNode *TFather, int val) { if (T == NULL) { cout << TFather->val << endl; T = new TreeNode(val); // T->val = val; // T->left = T->right = NULL; return T; } else if (val < T->val) { T->left = InsertBST(T->left, T,val); } else if (val > T->val) { T->right = InsertBST(T->right,T, val); } return T; } int main() { int n; while (cin >> n) { int val; bool first = true; TreeNode root(val); cout << -1 << endl; while (n--) { cin >> val; if (first) { root.val = val; first = false; } InsertBST(&root, NULL,val); } } return 0; }
/* *仍然是模拟排序树创建过程,插入函数每次保留一下父节点即可。 */ #include<bits/stdc++.h> using namespace std; struct Node { int v; struct Node* lchild,* rchild; }; int n; Node* newNode(int x) { Node* t = new Node; t->v = x; t->lchild = t->rchild = nullptr; return t; } void Insert(Node*& root, int x, int f) { if(root == nullptr) { cout << f << '\n'; root = newNode(x); return ; } if(root->v == x) return ; else if(root->v < x) Insert(root->rchild, x, root->v); else Insert(root->lchild, x, root->v); } int main() { ios::sync_with_stdio(false); while(cin >> n) { int x; Node* root = nullptr; while(n--) { cin >> x; Insert(root, x, -1); } } return 0; }
#include<iostream> using namespace std; struct TNode { int data; TNode* left, * right; TNode(int d) :data(d), left(nullptr), right(nullptr) {} }; int Insert(int node, TNode*& tree)//tree必须要用引用类型 { int father = -1; TNode* move = tree, * parent = nullptr; while (move != nullptr)//找要插入节点的父节点 { parent = move; father = move->data; if (node > move->data) move = move->right; else move = move->left; } TNode* temp = new TNode(node);//临时节点 if (parent == nullptr)//插入到二叉排序树中 tree = temp; else if (node < parent->data) parent->left = temp; else parent->right = temp; return father; } int Insert2(int node, TNode*& tree, int& father)//递归 { if (tree == nullptr) tree = new TNode(node); else { father = tree->data; if (node < tree->data) Insert2(node, tree->left,father); else Insert2(node, tree->right,father); } return father; } int main() { int N, node; while (cin>>N) { TNode* tree = nullptr; int father = -1; for (int i = 0; i < N; i++) { cin >> node; //cout << Insert(node, tree) << endl; cout << Insert2(node, tree, father) << endl; } } return 0; }
//照搬一下讨厌鬼大佬的题解, 增加一下印象 #include<stdio.h> typedef struct TNode{ int data; struct TNode *left; struct TNode *right; }*BiTree,TNode; int loc; TNode T[101]; //建树 BiTree create() { T[loc].left=T[loc].right=NULL;//初始化空树 return &T[loc++]; } //增加结点 BiTree Insert(BiTree T,int x,int father) { if(!T){ T=create();//建树 T->data=x; printf("%d\n",father); return T; } if(x<T->data) T->left=Insert(T->left,x,T->data); if(x>T->data) T->right=Insert(T->right,x,T->data); return T; } int main() { int n,tmp; while(scanf("%d",&n)!=EOF) { TNode *T=NULL; loc=0; for(int i=0;i<n;i++) { scanf("%d",&tmp); T=Insert(T,tmp,-1); } } return 0; }
import java.util.Scanner; public class Main { static class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int val) { this.val = val; } } static void creat(TreeNode root, int value){ if (value<root.val){ if (root.left==null) { root.left = new TreeNode(value); System.out.println(root.val); } else creat(root.left,value); }else { if (root.right==null){ root.right= new TreeNode(value); System.out.println(root.val); }else creat(root.right,value); } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()){ int n = scanner.nextInt(); TreeNode root = new TreeNode(scanner.nextInt()); System.out.println("-1"); for (int i = 1; i < n; i++) { creat(root,scanner.nextInt()); } } } }
#include <bits/stdc++.h> using namespace std; struct TreeNode{ int data; TreeNode* lChild; TreeNode* rChild; TreeNode(int data):data(data),lChild(NULL),rChild(NULL){} }; // 二叉排序树建树,将key插入二叉排序树中的正确位置 TreeNode* Insert(TreeNode*& root,int key,int father){ if(root==NULL){ // 找到叶子节点,此时插入节点成功,那么直接输出其父节点的值 root = new TreeNode(key); cout<<father<<endl; }else{ if(key<root->data){ root->lChild = Insert(root->lChild,key,root->data); }else{ root->rChild = Insert(root->rChild,key,root->data); } } return root; } int main(){ int n; while(cin>>n){ TreeNode* root = NULL; // 建立空树 for(int i=0;i<n;i++){ int key; cin>>key; root = Insert(root,key,-1); } } return 0; }
#include <string> #include <iostream> #include <algorithm> using namespace std; struct ptree{ long int v; ptree * lc; ptree * rc; }; void inserttree(ptree * a,int b){ if(b>a->v){ //如果插入数据比当前节点值大,插入右子树 if(a->rc==NULL){ //如果右子树为空则插入 ptree * node=(ptree *)malloc(sizeof(ptree)); //创建节点 a->rc=node; //右孩子指向该节点 node->v=b; node->lc=NULL;node->rc=NULL; } else inserttree(a->rc,b); } else{ if(a->lc==NULL){ //否则插入左子树 ptree * node=(ptree *)malloc(sizeof(ptree)); a->lc=node; //左孩子指向该节点 node->v=b; node->lc=NULL;node->rc=NULL; } else inserttree(a->lc,b); } } int outputf(ptree * a,int b){ //遍历时,输入头节点和要查找的值 if(a->v!=b){ //如果头节点值不等于目标值 ptree * node,* p=a; while(p->v!=b){ //遍历 node=p; //记录前一个节点 if(b>p->v) p=p->rc; else p=p->lc; } return node->v; //返回前一个节点值 } else return -1; //若头节点值等于目标值,返回 -1 } int main() { int N; cin>>N; long int a[N]; for(int i=0;i<N;i++){ cin>>a[i]; } ptree * head; head=(ptree *)malloc(sizeof(ptree)); //构建第一个节点 head->v=a[0]; head->lc=NULL;head->rc=NULL; //设置孩子指针为空 for(int i=1;i<N;i++){ //插入数据 inserttree(head,a[i]); } for(int i=0;i<N;i++){ //查找数据 long int n=outputf(head,a[i]); cout<<n<<endl; } return 0; }
注意:
(1)插入的时候要保存父节点的值
(2)开始新的一棵树的时候要将原来的二叉树的值清空
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef struct BiNode{
int v;
struct BiNode *lchild, *rchild;
}BiNode, *BiTree;
int Insert(BiTree &T, int tmp, int pre)
{
if(T==NULL){
T = (BiTree)malloc(sizeof(BiNode));
T->v = tmp;
T->lchild = T->rchild = NULL;
return pre; //插入节点的时候返回父节点
}
else{
if(tmp<T->v) return Insert(T->lchild, tmp, T->v);
else return Insert(T->rchild, tmp, T->v);
}
}
void Delete(BiTree &T) //清空二叉树
{
if(T!=NULL)
{
if(T->lchild==NULL && T->rchild == NULL)
free(T);
else{
if(T->lchild!=NULL) Delete(T->lchild);
if(T->rchild!=NULL) Delete(T->lchild);
}
}
T = NULL;
}
int main()
{
BiTree T = NULL;
int n;
while(cin>>n)
{
for(int i = 0; i<n; i++)
{
int tmp;
cin>>tmp;
cout<<Insert(T, tmp, -1)<<endl; //插入操作多一个参数存放父节点
}
Delete(T);
}
return 0;
}
#include<cstdio> #include<iostream> using namespace std; struct Node{ int val; Node*left=NULL; Node*right=NULL; }; void buildTree(Node*&r,int a){ if(r==NULL){ r=new Node; r->left=r->right=NULL; r->val=a; cout<<"-1"<<endl; } else{ if(a<r->val){ if(r->left==NULL){ Node*tmp=new Node; //左子树为空,就申请一个节点挂上去, tmp->left=tmp->right=NULL; tmp->val=a; r->left=tmp; cout<<r->val<<endl; } else{ buildTree(r->left,a); } } else{ if(r->right==NULL){ Node*tmp=new Node; tmp->left=tmp->right=NULL; tmp->val=a; r->right=tmp; cout<<r->val<<endl; } else buildTree(r->right,a); } } } int main(){ int n; int a; while(cin>>n){ Node*root=NULL; while(n--){ cin>>a; buildTree(root,a); } } }
#include <stdio.h> #include <stdlib.h> typedef struct BTNode{ int data; struct BTNode *lchild; struct BTNode *rchild; }BTNode; /* 二叉排序树插入操作 */ BTNode* BST_Insert(BTNode *T,int x){ if(T==NULL){ T = (BTNode*)malloc(sizeof(BTNode)); T->data = x; T->lchild = T->rchild = NULL; return T; }else if(x < T->data){ T->lchild = BST_Insert(T->lchild,x); }else { T->rchild = BST_Insert(T->rchild,x); } return T; } /* 先序遍历二叉树 */ void PrintBT(BTNode *T){ if(T!=NULL){ printf("%d ",T->data); PrintBT(T->lchild); PrintBT(T->rchild); } } /* 打印其父节点的值 */ void PrintFather(BTNode *T,int x){ if(T!=NULL){ if((T->lchild != NULL && T->lchild->data == x) || (T->rchild!=NULL && T->rchild->data == x)){ //别忘了左右判断左右子树 均非空才行 printf("%d\n",T->data); return; } PrintFather(T->lchild,x); PrintFather(T->rchild,x); } } int main(){ int n,x; while(scanf("%d",&n) != EOF){ BTNode *T = NULL; for(int i=0;i<n;i++){ scanf("%d",&x); T = BST_Insert(T,x); if(i==0){ printf("-1\n"); }else{ PrintFather(T,x); } } // PrintBT(T); //前序打印二叉树 } return 0; } //DEV 正常,然而却说我只有1%的通过
#include<stdio.h> #include<stdlib.h>
typedef struct Bnode {
int data;
struct Bnode* lchild;
struct Bnode* rchild;
}Bnode;
Bnode* insert(Bnode *T, int d, int &f)//在插入的时候顺便记录父节点的数据
{
if (T == NULL)
{
T = (Bnode*)malloc(sizeof(Bnode));
T->data = d;
T->lchild = NULL;
T->rchild = NULL;
}
else if (T->data>d)
{
f = T->data;
T->lchild = insert(T->lchild, d, f);
}
else
{
f = T->data;
T->rchild = insert(T->rchild, d, f);
}
return T;
}
int main()
{
int n, f, d;
while (scanf("%d", &n) != EOF)
{
Bnode *T = NULL;
for (int i = 0; i<n; i++)
{
f = -1;
scanf("%d", &d);
T = insert(T, d, f);
printf("%d\n", f);
}
}
return 0;
}
#include<stdio.h> typedef struct TNode{ int data; struct TNode *left,*right; }*BiTree,TNode; int loc; TNode T[101]; BiTree creat(){ T[loc].left=T[loc].right=NULL; return &T[loc++]; } BiTree Insert(BiTree T,int x,int father){ if(!T){ T=creat(); T->data=x; printf("%d\n",father); return T; } if(x<T->data) T->left=Insert(T->left,x,T->data); else if(x>T->data) T->right=Insert(T->right,x,T->data); return T; } int main(){ int n,tmp; while(scanf("%d",&n)!=EOF){ TNode *T=NULL; loc=0; for(int i=0;i<n;i++){ scanf("%d",&tmp); T=Insert(T,tmp,-1); } } return 0; }
若插入的结点比父节点大,则插入2i+1的位置,
若比父节点小,则插入到2i的位置(数组要开很大,不然过不了)
#include<iostream>
using namespace std;
void binTree(int *a,int num)
{
int i = 1;
while(a[i])
{
if(num>a[i])
i = 2*i+1;
if(num<a[i])
i = 2*i;
}
a[i] = num;
if(i!=1)
{
cout<<a[i/2]<<endl;
}
else
cout<<"-1"<<endl;
}
int main()
{
int a[1000000] = {0};
int n;
int temp;
cin>>n;
for(int i = 0;i<n;i++)
{
cin>>temp;
binTree(a,temp);
}
return 0;
}
//Binary Search Tree #include<iostream> #include<cstdio> using namespace std; struct TreeNode{ int data; TreeNode* leftChild; TreeNode* rightChild; TreeNode(int x): data(x),leftChild(NULL),rightChild(NULL){} }; TreeNode* Insert(TreeNode* root,int x,int father){ if(root==NULL){ root = new TreeNode(x); cout<<father<<endl; } else if(x<root->data){ root->leftChild = Insert(root->leftChild,x,root->data); } else if(x>root->data){ root->rightChild = Insert(root->rightChild,x,root->data); } return root; } int main(){ int N; int temp; TreeNode* root = NULL; cin>>N; for(int i=0; i<N; i++){ cin>>temp; root = Insert(root,temp,-1); } return 0; }