数据结构（陈越，何钦铭）第四讲树（中）

4.1 二叉搜索树

4.1.1 二叉搜索树及查找

在这里插入图片描述

Position Find(ElementTyoe X,BinTree BST){if(!BST){return NULL;}if(X>BST->Data){return Find(X,BST->Right)}else if(X<BST->Data){return Find(X,BST->Left)}else{return BST;}
} Position IterFind(ElementType X,BinTree BST){while(BST){if(X>BST->Data){BST=BST->Right;}else if(X<BST->Data){BST=BST->Left;}else{return BST;}}
}Position FindMin(BinTree BST){if(!BST){return NULL;}else if(!BST->Left){return BST;}else{return FindMin(BST->Left);}
}Position FindMax(BinTree BST){if(BST){while(BST->Right){BST=BST->Right;}}return BST;
}

4.1.2 二叉搜索树的插入

BinTree Insert(ElementType X,BinTree BST){if(!BST){BST=(BinTree)malloc(sizeof(struct TreeNode));BST->Data=X;BST->Left=BST->Right=NULL;}else{if(X<BST->Data){BST->Left=Insert(X,BST->Left);}else if(X>BST->Data){BST->Right=Insert(X,BST->Right);}}return BST;
}

4.1.3 二叉搜索树的删除

BinTree Delete(ElementType X,BinTree BST){Position Tmp;if(!BST){printf("要删除的元素未找到");}else if(X<BST->Data){BST->Left=Delete(X,BST->Left);}else if(X>BST->Data){BST->Right=Delete(X,BST->Right);}else{if(BST->Left&&BST->Right){Tmp=FindMin(BST->Right);BST->Data=Tmp->Data;BST->Right=Delete(BST->Data,BST->Right);}else{Tmp=BST;if(!BST->Left){BST=BST->Right;}else if(!BST->Right){BST=BST->Left;}free(Tmp);}}return BST;
}

4.2 平衡二叉树

4.2.1 什么是平衡二叉树

在这里插入图片描述

4.2.2 平衡二叉树的调整

在这里插入图片描述

Position Find(ElementTyoe X,BinTree BST){if(!BST){return NULL;}if(X>BST->Data){return Find(X,BST->Right)}else if(X<BST->Data){return Find(X,BST->Left)}else{return BST;}
} Position IterFind(ElementType X,BinTree BST){while(BST){if(X>BST->Data){BST=BST->Right;}else if(X<BST->Data){BST=BST->Left;}else{return BST;}}
}Position FindMin(BinTree BST){if(!BST){return NULL;}else if(!BST->Left){return BST;}else{return FindMin(BST->Left);}
}Position FindMax(BinTree BST){if(BST){while(BST->Right){BST=BST->Right;}}return BST;
}BinTree Insert(ElementType X,BinTree BST){if(!BST){BST=(BinTree)malloc(sizeof(struct TreeNode));BST->Data=X;BST->Left=BST->Right=NULL;}else{if(X<BST->Data){BST->Left=Insert(X,BST->Left);}else if(X>BST->Data){BST->Right=Insert(X,BST->Right);}}return BST;
}BinTree Delete(ElementType X,BinTree BST){Position Tmp;if(!BST){printf("要删除的元素未找到");}else if(X<BST->Data){BST->Left=Delete(X,BST->Left);}else if(X>BST->Data){BST->Right=Delete(X,BST->Right);}else{if(BST->Left&&BST->Right){Tmp=FindMin(BST->Right);BST->Data=Tmp->Data;BST->Right=Delete(BST->Data,BST->Right);}else{Tmp=BST;if(!BST->Left){BST=BST->Right;}else if(!BST->Right){BST=BST->Left;}free(Tmp);}}return BST;
}

小白专场

在这里插入图片描述

#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 check(Tree T,int V){if(T->flag){if(V<T->v){return check(T->Left,V);}else if(V>T->v){return check(T->Right,V);}else{return 0;}}else{if(V==T->v){T->flag=1;return 1;}else{return 0;}}
}int Judge(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)&&(!check(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;scanf("%d",&N);while(N){scanf("%d",&L);T=MakeTree(N);for(i=0;i<L;i++){if(Judge(T,N)){printf("Yes\n");	}else{printf("No\n");}ResetT(T);}FreeTree(T);scanf("%d",&N);}return 0;
}