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);