Skip to content

Latest commit

 

History

History
354 lines (301 loc) · 9.46 KB

binary_tree.md

File metadata and controls

354 lines (301 loc) · 9.46 KB
Raw

更新 2017-03-22

畏惧了好久的二叉树，终于在近两天开搞了。二分法查找已在前几天完成，磨刀霍霍向猪羊，吼吼吼！ 何为二叉树？按照我目前的理解就是类似于发叉的树，树干上发两个叉或者一个(不发叉的树真不到有何用处)，发叉的地方称为节点。然后发的两个叉又可以继续像树干一样发叉，新发的叉有可以继续发叉，子又生子，孙又生孙，无穷尽也！但是树的左边的叉的值小于节点值，右边的大于节点值。

本文参考： 老齐的Github

首先，建立一棵树。

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

这样，光秃秃的小树苗就种好了。接着就是茁长生长啦。浇水去喽！

class Node：
    '''
    ...
    '''
    def insert(self, data):
        if data < self.data: # 树叉小于节点
            if self.left is None: # 并且左面的树叉为空
                self.left = Node(data) # 当仁不让的插入
            else:                   # 非空的话
                self.left.insert(data) # 以左树叉为节点继续插入

        elif data > self.data:
            if self.right is None:
                self.right = Node(data)
            else:
                self.right.insert(data)
        else:
            self.data = data

浇完水后，小树苗噌噌的往上窜啊。

class Node：
    '''
    省略上述代码
    '''
    def search(self, data, parent=None):
    '''
    data为目标查询值，同时返回parent(父节点)便于定位。
    '''
        if data < self.data:
            if self.left is None:
                return None, None
            else:
                return self.left.search(data, self)

        elif data > self.data:
            if self.right is None:
                return None, None

            return self.right.search(data, self)
        else:
           #  return self.data, parent.data
            return self, parent

树苗生长的那么好，想看看每个叉上都是啥呀，来来来，抬头往上看((其实是往下看啦)。

def print_tree(self):
        if self.left:
            self.left.print_tree()
        print(self.data)
        if self.right:
            self.right.print_tree()

树的遍历又分为以下三种：

  1. 前序(root -> left -> right)
  2. 中序(left -> root -> right)
  3. 后序(left -> right -> root)

调整print_tree函数里 print(self.data) 的顺序即可实现三种遍历方式。

转眼间小树苗涨的太旺盛了，疯涨啊！！怎么办呢，剪几个枝吧。别怪我哦，小树苗！ 删除节点时，有三种可能的情况：

  1. 目标节点下没有任何节点(0个)
  2. 目标节点下有一个节点
  3. 目标节点下有两个节点

判断节点数目程序如下：

class Node：
'''
省略代码
'''
def chrildren(self):
    count = 0
    if self.left:
        count += 1

    if self.right:
        count += 1

    return count

接下来就是删除操作啦。哦吼吼。

class Node：
'''
省略
'''

def delete(self, data):
    node, parent = self.search(data)
    chrildren = node.chrildren() # 子节点数目
    if chrildren == 0: # 情况 1， 没有子节点，直接删除即可
        if parent.left is node: # 判断目标节点是其父节点的 左or右 节点
            parent.left = None
        else:
            parent.right = None
        del node

    elif chrildren == 1: # 情况 2， 有一个子节点，用子节点替换其即可
        if node.left:
            tmp = node.left
        else:
            tmp = node.right
        if parent:
            if parent.left is node:
                parent.left = tmp
            else:
                parent.right = tmp
        del node
    else:
    '''
    第三种情况比较复杂：
    1\. 左节点0个子节点
    2\. 左节点1个子节点
    3\. 左节点2个子节点
    '''
        parent = node
        successor = node.right
        while successor.left:  # 递归思想，直至找到'最左'的子节点， 保持树的平衡，用右子节点的值替换
            parent = successor
            successor = successor.left
        node.data = successor.data
        if parent.left ==  successor:
            parent.left = successor.right
        else:
            parent.right = successor.right

# 接下来可以测试以下种的树怎么样啦。

root = Node(11) root.insert(14) root.insert(9) root.insert(9) root.insert(7) root.insert(10) root.insert(4) root.insert(5) root.insert(6) root.insert(8) value, parent = root.search(10) print(value.data, parent.data) root.print_tree() print('_'_ 20) root.delete(4) root.print_tree()

把自己理解的部分写了写。当做练习，就先当个α版吧。 2016-05-28

基本搞明白了 完整代码在这里

广度遍历和深度遍历二叉树！

def lookup(root):
    stack = [root]
    while stack:
        current = stack.pop()
        print(current.data)
        if current.left:
            stack.append(current.left)
        if current.right:
            stack.append(current.right)


def deep(root):
    if not root:
        return
    deep(root.left)
    deep(root.right)
    print(root.data)

求最大树深

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def TreeDepth(self, pRoot):
        if not pRoot:
            return 0
        return max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right)) + 1

比较两棵树是否相同

def is_same(t1, t2):
    if t1 == None and t2 == None:
        return True
    elif t1 and t2:
        return t1.data == t2.data and is_same(t1.left, t2.left)\
                                  and is_same(t1.right, t2.right)
    else:
        return False

已知前序中序求后序

前面说到： 前序: root -> left -> right 中序: left -> root -> right 后序: left -> right -> root

前序: 第一个值 A 即为根节点 中序: A 的左边全为左子树，右边全是右子树

def pre_in_post(pre_order, in_order):
    if not pre_order:
        return
    post = Node(pre_order[0])
    index = in_order.index(pre_order[0])
    post.left = pre_in_post(pre_order[1:index+1], in_order[:index])
    post.right = pre_in_post(pre_order[index+1:], in_order[index+1:])
    return post

已知前序中序构造出树

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if not pre:
            return
        tree = TreeNode(pre[0])
        index = tin.index(pre[0])
        tree.left = self.reConstructBinaryTree(pre[1:index+1],tin[:index])
        tree.right = self.reConstructBinaryTree(pre[index+1:],tin[index+1:])
        return tree

    @classmethod
    def print_tree(cls, tree):
        if tree:
            cls.print_tree(tree.left)
            cls.print_tree(tree.right)
            print(tree.val)

pre = [1,2,3,4,5,6,7]
tin = [3,2,4,1,6,5,7]
s = Solution()
t = s.reConstructBinaryTree(pre, tin)
s.print_tree(t)

树的子结构

求pRoot2 的子树是否为 pRoot2
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def is_subtree(self, t1, t2): 
        if not t2:               # t2 is None 其为子树
            return True
        if not t1:
            return False
        if not t1.val == t2.val:
            return False
        return self.is_subtree(t1.left, t2.left) and self.is_subtree(t1.right, t2.right)
        
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        result = False
        if pRoot1 and pRoot2:
        	if pRoot1.val == pRoot2.val:
        	    result = self.is_subtree(pRoot1, pRoot2)
        	if not result:
        	    result = self.is_subtree(pRoot1.left, pRoot2)
        	if not result:
        	    result = self.is_subtree(pRoot1.right, pRoot2)
		return result

对称二叉树

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:

    def isSymmetrical(self, pRoot):
        def is_same(p1, p2):
            if not (p1 or p2):
                return True
            elif p1 and p2 and p1.val == p2.val:
                return is_same(p1.left, p2.right) and is_same(p1.right, p2.left)
            return False

        if not pRoot:
            return True
        return is_same(pRoot.left, pRoot.right)

二叉树镜像

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回镜像树的根节点
    def Mirror(self, root):
        # write code here
        if not root:
            return None
        elif not (root.left or root.right):
            return root
    	
        root.left, root.right = root.right, root.left
        if root.left:
            self.Mirror(root.left)
        if root.right:
            self.Mirror(root.right)