特殊矩阵的压缩存储算法的实现

typedef struct tnode {

KeyType key; ElemType data;

struct tnode *lchild,*rchild; }BSTNode;

void BSTdisp(BSTNode *b);

BSTNode *BSTSearch(BSTNode *bt,KeyType k) {

BSTNode *p=bt;

while (p!=NULL && p->key!=k) {

if (kkey)

p=p->lchild; /*沿左子树查找*/ else

p=p->rchild; /*沿右子树查找*/ }

return(p); }

int BSTInsert(BSTNode *&bt,KeyType k) {

BSTNode *f,*p=bt; while (p!=NULL) {

if (p->key==k) return(0);

f=p; /*f指向*p结点的双亲结点*/ if (p->key>k)

p=p->lchild; /*在左子树中查找*/ else

p=p->rchild; /*在右子树中查找*/ }

p=new BSTNode; /*建立新结点*/ p->key=k;

p->lchild=p->rchild=NULL;

if (bt==NULL) /*原树为空时,*p作为根结点插入*/ bt=p;

else if (kkey)

f->lchild=p; /*插入*p作为*f的左孩子*/ else

f->rchild=p; /*插入*p作为*f的右孩子*/ return(1); }

/*BSTNode *CreatBST(KeyType A[],int n)

//由数组中的关键字建立一棵二叉排序树 {

BSTNode *bt=NULL; //初始时bt为空树 int i=0; while(i

if(BSTInsert(bt,A[i])) //将A[i]插入二叉排序树T中 {

count<<\第\步，插入:\ DispBST(bt); printf(\ i++; }

return bt; //返回建立的二叉排序树的根指针 }*/

void CreateBST(BSTNode *&bt,KeyType str[],int n) {

bt=NULL; /*初始时bt为空树*/ int i=0; while (i

BSTInsert(bt,str[i]); /*将关键字str[i]插入二叉排序树bt中*/ i++; } }

int BSTDelete(BSTNode *&bt,KeyType k) {

BSTNode *p=bt,*f,*r,*f1;

f=NULL; /*p指向待比较的结点,f指向*p的双亲结点*/

while (p!=NULL && p->key!=k)/*查找值域为x的结点*/ { f=p;

if (p->key>k)

p=p->lchild; /*在左子树中查找*/ else

p=p->rchild; /*在右子树中查找*/ }

if (p==NULL) /*未找到key域为k的结点*/ return(0);

else if (p->lchild==NULL) /**p为被删结点,若它无左子树*/ {

if (f==NULL) /**p是根结点,则用右孩子替换它*/ bt=p->rchild;

else if (f->lchild==p) /**p是双亲结点的左孩子,则用其右子替换它*/

{ f->lchild=p->rchild; delete p; }

else if(f->rchild==p) /**p是双亲结点的右孩子,则用其右孩子替换它*/

{ f->rchild=p->rchild; delete p; } }

else if (p->rchild==NULL) /**p为被删结点,若它无右子树*/ {

if (f==NULL) /**p是根结点,则用左孩子替换它*/ bt=p->lchild; if (f->lchild==p) /**p是双亲结点的左孩子,则用其左孩子替换它*/

{ f->lchild=p->lchild; delete p; }

else if(f->rchild==p) /**p是双亲结点的右孩子,则用其左孩子替换它*/

{ f->rchild=p->lchild; delete p; } }

else /**p为被删结点,若它有左子树和右子树*/ {

f1=p;r=p->lchild; /*查找*p的左子树中的最右下结点*r*/

while (r->rchild!=NULL) /**r一定是无右子树的结点,*f1作为r的双亲*/

{ f1=r; r=r->rchild; }

if (f1->lchild==r) /**r是*f1的左孩子,删除*r*/ f1->lchild=r->rchild;

else if (f1->rchild==r) /**r是*f1的右孩子,删除*r*/ f1->rchild=r->lchild;

r->lchild=p->lchild; /*以下语句是用*r替代*p*/ r->rchild=p->rchild;

if (f==NULL) /**f为根结点*/

bt=r; /*被删结点是根结点*/ else if (f->lchild==p) /**p是*f的左孩子*/ f->lchild=r;

else /**p是*f的右孩子*/ f->rchild=r;

delete p; }

return(1); }

//先序遍历

/*void preorder(BSTNode *t) {

if(t!=0) {

cout<key<<\ preorder(t->lchild); preorder(t->rchild); } }*/

//中序遍历

void inorder(BSTNode *t) {

if(t!=0) {

inorder(t->lchild); cout<key<<\ inorder(t->rchild); } }

void BSTdisp(BSTNode *bt) {

if(bt!=NULL) {

cout<key;

if(bt->lchild !=NULL||bt->rchild !=NULL) {

cout<<\

BSTdisp(bt->lchild ); if(bt->rchild !=NULL) cout<<\

BSTdisp(bt->rchild ); cout<<\ } } }

void main() {

int n;

BSTNode *bt=NULL,*p;