学习目标：

二叉查找树
AVL树
树结构练习题
搭建自己的github主页

10.12 二叉查找树

性质：比父节点小的key都出现在左子树，其他的出现在右子树
由于插入顺序不同，生成的bst也不同

前置知识：特殊方法

诸如__xxx__（前后两个下划线，中间是方法名）
自己不需要调用它们，使用内置函数来用
例如__len__，使用时用len(xx)而不是xx.len()，其实是调用xx.len()

前置知识：yield

例子——fib

第一种：返回一个list，用迭代print出来（运行中占用的内存会随着参数n_max的增大而增大）
第二种：通过 iterable 对象来迭代，内存占用小
第三种：yield，保留第一种方法的简洁性同时获得iterable的效果

### 第一种
print('第1种')
def fib(n_max):
    listx = []
    n,a,b = 1,0,1
    while n <= n_max:
        listx.append(b)
        a,b = b, a+b
        n += 1
    return listx

for i in fib(6): print(i)

    
    
print('\n 第2种')
### 第二种
# 思路，通过next不断返回序列的下一个数字，把fab写成一个支持iterable 的class
class Fib(object):
    def __init__(self,n_max):
        self.max = n_max
        self.n,self.a,self.b = 1,0,1
        
    def __iter__(self):   
        return self
    
    def __next__(self):
        if self.n<=self.max:
            self.a,self.b = self.b, self.a+self.b
            self.n +=1
            return self.a
        raise StopIteration()   # 如果超过就推出循环

for n in Fib(6): print(n)
    
    
    
print('\n 第3种')  
### 第三种 使用yield
def fib(n_max):
    n, a, b = 1, 0, 1
    while n<= n_max:
        yield b     # 迭代时可看做return，只是fib变成一个生成器
        a,b, = b, a+b
        n = n+1

for n in fib(6): print(n)

### 实现一个二叉搜索树：
        
### 1.node
class TreeNode:  # 键值、数据项、左右节点、父节点
    def __init__(self,key,val,left = None,right = None,parent =None):
        self.key = key
        self.payload =val
        self.leftchild=left
        self.rightchild = right
        self.parent = parent
        
    def hasleftchild(self):
        return self.leftchild
    
    def hasrightchild(self):
        return self.rightchild
    
    def hasanychild(self):
        return self.rightchild or self.leftchild
    
    def hasbothchild(self):
        return self.rightchild and self.leftchild
    
    def isleftchild(self):
        return self.parent and self.parent.leftchild==self
    
    def isrightchild(self):    # 父节点&是否是右子节点
        return self.parent and self.parent.rightchild==self
    
    def isroot(self):    # 是否是根节点
        return not self.parent 
    
    def isleaf(self):
        return not (self.leftchild or self.rightchild)
    
    def replaceNodeData(self,key,value,lc,rc):
        self.key = key
        self.payload = value
        self.leftchild = lc
        self.rigthchild = rc      # 新的子节点
        if self.hasleftchild():    #如果原本有子节点，链接到修改后的父节点
            self.leftchild.parent = self
        if self.hasrightchild():
            self.rightchild.parent=self
    
    def __iter__(self):  # 迭代器
        if self:
            if self.hasleftchild():
                for elem in self.leftchild:
                    yield elem    # 对每次迭代的返回值
            yield self.key
            if self.hasrightchild():
                for elem in self.rightchild:
                    yield elem
                    
    def findMin(self): 
        current = self
        while current.hasleftchild():   # 顺着左子树一直找
            current = current.leftchild
        return current
    
    def findSuccessor(self):    # 寻找后继(只考虑基本情况)
        succ = None
        if self.hasrightchild():
            succ = self.rightchild.findMin()
        return succ
    
    def spliceOut(self):  # 摘除叶节点
        if self.isleaf():
            if self.isleftchild():
                self.parent.leftchild = None
            else:
                self.parent.rightchild = None
                

### 2.BST
class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.size = 0
    
    def length(self):
        return self.size
    
    def __len__(self):
        return self.size
    
    def __iter__(self):
        return self.root.__iter__()
    
    
    #### 赋值方法
    def put(self, key,val):
        if self.root:   # 如果是空树，直接作为root，如果不是就调用_put
            self._put(key,val,self.root)
        else:
            self.root = TreeNode(key,val)  
            self.size = self.size+1  
    
    def _put(self,key,val,currentNode):   # 辅助方法
        if key < currentNode.key:  # 大就放在右节点，但如果有了右子树，递归到下一级
            if currentNode.hasleftchild():  
                self._put(key,val, currentNode.leftchild)  # 递归
            else:
                currentNode.leftchild = TreeNode(key,val,parent =currentNode)
        else:
            if currentNode.hasrightchild():
                self._put(key,val,currentNode.rightchild)
            else:
                currentNode.rightchild = TreeNode(key,val,parent =currentNode)
    
    def __setitem__(self,key,val):   #索引赋值
        self.put(key,val)
        
        
    #### 搜索方法：
    def get(self, key):
        if self.root:   
            res = self._get(key, self.root)    # 从root开始找
            if res: 
                return res.payload   # 返回数据项
            else:
                return None           # 没找到
        else:
            return None
        
    def _get(self,key,currentNode):
        if not currentNode:              # 停止条件
            return None
        elif currentNode.key==key:   # 如果匹配
            return currentNode
        elif key<currentNode.key:     # 如果小于当前节点，往左子节点递归
            return self._get(key,currentNode.leftchild) 
        else: 
            return self._get(key,currentNode.rightchild)
    
    def __getitem__(self,key):
        return self.get(key)
    
    def __contains__(self,key):
        if self._get(key,self.root):
            return True
        else:
            return False

from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"  

mytree1 = BinarySearchTree()

## 索引赋值
mytree1[3] = "yy"
mytree1[4] = "python"
mytree1[6] = "read"
mytree1[2] = "today"
mytree1[7] = "is"
mytree1[1] = "now"

len(mytree1)
print("根节点 key={}，value={}".format(mytree1.root.key,mytree1.root.payload))
print("第一个左子节点 key={}，value={}".format(mytree1.root.leftchild.key,mytree1.root.leftchild.payload))   # 第一个左子节点
print("第一个右子节点 key={}，value={}".format(mytree1.root.rightchild.key,mytree1.root.rightchild.payload))   # 第一个右子节点
mytree1.root.leftchild.isleaf()
mytree1.root.rightchild.hasbothchild() 

## 索引查找
6 in mytree1
print(mytree1[4])

根节点 key=3，value=yy
第一个左子节点 key=2，value=today
第一个右子节点 key=4，value=python
python

### 迭代枚举所有key
for i in mytree1: print(i, mytree1[i])

1 now
2 today
3 yy
4 python
6 read
7 is

先序、中序、后序

最简单——用递归复杂度o(n)

首先都是从根向下迭代，只是输出时机不同
先序：直接输出
中序：先存着，左边遍历完了再把存着的输出——结果就是从小到大排列的！！
后序：先存着，两边都完了再输出

## 按照前面的插入顺序得到的树的样子：
from IPython.display import Image
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"     
Image(filename = 'Desktop/快乐研一/python/mytree1.jpg', width=400, height=400)

# 三种遍历方法：
def qianxu(root):
    if not root == None:
        print(root.key, root.payload)
        qianxu(root.leftchild)
        qianxu(root.rightchild)        
qianxu(mytree1.root)
print("\n")

def zhongxu(root):    # 从小到大排列的！
    if not root==None:
        zhongxu(root.leftchild)
        print(root.key,root.payload)
        zhongxu(root.rightchild)
zhongxu(mytree1.root)  
print("\n")

def houxu(root):
    if not root==None:
        zhongxu(root.leftchild)
        zhongxu(root.rightchild)
        print(root.key,root.payload)
houxu(mytree1.root)

3 yy
2 today
1 now
4 python
6 read
7 is


1 now
2 today
3 yy
4 python
6 read
7 is


1 now
2 today
4 python
6 read
7 is
3 yy

Image(filename = 'Desktop/快乐研一/python/bianlitree.png', width=400, height=400)

一个更加直观的例子

根节点的左子节点，如果按照前序遍历:

[2,3,5,6,4,7,8,]

如果按照中序遍历

[2,3,4,5,6,7,8]

如果按照后序遍历
[5,6,3,7,8,4,2]

中序遍历——一个栈实现

不断往左子树方向走，每走一次如果不是空，就将当前节点push进去
左子树为空了，从栈中pop，然后转向右边节点

def zhongxu_stack(root):
    mystack = []
    results = []
    
    while root or mystack:   
        if root:    
            mystack.append(root)
            root = root.leftchild
        else:     
            # 说明上一步节点没有左节点，pop回到上一步
            # 输出上一步的key，同时把当前设为上一步的右节点
            # 重复上述步骤
            # mystack 为空，说明左边已经遍历了
            # 两者同时为为空，说明右边也遍历完了，可以结束了
            tmp = mystack.pop()
            root = tmp.rightchild
            results.append(tmp.key)
    return results
    
zhongxu(mytree1.root)
zhongxu_stack(mytree1.root)

1 now
2 today
3 yy
4 python
6 read
7 is





[1, 2, 3, 4, 6, 7]

练习，熟悉

## 1.给所有节点key+1
def plusOne(root):
    if not root==None:  # 结束条件
        root.key+=1
        plusOne(root.leftchild)
        plusOne(root.rightchild)

zhongxu(mytree1.root)
print('\n')
plusOne(mytree1.root)
zhongxu(mytree1.root)

1 now
2 today
3 yy
4 python
6 read
7 is


2 now
3 today
4 yy
5 python
7 read
8 is

### 2.判断两棵树是否一致
### 递归到左子树和右子树
### 如果两棵树没有子树，直接对比
### 如果不是同一边/子树不一致，直接F
def isSameTree(root1,root2):
    if (root1==None and root2==None): 
        return True
    if (root1==None or root2 == None):   # 一边有一边没有
        return False
    else:   # 非空先看当前数值
        if (not root1.key==root2.key):  # 数值不同
            return False
        else:    # 如果暂时相同就递归
            return (isSameTree(root1.leftchild,root2.leftchild) and isSameTree(root1.rightchild, root2.rightchild))

    
mytree1 = BinarySearchTree()
mytree1[3] = ""
mytree1[4] = ""
mytree1[6] = ""
mytree1[2] = ""
mytree1[7] = ""
mytree1[1] = ""

mytree2 = BinarySearchTree()
mytree2[3] = ""
mytree2[4] = ""
mytree2[6] = ""
mytree2[2] = ""
mytree2[7] = ""

isSameTree(mytree1.root, mytree2.root)
mytree2[1] = ""
isSameTree(mytree1.root, mytree2.root)

False






True

10.13

学习目标

remove 一个节点
练习题【简单】:1.深度、2.路径总和、3.打印

remove

分为几种情况

叶节点，把父节点的对应的child改成None
如果有一个子节点，把这个唯一的子节点上移，也就是把父节点的child改为子节点【逐个讨论左右、根节点问题】
如果有两个子节点——寻找另一个合适的节点来替换。“合适的节点”下一个key值的节点，即右子树中最小的——“后继”

这里又要考虑一个问题：后继节点怎么找？

节点有右子树，那么该节点的后继节点是其右子树中val值最小的节点（也就是右子树中所谓的leftMostNode）

（下面不会遇到）

若一个节点没有右子树，那么判断该节点和其父节点的关系：
若该节点是其父节点的左边孩子，那么该节点的后继结点即为其父节点
若该节点是其父节点的右边孩子，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的左边孩子

def remove(currentNode):
    if currentNode.isleaf():  ### 情况1 是叶节点：
        if currentNode == currentNode.parent.leftchild:
            currentNode.parent.leftchild == None
        else:
            currentNode.parent.rightchild ==None 
            
    elif currentNode.hasbothchild():  ### 情况3，有左右两个节点
        succ = currentNode.findSuccessor()   # 找后继
        succ.spliceOut
        currentNode.key = succ.key
        currentNode.payload = succ.payload
    
    else:  #### 情况2. 有一个子节点
        if currentNode.hasleftchild():  # 如果有的是左节点，把节点上移
            if currentNode.isleftchild:     # 如果当前节点是左节点，上移为parent 的左节点
                currentNode.leftchild.parent = currentNode.parent
            elif currentNode.isrightchild:  # 如果当前节点是左节点，上移为parent 的左节点
                currentNode.rightchild.parent= currentNode.parent
            else:   # 如果当前节点是根节点，把这个根节点的信息替换为左子节点的信息
                currentNode.replaceNodeData(currentNode.leftchild.key, currentNode.leftchild.payload,currentNode.leftchild.leftchild,currentNode.leftchild.rightchild)
        else:   #如果有的是右节点，同上
            if currentNode.isleftchild:   # 如果当前节点是左节点，上移为parent 的左节点
                currentNode.rightchild.parent = currentNode.parent
            elif currentNode.isrightchild:  # 如果当前节点是左节点，上移为parent 的左节点
                currentNode.rightchild.parent = currentNode.parent
            else:   # 如果当前节点是根节点，把这个根节点的信息替换为左子节点的信息
                currentNode.replaceNodeData(currentNode.rightchild.key, currentNode.rightchild.payload,currentNode.rightchild.leftchild,currentNode.rightchild.rightchild)

练习

### 1.深度——第一反应：递归
def maxdepth(root):

    if root == None:   # 结束条件
        return 0

    depth1 = maxdepth(root.leftchild)+1   # 递归
    depth2 = maxdepth(root.rightchild)+1
    
    if depth1>depth2:   # 取出最大值
        return depth1
    else:
        return depth2
    
maxdepth(mytree1.root)


### 2.路径综合——第一反应：递归
# 如果比左边小右边大：差值对右边递归
# 如果比两边都大：差值对两边递归，取or
def sumPath(root, item):
    if item<0: 
        return False
    
    if not root:     # 如果已经到头item还没有匹配完，False
        return False
   
    if root.key == item and not root.leftchild and not root.rightchild:    
        return True
    
    print("当前root={}，item={}".format(root.key, item))
    left = sumPath(root.leftchild, item - root.key)
    right = sumPath(root.rightchild, item - root.key)

    return left or right

sumPath(mytree1.root, 1)  
sumPath(mytree1.root, 6)  
sumPath(mytree1.root, 7)
#### 最开始错误原因，没有判断是不是叶节点就输出True了


#### 3.每一层打印到一行—— 用队列处理
def printTree(root):
    results = []
    nodes = []

    nodes.append(root) 
    
    while len(nodes)>0:
        layers= [] 
        for i in range(len(nodes)):   # 一边把队首的pop出来，一边看如果有子节点就加入队列
            tmp = nodes.pop(0)
            layers.append(tmp.key)
            if tmp.leftchild:
                nodes.append(tmp.leftchild)
            if tmp.rightchild:
                nodes.append(tmp.rightchild)
        results.append(layers)
        print(results)

#测试
printTree(mytree1.root)

4



当前root=3，item=1





False



当前root=3，item=6
当前root=2，item=3
当前root=4，item=3





True



当前root=3，item=7
当前root=2，item=4
当前root=1，item=2
当前root=4，item=4
当前root=6，item=0





False



[[3]]
[[3], [2, 4]]
[[3], [2, 4], [1, 6]]
[[3], [2, 4], [1, 6], [7]]

二叉查找树

10.12

二叉查找树

前置知识：特殊方法

前置知识：yield

先序、中序、后序

最简单——用递归 复杂度o(n)

一个更加直观的例子

中序遍历——一个栈实现

练习，熟悉

10.13

remove

练习

感谢您的支持，我会继续努力的!

最简单——用递归复杂度o(n)