Question

用C++语言编写一个采用二叉链式结构做存储结构的二叉排序树建立和查找算法。关于数据结构的，高手救命！！

Answer 1

//自己好好看看，不理解的即时问
#include <stdio.h>
#include <malloc.h>
typedef int KeyType;
typedef char InfoType[10];
typedef struct node //记录类型
{
KeyType key; //关键字项
InfoType data; //其他数据域
struct node *lchild,*rchild; //左右孩子指针
} BSTNode;
int InsertBST(BSTNode *&p,KeyType k)
{
if (p==NULL) //原树为空, 新插入的记录为根结点
{
p=(BSTNode *)malloc(sizeof(BSTNode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
else if (k==p->key) //树中存在相同关键字的结点,返回0
return 0;
else if (k<p->key)
return InsertBST(p->lchild,k); //插入到*p的左子树中
else
return InsertBST(p->rchild,k); //插入到*p的右子树中
}
BSTNode *CreateBST(KeyType A[],int n) //返回BST树根结点指针
{
BSTNode *bt=NULL; //初始时bt为空树
int i=0;
while (i<n)
{
InsertBST(bt,A[i]); //将关键字A[i]插入二叉排序树T中
i++;
}
return bt; //返回建立的二叉排序树的根指针
}
void DispBST(BSTNode *bt) //使用广义表的方式，输出一棵排序二叉树
{
if (bt!=NULL)
{ printf("%d",bt->key);
if (bt->lchild!=NULL || bt->rchild!=NULL)
{ printf("("); //有孩子结点时才输出(
DispBST(bt->lchild); //递归处理左子树
if (bt->rchild!=NULL) printf(","); //有右孩子结点时才输出,
DispBST(bt->rchild); //递归处理右子树
printf(")"); //有孩子结点时才输出)
}
}
}

BSTNode *SearchBST(BSTNode *bt,KeyType k)
{
if (bt==NULL || bt->key==k) //递归终结条件
return bt;
if (k<bt->key)
return SearchBST(bt->lchild,k); //在左子树中递归查找
else
return SearchBST(bt->rchild,k); //在右子树中递归查找
}

void main()
{
BSTNode *bt,*p,*f;
int n=9;
KeyType a[]={1,12,5,8,3,10,7,13,9};
bt=CreateBST(a,n);
printf("BST:");
DispBST(bt);
printf("\n");
}

Answer 2

#include<iostream>
using namespace std;
class Node{
public:
int key;
Node*left;
Node*right;
Node*father;
Node(int k=-1,Node*f=NULL,Node*l=NULL,Node*r=NULL){
key=k;
left=l;
right=r;
father=f;
}
};
class BinaryTree{
protected:
Node*root;
public:
BinaryTree(int k=-1,Node*f=NULL,Node*l=NULL,Node*r=NULL){
root=new Node(k,f,l,r);
}
~BinaryTree(){
Delete(root);
}
Node* getRoot(){return root;}//返回根节点
Node* setRoot(int k){root->key=k;}//重置根节点的值
void Delete(Node*p){//删除以p为根节点的子树
if(p->left==NULL&&p->right==NULL)
delete []p;
if(p->left)
Delete(p->left);
if(p->right)
Delete(p->right);

}
void push_back(int k){//添加一个值为k的节点，并且保持右孩子的值大于等于父节点的值，左孩子的值小于父节点的值
Node*p1=root;
Node*p2=NULL;
while(p1!=NULL){
p2=p1;
if(p1->key<k){
p1=p1->right;
}
else p1=p1->left;
}
p1=new Node(k);
if(p2->key<k){
p2->right=p1;
p1->father=p2;
}
else {
p2->left=p1;
p1->father=p2;
}
}
bool find(int k){//查找键值为k的节点，若存在，返回true
Node*p=root;
while(p){
if(p->key==k)
return true;
else if(p->key>k)p=p->left;
else p=p->right;
}
return false;
}
void LMR(Node *p){//前序遍历以p为根节点的子树
if(p!=NULL){
cout<<p->key<<"\t";
LMR(p->left);
LMR(p->right);
}
}
void LMR(){//前序遍历整个二叉树
LMR(root);
}
};
int main(){
BinaryTree t(8);//创建一棵二叉搜索树
for(int i=0;i<10;i++){//将随机数添加到t中
t.push_back(rand());
}
t.LMR();//遍历t
int key;
cout<<endl;
while(cin>>key)//输入一个数字并查询该数是否在t中
if(t.find(key))
cout<<"存在"<<endl;
else cout<<"不存在"<<endl;
return 0;
}