华科：二叉排序树

2023-12-04 07:58

文章标签 排序二叉华科

本文主要是介绍华科：二叉排序树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

输入描述:

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

输出描述:

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

示例1

输入

5
2 5 1 3 4

输出

下面是我的做法，标准的严蔚敏方法，太麻烦啦！

#include<bits/stdc++.h>
using namespace std;typedef struct bnode
{int data;struct bnode *lchild,*rchild;
}BNode,*bitree;int searchBST(bitree T,int key,bitree f,bitree &p)
{if(!T){p=f;return 0;}else{if(T->data==key){p=T;return 1;}else if(T->data<key)return searchBST(T->rchild,key,T,p);elsereturn searchBST(T->lchild,key,T,p);}
}int insertBST(bitree &T,int key)
{bitree p,s;if(!searchBST(T,key,NULL,p)){s=new BNode[sizeof(BNode)];s->data=key;s->lchild=s->rchild=NULL;if(!p){T=s;printf("-1\n");}else if(p->data>key){p->lchild=s;printf("%d\n",p->data);}else{p->rchild=s;printf("%d\n",p->data);}return 1;}return 0;
}int main()
{int n,i,x;bitree T;while(scanf("%d",&n)!=EOF){T=NULL;for(i=0;i<n;i++){scanf("%d",&x);InsertBST(T,x);}}
}

下面这位同学给出了一个很好的思路，值得我们借鉴，他是完全按照二叉排序树的定义来做的

#include <bits/stdc++.h>
using namespace std;typedef struct bnode
{int data;struct bnode *lchild,*rchild;
}BNode,*bitree;int InsertBST(bitree &T,int key,bitree &f)//T和f表示当前探索的节点和T的父节点，如果空就申请空间，如果不空就探索左孩子或者右孩子
{if(!T)/*如果空就申请空间*/{T=new BNode[sizeof(BNode)];T->data=key;T->lchild=T->rchild=NULL;}else{f=T;/*不论是左孩子还有右孩子它们的爸爸都是T*/if(key<T->data)return InsertBST(T->lchild,key,f);//小于的话就探索左孩子，elsereturn InsertBST(T->rchild,key,f);//大于的话就探索左孩子，}return 1;
}int main()
{int n,i,x;bitree T,f;while(~scanf("%d",&n)){T=f=NULL;for(i=0;i<n;i++){scanf("%d",&x);InsertBST(T,x,f);if(!f)printf("-1\n");elseprintf("%d\n",f->data);}}
}