浙大数据结构Week4
课程地址：https://www.icourse163.org/course/ZJU-93001
笔记中图片均来自此mooc中讲义。
这周的的内容依旧是树，感觉有点难，现在回顾下。
Part1:回顾
1.二叉搜索树(BST)
首先来看一下二叉搜索树的定义。
看完了定义，再来看下二叉搜索树支持的操作,这部分操作和上一周课程中树的操作类似，但是由于二叉搜索树的性质，又略有不同。
先来看下Find操作，Find操作是在二叉搜索树寻找给定的元素，返回它所在节点的位置，如果元素不存在，则返回空。
FinMin,FinMax比较容易，因为根据二叉搜索树的特点，最大元素一定在最右分支的端节点上，最小元素一定在最左分支的端节点上。
再来看一下Insert操作,插入操作的关键点是找到插入的位置，最方便的自然是插在叶节点之后，所以这里可以采取类似Find的操作。
- 从根节点开始，如果树为空，则插入点为根节点。
- 若树非空，则拿插入值和根节点比较，如果插入值小于节点值，在左子树继续进行插入操作。
- 如果插入值大于节点值，在右子树继续进行插入操作。
- 重复此操作直至节点为叶节点。
来看一张图可以方便理解。
最后来看一下删除操作，删除操作相对麻烦麻烦一些，要分为三种情况，即删除点有0个，1个以及2个子节点的情形。
从以上操作可以看出，二叉搜索树的操作时长和二叉搜索树的高度密切相关，所以建树的时候应该尽量减少树的高度
2.平衡二叉树(AVL树)
从二叉搜索树的例子中我们可以看到，树的操作和树的高度有关，那么应该怎样建树才能使树的高度比较低呢？这就引出了平衡二叉树的概念。
从二叉树的定义我们知道，树的高度最小为$O(log_2(n))$,n为节点数量，那么平衡二叉树的高度可以达到$O(log_2(n))$吗？答案是肯定的。
平衡二叉树的各种操作中，调整是最难的，因为它会影响父节点和子节点，下面分四种情况介绍。
刚开始看这个时候头挺晕的，等到写代码的时候更是完全不会了，感觉这部分内容要多体会体会。
Part2:作业
- 作业1
04-树4 是否同一棵二叉搜索树（25 分）
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。
输入格式:
输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。最后L行，每行给出N个插入的元素，属于L个需要检查的序列。
简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。
输出格式:
对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。
输入样例:
4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0
输出样例:
Yes
No
No
这题我采取不建树的方法，思路是两个二叉搜索树相同当且仅当任意对应节点相同以及左子树和右子树中元素相同。
将两组输入序列存入列表x,y，首先比较x,y长度，如果长度不相等，则输出No，否则比较列表首元素，如果首元素不相同，则输出No，否则将列表中小于首元素的元素存入x1,y1,大于首元素的元素存入x2,y2，再用同样的方式比较x1,y1;x2,y2即可。
# -*- coding: utf-8 -*-
"""
Created on Mon Apr 02 12:28:35 2018
@author: 715073608
"""
def f(x,y):
if len(x)!=len(y):
return False
else:
if len(x)==0:
return True
else:
if x[0]!=y[0]:
return False
else:
a=x[0]
x1=[]
y1=[]
x2=[]
y2=[]
for i in range(1,len(x)):
if x[i]<a:
x1.append(x[i])
elif x[i]>a:
x2.append(x[i])
for i in range(1,len(y)):
if y[i]<a:
y1.append(y[i])
elif y[i]>a:
y2.append(y[i])
return f(x1,y1) and f(x2,y2)
ans=[]
while (True):
a=map(int,raw_input().split(' '))
if a[0]==0:
break
else:
b=[]
tree=map(int,raw_input().split(' '))
for i in range(a[1]):
temp=map(int,raw_input().split(' '))
b.append(f(tree,temp))
ans.append(b)
for i in ans:
for j in i:
if j:
print 'Yes'
else:
print 'No'- 作业2
04-树5 Root of AVL Tree（25 分）
An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.
Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the root of the resulting AVL tree in one line.
Sample Input 1:
5
88 70 61 96 120
Sample Output 1:
70
Sample Input 2:
7
88 70 61 96 120 90 65
Sample Output 2:
88
图片不帖了，这题的意思其实就是实现AVL树的插入操作，要将之前描述的LL,RR,LR,RL操作都实现一遍。这题当时纠结了很久，主要疑惑点是如何在python中表示，后来参考了下别人的代码，发现定义一个Node类，包含元素，高度，左指针，右指针四个属性即可实现。
# -*- coding: utf-8 -*-
"""
Created on Mon Apr 02 23:26:09 2018
@author: Administrator
"""
class Node(object):
def __init__(self,key):
self.key=key
self.left=None
self.right=None
self.height=0
class AVL(object):
def __init__(self):
self.root=None
def height(self,node):
if node is None:
return -1
else:
return node.height
#LL
def SingleLeftRotation(self,node):
B=node.left
node.left=B.right
B.right=node
node.height=max(self.height(node.left),self.height(node.right))+1
B.height=max(self.height(B.left),node.height)+1
return B
#RR
def SingleRightRotation(self,node):
B=node.right
node.right=B.left
B.left=node
node.height=max(self.height(node.left),self.height(node.right))+1
B.height=max(self.height(B.right),node.height)+1
return B
#LR
def DoubleLeftRightRotation(self,node):
node.left=self.SingleRightRotation(node.left)
return self.SingleLeftRotation(node)
#RL
def DoubleRightLeftRotation(self,node):
node.right=self.SingleLeftRotation(node.right)
return self.SingleRightRotation(node)
def Insert(self,key,node):
if node==None:
node=Node(key)
elif key<node.key:
node.left=self.Insert(key,node.left)
if (self.height(node.left)-self.height(node.right))==2:
#LL
if key<node.left.key:
node=self.SingleLeftRotation(node)
#LR
else:
node=self.DoubleLeftRightRotation(node)
elif key>node.key:
node.right=self.Insert(key,node.right)
if (self.height(node.right)-self.height(node.left))==2:
#RR
if key>node.right.key:
node=self.SingleRightRotation(node)
#Rl
else:
node=self.DoubleRightLeftRotation(node)
node.height=max(self.height(node.right),self.height(node.left))+1
return node
a=int(raw_input())
b=map(int,raw_input().strip().split(' '))
node=Node(b[0])
tree=AVL()
for i in range(1,a):
node=tree.Insert(b[i],node)
print node.key
- 作业3
04-树6 Complete Binary Search Tree（30 分）
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.
A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.
Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.
Output Specification:
For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
Sample Input:
10
1 2 3 4 5 6 7 8 9 0
Sample Output:
6 3 8 1 5 7 9 0 2 4
这题的意思是给定输入序列，将其按照完全二叉搜索树的先序遍历的顺序输出。这里我采用了一个投机取巧的方法，现将序列按从小到大排序，因为是完全二叉搜索树，所以根节点可以确定，左子树中的元素可以确定，为小于根节点的元素，右子树的元素也可以确定，为大于根节点的元素，如此递归判断即可。那么现在的问题转化为如何找到根节点。
首先来看下树的高度，对于n个节点的完全二叉搜索树，假设高度为k，则有这样一个式子
$2^{k-1} \le n < 2^k-1$
这是因为高度为k的完美二叉树点的个数为$\sum_{i=0}^{k}2^i=2^k-1$，所以$n< 2^k-1$
其次，因为高度为k，因此至少有高度为k-1的完美二叉树的节点个数加1，所以$n\ge2^{k-1}$
$log_2{(n+1)}< k \le log_2n+1$
所以$k-1=[log_2{(n+1)}],[]$表示向下取整函数,这里为什么要求k-1呢，因为对于k层的完全二叉树，截至k-1层的数量是固定的，为$2^{k-1}-1$。再来看截至k-1层，小于根节点的节点数量，显然为一个k-2层的完美二叉树的数量之和，为$2^{k-2}-1$。最后来看下最后一层小于根节点的数量，下面通过两张图片来说明。
对于此图，最后一层小于根节点的数量为$n-2^{k-1}+1(n=8,k=4)$
对于此图，最后一层小于根节点的数量为$2^{k-2}(n=12,k=4)$,k层最大节点数量的一半。
综上，根节点的位置为$2^{k-2}-1+min(n-2^{k-1}+1,2^{k-2})$
下面帖下代码，注意代码中的a为节点个数，n为树的高度减1
# -*- coding: utf-8 -*-
"""
Created on Tue Apr 03 12:27:46 2018
@author: 715073608
"""
from math import log
a=raw_input('')
b=map(int,raw_input('').strip().split(' '))
b.sort()
#b=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
c=[]
#找到根节点
def findroot(b):
if len(b)==1:
return 0
else:
a=len(b)
n=int(log(a+1,2))
s1=2**(n-1)-1
s2=min(2**(n-1),a-2**n+1)
k=s1+s2
return k
#恢复成bst树
def bst(b,c):
tree=[]
a=len(b)
k=findroot(b)
temp=[b[:k],b[k+1:]]
tree.append(temp)
c.append(str(b[k]))
i=2
while len(c)<a:
s=tree[i/2-1]
if i%2==0:
temptree=s[0]
if len(temptree)>0:
k=findroot(temptree)
#print k,len(temptree)
if k<len(temptree)-1:
temp=[temptree[:k],temptree[k+1:]]
else:
temp=[temptree[:k],[]]
tree.append(temp)
c.append(str(temptree[k]))
else:
temptree=s[1]
if len(temptree)>0:
k=findroot(temptree)
#print k,len(temptree)
if k<len(temptree)-1:
temp=[temptree[:k],temptree[k+1:]]
else:
temp=[temptree[:k],[]]
tree.append(temp)
c.append(str(temptree[k]))
i+=1
return c,tree
c,tree=bst(b,c)
print ' '.join(c)- 作业4
04-树7 二叉搜索树的操作集（30 分）
本题要求实现给定二叉搜索树的5种常用操作。
函数接口定义：
BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );
其中BinTree结构定义如下：
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};
函数Insert将X插入二叉搜索树BST并返回结果树的根结点指针；
函数Delete将X从二叉搜索树BST中删除，并返回结果树的根结点指针；如果X不在树中，则打印一行Not Found并返回原树的根结点指针；
函数Find在二叉搜索树BST中找到X，返回该结点的指针；如果找不到则返回空指针；
函数FindMin返回二叉搜索树BST中最小元结点的指针；
函数FindMax返回二叉搜索树BST中最大元结点的指针。
这里就是实现二叉搜索树的全部操作。
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};
void PreorderTraversal( BinTree BT ); /* 先序遍历，由裁判实现，细节不表 */
void InorderTraversal( BinTree BT ); /* 中序遍历，由裁判实现，细节不表 */
BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );
int main()
{
BinTree BST, MinP, MaxP, Tmp;
ElementType X;
int N, i;
BST = NULL;
scanf("%d", &N);
for ( i=0; i<N; i++ ) {
scanf("%d", &X);
BST = Insert(BST, X);
}
printf("Preorder:"); PreorderTraversal(BST); printf("\n");
MinP = FindMin(BST);
MaxP = FindMax(BST);
scanf("%d", &N);
for( i=0; i<N; i++ ) {
scanf("%d", &X);
Tmp = Find(BST, X);
if (Tmp == NULL) printf("%d is not found\n", X);
else {
printf("%d is found\n", Tmp->Data);
if (Tmp==MinP) printf("%d is the smallest key\n", Tmp->Data);
if (Tmp==MaxP) printf("%d is the largest key\n", Tmp->Data);
}
}
scanf("%d", &N);
for( i=0; i<N; i++ ) {
scanf("%d", &X);
BST = Delete(BST, X);
}
printf("Inorder:"); InorderTraversal(BST); printf("\n");
return 0;
}
/* 你的代码将被嵌在这里 */
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->Left=Insert(BST->Left,X);
else if(X>BST->Data)
BST->Right=Insert(BST->Right,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){
//printf("Not Found");
return BST;
}else{
if (X<BST->Data){
return Find(BST->Left,X);
}else if(X>BST->Data){
return Find(BST->Right,X);
}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){
return NULL;
}else if(!BST->Right){
return BST;
}else{
return FindMax(BST->Right);
}
}
void PreorderTraversal( BinTree BST ){
if(BST){
printf("%d ",BST->Data);
PreorderTraversal(BST->Left );
PreorderTraversal(BST->Right );
}
}
void InorderTraversal( BinTree BST ){
if(BST){
InorderTraversal(BST->Left );
printf("%d ",BST->Data);
InorderTraversal(BST->Right );
}
}