数据结构课程设计 二叉排序树与平衡二叉排序树

#include<stdio.h> #include<malloc.h> #define LH -1 #define EH 0 #define RH 1 typedef int DataType; typedef int KeyType; typedef struct Node{ DataType da; struct Node *next; }node; typedef struct bst{ DataType data; struct bst *lchild,*rchild; }BSTnode,*pBST; typedef struct NODE { KeyType key; int bf; //平衡因子 struct NODE *lchild,*rchild; }AVLnode,*pAVLtree; node *head=NULL; void Save_data() { char ch; node *p,*q; head=(node *)malloc(sizeof(node)); q=head; DataType data; printf("请输入一数列(以回车结束)\n"); do { scanf("%d",&data); ch=getchar(); p=(node*)malloc(sizeof(node)); p->da=data; q->next=p; q=p; q->next=NULL; }while(ch!='\n'); } void Del_data(DataType x) { node *p,*pre; pre=head; p=head->next; while(p->da!=x) { pre=p; p=p->next; } pre->next=p->next; free(p); } /*****************判断元素x是否在排序树***********************/ int Is_In_BST(BSTnode *root,pBST *current_node,pBST *parent_node,DataType x) { //判断x元素是否已经存在，若存在，返回1，且current_node指向该节点，parent_node指向其 //父节点；否则，返回0，且parent_node指向最后查找的节点 int flag=0; *current_node=root; *parent_node=root; while(*current_node) { if(x>(*current_node)->data) { *parent_node=*current_node; *current_node=(*current_node)->rchild; } else if(x<(*current_node)->data) { *parent_node=*current_node; *current_node=(*current_node)->lchild; } else { flag=1; break; } } return flag; } /****************插入元素x*****************/ int Insert_BSTnode(pBST *root,DataType x) { pBST current_node,parent_node,p; int flag=0; current_node=*root; if(!Is_In_BST(*root,&current_node,&parent_node,x)) { p=(pBST)malloc(sizeof(pBST)); p->data=x; p->lchild=NULL; p->rchild=NULL; flag=1; if(parent_node==current_node) //空树,此时parent_node==current_node==NULL *root=p; else { if(x>parent_node->data) parent_node->rchild=p; else parent_node->lchild=p; } } return flag; } /******************节点的深度*************/ int BSTNode_depth(BSTnode *root) { int a,b; if (!root) return 0; a=BSTNode_depth(root->lchild); b=BSTNode_depth(root->rchild); return a>b?a+1:b+1; } /******************统计节点的个数***********/ int CountBSTNodes(pBST root) { int n=1; if(!root) return 0; if(root->lchild) n+=CountBSTNodes(root->lchild); if(root->rchild) n+=CountBSTNodes(root->rchild); return n; } /*******************一个节点的查找长度***************/ int OneBSTNode_Sort_length(pBST root,DataType e) { int n=0; if(root->data==e) return 1; else if(root->lchild && e<root->data) n+=OneBSTNode_Sort_length(root->lchild,e)+1; else if(root->rchild && e>root->data) n+=OneBSTNode_Sort_length(root->rchild,e)+1; return n; } /********************查找总长度**********************/ int AllBSTNodes_Sort_length(pBST root) { int sort_len=0; node *p; p=head->next; while(p) { sort_len+=OneBSTNode_Sort_length(root,p->da); p=p->next; } return sort_len; } /****************中序遍历*****************/ void InOrderBST(pBST root) { pBST p; p=root; if(p==NULL) return; else { InOrderBST(root->lchild); printf("%d ",root->data); InOrderBST(root->rchild); } } /****************是否为AVL树***********************/ int Is_AVLtree(pBST root) { int a,b; static int flag1,flag2; flag1=flag2=1; if(!root) return 1; a=BSTNode_depth(root->lchild); b=BSTNode_depth(root->rchild); if(a-b>=2||a-b<=-2) return 0; else { flag1=Is_AVLtree(root->lchild); flag2=Is_AVLtree(root->rchild); } if(flag1 && flag2) return 1; } /* void PrintData() { node *p; p=head->next; while(p) { printf("%d ",p->da); p=p->next; } } */ /******************创建二叉排序树*****************/ void CreateBST(pBST *root) { node *p; p=head->next; while(p) { Insert_BSTnode(root,p->da); p=p->next; } } /*********************查找删除******************/ void Search_Delete(pBST *root,DataType x) { pBST current_node,parent_node,*p,temp1,temp,del_node; //parent_node=*root; if(!Is_In_BST(*root,&current_node,&parent_node,x)) //没有找到 printf("无节点%d!\n",x); else //找到 { printf("查找长度为:%d",OneBSTNode_Sort_length(*root,x)); del_node=current_node; if(parent_node==del_node) //待删除节点为根节点 p=root; else //待删除节点为非根节点 { p=&(parent_node->lchild); if(x>parent_node->data) p=&(parent_node->rchild);//p节点指向待删除节点父节点中指向待删除节点的那个指针域 } if(!del_node->rchild) *p=del_node->lchild; //待删除节点del_node无右子树，以左孩子代替待删除节点 else { if(!del_node->lchild) *p=del_node->rchild; //待删除节点del_node无左子树，以右孩子代替待删除节点 else //左右子树都有 { temp=del_node->rchild; temp1=temp; while(temp->lchild) { temp1=temp; temp=temp->lchild; } *p=temp; //用del_node节点右子树最左边的节点temp代替待删除节点 temp->lchild=del_node->lchild; //将代替节点temp与del_node节点的左子树连起来 if(temp!=temp1) { temp1->lchild=temp->rchild; //将temp节点的右子树作为其原父节点temp1的左孩子 temp->rchild=del_node->rchild; //将代替节点temp与del_node节点的右子树连起来 } } } // free(del_node); printf(" 此时的二叉排序树为:"); InOrderBST(*root); printf("(中序)"); printf("\n"); Del_data(x); } } int AVLnode_depth(AVLnode *node) { int a,b; if (!node) return 0; a=AVLnode_depth(node->lchild); b=AVLnode_depth(node->rchild); return a>b?a+1:b+1; } void AVLnode_bf(AVLnode *node){ node->bf=AVLnode_depth(node->lchild)-AVLnode_depth(node->rchild); } void Left_Rotate(pAVLtree *root) //对以*root指向的节点为根的子树，作左单旋转处理，处理之后，*root指向的节点为子树的新根 { AVLnode *rp=(*root)->rchild; (*root)->rchild=rp->lchild; rp->lchild=*root; *root=rp; (*root)->bf=(*root)->lchild->bf=0; } void Right_Rotate(pAVLtree *root) //对以*root指向的节点为根的子树，作右单旋转处理，处理之后，*root指向的节点为子树的新根 { AVLnode *lp=(*root)->lchild; //lp指向*root左子树跟节点 (*root)->lchild=lp->rchild; //lp的右子树挂接*root的左子树 lp->rchild=*root; *root=lp; //*root指向新的根节点 (*root)->bf=(*root)->rchild->bf=0; } int Insert_AVLnode(pAVLtree *root,AVLnode *avlNode) //若在平衡的二叉排序树root中不存在x元素，则将其插入，并返回1，否则返回0；若因插入而使二叉排序树 //失去平衡，则作平衡旋转处理，整形变量taller反映长高与否，1长高，0不长高。 { int a,b; if(*root==NULL) { (*root)=avlNode; (*root)->bf=EH; return 1; } if(avlNode->key==(*root)->key) return 1; if(avlNode->key<(*root)->key) { Insert_AVLnode(&((*root)->lchild),avlNode); a=AVLnode_depth((*root)->rchild); b=AVLnode_depth((*root)->lchild); (*root)->bf=a-b; if((*root)->bf>-2 && (*root)->bf<2) return 1; /* (*root)->bf==-2 */ if((*root)->lchild->bf==-1) Right_Rotate(root); if((*root)->lchild->bf==1) { Left_Rotate(&(*root)->lchild); Right_Rotate(root); AVLnode_bf((*root)->rchild); AVLnode_bf((*root)->lchild); } } else { Insert_AVLnode(&((*root)->rchild),avlNode); a=AVLnode_depth((*root)->rchild); b=AVLnode_depth((*root)->lchild); (*root)->bf=a-b; if((*root)->bf>-2 && (*root)->bf<2) return 1; /* (*root)->bf==2 */ if((*root)->rchild->bf==1) Left_Rotate(root); if((*root)->rchild->bf==-1) { Right_Rotate(&(*root)->rchild); Left_Rotate(root); AVLnode_bf((*root)->lchild); AVLnode_bf((*root)->rchild); } } } void CreateAVLtree(pAVLtree *root) { node *p; AVLnode *avlNode; p=head->next; while(p) { avlNode=(AVLnode *)malloc(sizeof(AVLnode));