二叉排序树

#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<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;
}

#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;
}

#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;
}