1130310126_李明远_第五章作业与练习

《1130310126_李明远_第五章作业与练习》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第五章作业与练习五•算法设计（作业，必须交）1.设计算法判断一棵二叉树是否为二叉排序树。flag二1代表是，flag二0代表否使用dfs判断#include#includestructnode{intdata;node*left;node*right;}；flag=l;voiddfs(node*po){if(po==NULL)return;if(po->left!=NULL&&po->left->data>=po->data){flag=0;return;}if(po->right!=NULL&&po->right->data<=po

2、->data){flag=0;return;}dfs(po->left);dfs(po->right);return;2.设计算法判断一棵二叉排序树是否是平衡二叉树。如果任意节点的左右子树的深度相差不超过1,那这棵树就是平衡二叉树首先编写一个计算二叉树深度的函数，然后通过递归判断是否为平衡二叉〃计算二叉树的深度structnode{intdata;node*left;nodebright;JBSTreeNode;staticintDepth(BSTreeNode*pbs){讦(pbs=NULL)return0;else{intId=Depth(pbs->left);int

3、rd=Depth(pbs->right);return1+(Id>rd?Id:rd);}}〃利用递归判断左右子树的深度是否相差1來判断是否是平衡二叉树staticboolisBalance(BSTreeNode*pbs){if(pbs==NULL)returntrue;intdis=Depth(pbs->left)-Depth(pbs->right);if(dis>l

4、

5、dis<-l)returnfalse;elsereturnisBalance(pbs->left)&&isBalance(pbs->right);}3・实现平衡二叉树的插入和删除操作。#includena

6、vl_tree.hn#include#include#include#includevoidinsert_keys_to_AVL(AVLTree&tree,intkeys[],intn){inttaller=FALSE;//此初值无影响for(inti=0;i

7、入根结点，或叶子结点时(p->left=tree==null),且长高~tree=(AVLTree)malloc(TNODE_SIZE);tree->key=key;tree->left=tree->right=NULL;tree->bf=EH;taller=TRUE;}else{//当插入新结点之后，对于tree进行平衡处理if(EQ(key,tree->key)){〃存在相同关键字，不需要进行插入taller=FALSE;return0;}elseif(LT(key,tree->key)){//插入到左子树当中//如果由于已经存在相同关键字而没有成功插入到树当中〜if

8、(!insert_key_to_AVL(tree->left,key,taller))return0;if(taller)//如果左子树变高了{switch(tree->bf){//如果左子树已经高1〜，则需将左子树平衡〜caseLH:left_ballance(tree);taller=FALSE;break;caseEH:tree->bf=LH;taller=TRUE;break;caseRH:tree->bf=EH;taller=FALSE;break;}//switch(tree->bf)}}else{//右子树增高//如果由于已经存在相同关键字而没有成功插入到树

9、当中〜if(!insert_key_to_AVL(tree->right,key,taller))return0;if(taller)//如果右子树变高了{switch(tree->bf){caseLH:tree->bf=EH;taller=FALSE;break;caseEH://如果原左右子树相等，则左子树增加1,使得树“长高”tree->bf二RH;taller=TRUE;break;caseRH://如果右子树已经高1〜，现在又高1,则需将右子树平衡〜right_ballance(tree);taller=FALSE;