bst存储

A. 若二叉树采用二叉链表结构存储，请写出二叉树的结点类型定义，并编写

template

T
search(BSTNode
*
tree,
const
T&
elemt)
{
stack
*>
travStack;
BSTNode

*p
=
root;
//遍历指针
BSTNode

*q
=
root;
//层数看守
int
num
=
1;
If(p
!=
NULL)
travStack.push(p);
while(!travStack.empty())
{
p
=
travStack.pop();
if(p->data
!=
elemt)
if(p
==
q)
{
if(q->right
!=
NULL)
{
q
=
q->right;
}
q
=
q->left;
num+=1;
}
else
{
cout<<"The
number
of
piles
is
"<
left
!=
NULL)
travStack.push(p->left);
if(p->right
!=
NULL)
travStack.push(p->right);
}
}
这个是C++实现的，效率不高。主要运用的是前序遍历的方式,存取方式用的是队列；
思想：设置层数看守,看守始终在该层的最右端；按层次遍历，将该层元素从左向右加入到队列中；找到要求值就停止；

B. 求数据结构试验 线性表的顺序存储结构

#include<iostream.h>
#include<stdlib.h>
#include <malloc.h>
#define OVERFLOW 0
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100//线性表存储空间的初始增量
#define LISTINCREMENT 10 // ?
typedef struct{
int * elem;// 存储空间基址
int length;//当前长度
int listsize;//当前分配的存储容量
}SqList;
SqList L;
int InitList_Sq(SqList & L){
//构造一个新的线性表。
L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
if(!L.elem)exit(OVERFLOW);//存储容量失败
L.length=0; //空表长度为0
L.listsize=LIST_INIT_SIZE;//存储初始容量
return OK;
}//InitList_Sq
int LIstInsert_Sq(SqList & L,int i,int e){
//在顺序线性表L中第i位置之前插入新的元素e
if(i<1||i>L.length+1) return ERROR;
if(L.length>=L.listsize){
int * newbase=(int *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
if(!newbase)exit(OVERFLOW);
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
int * q=&(L.elem[i-1]);
for(int * p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;
*q=e;
++L.length;
return OK;
}
int ListDelete_Sq(SqList&L,int i,int &e)
{
if((i<1)||(i>L.length))return ERROR;
int *p=&(L.elem[i-1]);
e=*p;
int *q=L.elem+L.length-1;
for(++p;p<=q;++p)*(p-1)=*p;
--L.length;
return OK;
}
void main()
{
SqList L;
int i,n;
int e;
cout<<"输入顺序表的个数："<<endl;
cin>>n;
int *p=(int *)malloc(n*sizeof(int));
InitList_Sq(L);
cout<<"输入线性表"<<n<<"个元素的值"<<endl;
for(i=0;i<n;i++)
{
cin>>p[i];
L.elem[i]=p[i];
}
cout<<endl;
L.length=i;
cout<<endl;
cout<<"输入要插入元素的值"<<endl;
cin>>e;
cout<<endl;
cout<<"输入要插入的位置"<<endl;
cin>>i;
LIstInsert_Sq( L, i, e);
for(i=0;i<n+1;i++)
cout<<L.elem[i];
cout<<endl;
cout<<"输入要删除的位置"<<endl;
cin>>i;
ListDelete_Sq(L,i,e)
;for(i=0;i<n;i++)
cout<<L.elem[i];
free(p);