【MOOC-浙大数据结构】第四周的编程作业——二叉搜索树&二叉排序树

女爷i 2021-11-26 09:24 257阅读 0赞

**第四周的编程作业：**

**1.[是否同一棵二叉搜索树][Link 1]**

#include<stdio.h>
    #include<stdlib.h>
    typedef struct TreeNode *Tree;
    struct TreeNode
    {
    	int v;
    	Tree Left,Right;
    	int flag;
    };
    Tree newNode(int V)
    {
    	Tree T=(Tree)malloc(sizeof(struct TreeNode));
    	T->v=V;
    	T->Left=T->Right=NULL;
    	T->flag=0;
    	return T;
    }
    Tree Insert(Tree T,int V)
    {
    	if(!T) T=newNode(V);
    	else
    	{
    		if(V>T->v)
    		T->Right=Insert(T->Right,V);
    		else
    		T->Left=Insert(T->Left,V);
    	}
    	return T;
    }
    Tree MakeTree(int n)
    {
    	Tree T;
    	int i,V;
    	scanf("%d",&V);
    	T=newNode(V);
    	for(i=1;i<n;i++)
    	{
    		scanf("%d",&V);
    		T=Insert(T,V);
    	}
    	return T;
    }
    int Judge(Tree T,int V)
    {
    	if(T->flag)
    	{
    		if(V<T->v)
    		return Judge(T->Left,V);
    		else if(V>T->v)
    		return Judge(T->Right,V);
    		else 
    		return 0;
    	}
    	else
    	{
    		if(V==T->v)
    		{
    			T->flag=1;
    			return 1;
    		}
    		else return 0;
    	}
    }
    int Check(Tree T,int n)
    {
    	int i,V,flag=0;
    	scanf("%d",&V);
    	if(V!=T->v) flag=1;
    	else T->flag=1;
    	for(i=1;i<n;i++)
    	{
    		scanf("%d",&V);
    		if((!flag)&&(!Judge(T,V)))flag=1;
    	}
    	if(flag)return 0;
    	else return 1;
    }
    void ResetT(Tree T)
    {
    	if(T->Left) ResetT(T->Left);
    	if(T->Right) ResetT(T->Right);
    	T->flag=0;
    }
    void FreeTree(Tree T)
    {
    	if(T->Left) FreeTree(T->Left);
    	if(T->Right) FreeTree(T->Right);
    	free(T);
    }
    int main()
    {
    	int n,l,i;
    	Tree T;
    	while(scanf("%d",&n))
    	{
    		if(n==0)break;
    		scanf("%d",&l);
    		T=MakeTree(n);
    		while(l--)
    		{
    			if(Check(T,n))
    			printf("Yes\n");
    			else 
    			printf("No\n");
    			ResetT(T);
    		}
    		FreeTree(T);
    	}	
    }

2.**[Root of AVL Tree][]**

//按照输入顺序建立平衡二叉树，输出根节点

//四种情况都要转一下

#include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef int ElementType;
    typedef struct AVLNode *Position;
    typedef Position AVLTree;
    typedef struct AVLNode{
    	ElementType Data;
    	AVLTree Left;
    	AVLTree Right;
    	int Height;
    };
    int GetHeight(AVLTree T)
    {
    	int l,r,maxh;
    	if(T)
    	{
    		l=GetHeight(T->Left);
    		r=GetHeight(T->Right);
    		maxh=l>r?l:r;
    		return (maxh+1);
    	}
    	else return 0;
    }
    AVLTree SingleLeftRotation(AVLTree A)
    {
    	AVLTree B=A->Left;
    	A->Left=B->Right;
    	B->Right=A;
    	A->Height=max(GetHeight(A->Left),GetHeight(A->Right))+1;
    	B->Height=max(GetHeight(B->Left),A->Height)+1;
    	return B;
    }
    AVLTree SingleRightRotation(AVLTree A)
    {
    	AVLTree B=A->Right;
    	A->Right=B->Left;
    	B->Left=A;
    	A->Height=max(GetHeight(A->Left),GetHeight(A->Right))+1;
    	B->Height=max(GetHeight(B->Right),A->Height)+1;
    	return B;
    }
    AVLTree DoubleLeftRightRotation(AVLTree A)
    {
    	A->Left=SingleRightRotation(A->Left);
    	return SingleLeftRotation(A);
    }
    AVLTree DoubleRightLeftRotation(AVLTree A)
    {
    	A->Right=SingleLeftRotation(A->Right);
    	return SingleRightRotation(A);
    }
    AVLTree Insert(AVLTree T,ElementType x)
    {
    	if(!T)
    	{
    		T=(AVLTree)malloc(sizeof(struct AVLNode));
    		T->Data=x;
    		T->Height=1;
    		T->Left=T->Right=NULL;
    	}
    	else if(x<T->Data)
    	{
    		T->Left=Insert(T->Left,x);
    		if(GetHeight(T->Left)-GetHeight(T->Right)==2)
    		{
    			if(x<T->Left->Data)
    			T=SingleLeftRotation(T);
    			else 
    			T=DoubleLeftRightRotation(T);
    		}
    	}
    	else if(x>T->Data)
    	{
    		T->Right=Insert(T->Right,x);
    		if(GetHeight(T->Left)-GetHeight(T->Right)==-2)
    		{
    			if(x>T->Right->Data)
    			T=SingleRightRotation(T);
    			else 
    			T=DoubleRightLeftRotation(T);
    		}
    	}
    	T->Height=max(GetHeight(T->Left),GetHeight(T->Right))+1;
    	return T;
    }
    int main()
    {
    	int n,i;
    	ElementType x;
    	AVLTree T;
    	T=NULL;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		scanf("%d",&x);
    		T=Insert(T,x);
    	}
    	printf("%d\n",T->Data);
    }

3.**[Complete Binary Search Tree][]**

#include <stdio.h>
    #include <algorithm>
    #include <stdlib.h>
    using namespace std;
    int A[1005],T[1005];
    int n,p;
    void solve(int root)
    {
    	if(root<=n)
    	{
    		solve(root*2);//左 
    		T[root]=A[p++];
    		solve(root*2+1);//右 
    	}
    }
    int main()
    {
    	int i;
    	p=0;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	scanf("%d",&A[i]);
    	sort(A,A+n);
    	solve(1);
    	for(i=1;i<n;i++)
    	printf("%d ",T[i]);
    	printf("%d\n",T[n]);
    }

4.**[二叉搜索树的操作集][Link 2]**

Position FindMin( BinTree BST )
    {
    	if(BST)
    	{
    		while(BST->Left)
    		{
    			BST=BST->Left;
    		}
    	}
    	return BST;
    }
    Position FindMax( BinTree BST )
    {
    	if(BST)
    	{
    		while(BST->Right)
    		{
    			BST=BST->Right;
    		}
    	}
    	return BST;
    }
    BinTree Insert( BinTree BST, ElementType X )
    {
    	if(!BST) 
    	{
    		BST=(BinTree)malloc(sizeof(struct TNode));
    		BST->Data=X;
    		BST->Left=BST->Right=NULL;
    	}
    	else
    	{
    		if(X>BST->Data)
    		BST->Right=Insert(BST->Right,X);
    		else
    		BST->Left=Insert(BST->Left,X);
    	}
    	return BST;
    }
    BinTree Delete( BinTree BST, ElementType X )
    {
    	Position Tmp;
    	if(!BST)
    	printf("Not Found\n");
    	else
    	{
    		if(X<BST->Data)
    			BST->Left=Delete(BST->Left,X);
    		else if(X>BST->Data)
    			BST->Right=Delete(BST->Right,X);
    		else
    		{
    			if(BST->Left&&BST->Right)
    			{
    				Tmp=FindMin(BST->Right);
    				BST->Data=Tmp->Data;
    				BST->Right=Delete(BST->Right,BST->Data);
    			}
    			else
    			{
    				Tmp=BST;
    				if(!BST->Left)
    					BST=BST->Right;
    				else
    					BST=BST->Left;
    				free(Tmp);
    			}
    		}	
    	}
    	return BST;
    }
    Position Find( BinTree BST, ElementType X )
    {
    	if(!BST)return NULL;
    	if(X>BST->Data)
    		return Find(BST->Right,X);
    	else if(X<BST->Data)
    		return Find(BST->Left,X);
    	else 
    		return BST;
    }

[Link 1]: https://pintia.cn/problem-sets/1134360184290500608/problems/1143853180891389952
[Root of AVL Tree]: https://pintia.cn/problem-sets/1134360184290500608/problems/1143853180891389953
[Complete Binary Search Tree]: https://pintia.cn/problem-sets/1134360184290500608/problems/1143853180891389954
[Link 2]: https://pintia.cn/problem-sets/1134360184290500608/problems/1143853180891389955