5 二分查找算法

二叉树:

　根节点

　　左叶子节点

　　右叶子节点

　　子树

二叉树的遍历:

　　广度遍历(层级) 插入到第一次出现的空节点上面

　　深度遍历:

　　　　前序(根左右)

　　　　中序(左根右)

　　　　后序(左右根)

# 广度遍历  
class Node():
    def __init__(self,item):
        self.item = item
        self.left = None
        self.right = None
class Tree():
    def __init__(self):
        self.root = None
    def add(self,item): #插入节点
        node = Node(item) #新节点
        
        if self.root is None: #空树
            self.root = node
            return       
        queue = [self.root]  #列表  根节点 [1] 
        while queue: 
            cur = queue.pop(0)  #根节点    pop 1了
            if cur.left is None:  #子树左叶子空之后的赋值
                cur.left = node  #节点赋值
                return
            else:
                queue.append(cur.left)  #不为空 就追加   [2]
            if cur.right is None:  #子树右叶子空之后的赋值
                cur.right = node
                return
            else:
                queue.append(cur.right)   #[2,3]
    def travel(self):   #遍历
        if self.root is None: #空树
            return
        queue = [self.root] #根节点
        
        while queue:  #[...]
            cur = queue.pop(0)
            print(cur.item) #节点数据
            if cur.left is not None:
                queue.append(cur.left)
            if cur.right is not None:
                queue.append(cur.right)

tree = Tree() #实例化一个二叉树
for i in range(10):
　　tree.add(i)
tree.travel() #遍历拿到所有数据

实现排序二叉树
class Node(): #节点类
    def __init__(self,item):
        self.item = item
        self.left = None
        self.right = None
class Tree(): #树类
    def __init__(self):
        self.root = None
        
    def insertByOder(self,item): #有序插入
        
        node = Node(item)  #实例化节点
        if self.root is None:  #空树
            self.root = node  #放置节点
            return
        
        cur = self.root 
        while True:
            if item < cur.item:
                if cur.left is None:  #cur左叶子节点为空
                    cur.left = node  #赋值
                    return
                else: 
                    cur = cur.left  #节点下移
            else:
                if cur.right is None:
                    cur.right = node
                    return
                else:
                    cur = cur.right
            
    def forward(self,root):  #前序
        if root is None:
            return
        # 根 左 右
        print(root.item,end=' ')
        self.forward(root.left) #递归  自己调用自己
        self.forward(root.right) 
    def mid(self,root):   #中序 -- 排序
        if root is None:
            return
        #左 根 右
        self.mid(root.left)
        print(root.item,end=' ')
        self.mid(root.right)
    def back(self,root):  #后序
        if root is None:
            return
        #左 右 根
        self.back(root.left)
        self.back(root.right)
        print(root.item,end=' ')
#前中   后中  画倒树方法         

t = Tree()
alist = [10,7,12,55,33,20,4]
for i in alist:
    t.insertByOder(i)
    
t.forward(t.root) #10 7 4 12 55 33 20
print('
')
t.mid(t.root)  #4 7 10 12 20 33 55  
print('
') 
t.back(t.root) #4 7 20 33 55 10
print('
')

5 二分查找 算法

5 二分查找算法