工大数据结构第三章作业

node* rchild; bool ltag; bool rtag; elementtype element; };

typedef node* head;//指向树根root

typedef node* tree;//指向线索树的根节点

void makeNull(head& h)//将线索二叉树置空 { h->lchild=h; h->ltag=false; h->rchild=h; h->rtag=true; }

head pointTotree(head& h,tree& t)//令head指向tree,注意head指向的并不是根节点，tree指向根节点 { h->lchild=t; h->rchild=h; h->ltag=true; h->rtag=true; return h; }

//中根遍历的下一个节点 node* inNext(node* p) { node* q=p->rchild; if(p->rtag==true)//如果有右子树，找出右子树的最左节点 while(q->ltag==true) q=q->lchild; return q; }

//中根遍历的上一个节点 node* inPre(node* p) { node *q= p->lchild; if(p->ltag==true)//如果P的左子树存在，则其前驱结点为左子树的最右结点 while(q->rtag==true) q=q->rchild; return q;//左子树的最右结点 }

//中序遍历

void thInOrder(head h) { node* temp; temp=h; do{ temp=inNext(temp); if(temp!=h) cout<element<<\ }while(temp!=h); }

//插入右孩子

void rInsert(node* s,node* r) { node* w; r->rchild=s->rchild; r->rtag=s->rtag; r->lchild=s; r->ltag=false;//新插入的节点木有左子树，所以lchild指向的是父节点 s->rchild=r; s->rtag=true;//原节点的右孩子为新插入的节点 if(r->rtag==true){ //这里是神马意思呢∑q|?Д?|p，就是如果被插节点s有右子树 ， //找出被插节点s的的next位置，即右子树中的最左节点，令其lchild指向新添加的节点r //因为插入前该最左节点的lchild指向的是原来节点s w=inNext(r); w->lchild=r; } }

//插入左孩子

void lInsert(node* s,node* l) { node* w; l->lchild=s->lchild; l->ltag=s->ltag; l->rchild=s; l->rtag=false; s->lchild=l; s->ltag=true; if(l->ltag==true){//与插入右孩子方法相似，只需把左右方向对调即可 w=inPre(l); w->rchild=l;

} }

int main() { head h=new node; node* root=new node; node* lc=new node; node* rc=new node; node* c=new node; root->element=1; lc->element=2; rc->element=3; c->element=4; h->rchild=root; h->lchild=h; h->ltag=true; h->rtag=true; root->lchild=h; root->rchild=h; root->ltag=false; root->rtag=false; //构造线索树213 lInsert(root,lc); rInsert(root,rc); thInOrder(h); cout<

return 0; }

十、假设现在有如下的元素：7、16、49、82、5、31、6、2、44。画出将每一个元素插入堆中以后的最大堆。 要求：

利用基本操作Insert的基本原理，先用第一个元素7构成一个二叉树，然后将第二个元素16插入该二叉树中，再将第三个元素49插入堆中，……，直到最后一个元素插入为止。上述过程要求画图完成。

十一、编写一个函数，在最大堆中查找任意元素，并分析其时间复杂度。 要求：

1、 定义最大堆的型HEAP及其基本操作。

2、 定义函数int Find(HEAP H, Elementtype e)，查找e是否为堆的元素，如果是，返回

该元素在堆中的位置，如果不是，返回0。（提示：利用最大堆的元素特点进行查找，可降低复杂度）

在主函数中首先构建一个二叉树，然后验证所构造的函数。 typedefstryct{ int key;

datathpe data; }elementtype; Typedefstruct{

Elementtype elements[Maxsize]; int n; }HEAP;

Void MaxHeap(HEAP heap)// 创建一个空堆