Python 实现二叉树相关操作

前言

继昨天的链表，今天又复习了一下二叉树，发现之前很熟练的东西，现在确实是很生疏了。看来知识真的是不学就忘啊。

方法声明

在开始介绍之前，依然先来罗列一下实现了哪些方法：

['getsize(self)']
['print(self)']
['qianxuDG(self, root)']
['zhongxuDG(self, root)']
['height(self, root)']
['deepth(self, root)']
['houxuDG(self, root)']
['xianxu(self)']
['zhongxu(self)']
['houxu(self)']
['width(self, root)']

所用的匹配代码如下：

# coding: utf8

# @Author: 郭 璞
# @File: getmethods.py                                                                 
# @Time: 2017/4/5                                   
# @Contact: 1064319632@qq.com
# @blog: http://blog.csdn.net/marksinoberg
# @Description: 获取一个模块或者类中的所有方法及参数列表

import re

def parse(filepath, repattern):
    with open(filepath, 'rb') as f:
        lines = f.readlines()
    # 预解析正则
    rep = re.compile(repattern)
    # 创建保存方法和参数列表的结果集列表
    result = []
    # 开始正式的匹配实现
    for line in lines:
        res = re.findall(rep, str(line))
        print("{}的匹配结果{}".format(str(line), res))
        if len(res)!=0 or res is not None:
            result.append(res)
        else:
            continue
    return [item for item in result if item !=[]]


if __name__ == '__main__':
    repattern = "def (.[^_0-9]+\(.*?\)):"
    filepath = './TwoBranchTree.py'
    result = parse(filepath, repattern)
    for item in result:
        print(str(item))

二叉树相关

因为思路都比较简单，所以下面就直接贴出代码了。该做注释的地方已经注释过了。

# coding: utf8

# @Author: 郭 璞
# @File: TwoBranchTree.py                                                                 
# @Time: 2017/4/6                                   
# @Contact: 1064319632@qq.com
# @blog: http://blog.csdn.net/marksinoberg
# @Description: 二叉树相关所有内容

# 创建二叉树节点
class Node(object):
    def __init__(self, data, left, right):
        self.data = data
        self.left = None
        self.right = None

# 创建二叉树
class Tree(object):
    # 创建一棵树，默认会有一个根节点
    def __init__(self, data):
        self.root = Node(data, None, None)
        self.size = 1

        ##########################################################为了计算二叉树的宽度而用
        # 存放各层节点数目
        self.n = []
        # 初始化层，否则列表访问无效
        for item in range(pow(2, 5)):
            self.n.append(0)
        # 索引标识
        self.maxwidth = 0
        self.i = 0


    # 求二叉树包含的节点数目
    def getsize(self):
        stack = [self.root]
        # 为了正确获取数目，这里需要先初始化一下
        self.size = 0
        while stack:
            temp = stack.pop(0)
            self.size += 1
            if temp.left:
                stack.append(temp.left)
            if temp.right:
                stack.append(temp.right)
        return self.size

    # 默认以层次遍历打印出该二叉树
    def print(self):
        stack = [self.root]
        while stack:
            temp = stack.pop(0)
            print(str(temp.data)+"\t", end='\t')
            if temp.left:
                stack.append(temp.left)
            if temp.right:
                stack.append(temp.right)
    # 递归实现前序遍历
    def qianxuDG(self, root):
        if root:
            print(root.data)
            self.qianxuDG(root.left)
            self.qianxuDG(root.right)

    # 递归实现中序遍历
    def zhongxuDG(self, root):
        if root:
            self.zhongxuDG(root.left)
            print(root.data)
            self.zhongxuDG(root.right)

    # 求得二叉树的最大高度
    def height(self, root):
        if not root:
            return 0
        ldeepth = self.height(root.left)
        rdeepth = self.height(root.right)
        return max(ldeepth+1, rdeepth+1)
    # 求得二叉树的最大深度
    def deepth(self, root):
        return self.height(root)-1
    # 递归实现后序遍历
    def houxuDG(self, root):
        if root:
            self.houxuDG(root.left)
            self.houxuDG(root.right)
            print(root.data)

    # 二叉树的先序遍历非递归实现
    def xianxu(self):
        """
        进栈向左走， 如果当前节点有右子树， 则先把右子树入栈，再把左子树入栈。来实现先根遍历效果
        :return:
        """
        if self.root is None:
            return
        else:
            stack = [self.root]
            while stack:
                current = stack.pop()
                print(current.data)
                if current.right:
                    stack.append(current.right)
                if current.left:
                    stack.append(current.left)

    # 二叉树的中序非递归实现
    def zhongxu(self):
        if self.root is None:
            return
        else:
            # stack = [self.root]
            # current = stack[-1]
            stack = []
            current = self.root
            while len(stack)!=0 or current:
                if current:
                    stack.append(current)
                    current = current.left
                else:
                    temp = stack.pop()
                    print(temp.data)
                    current = temp.right

    # 二叉树的后序非递归实现
    def houxu(self):
        if self.root is None:
            return
        else:
            stack1 = []
            stack2 = []
            stack1.append(self.root)
            # 对每一个头结点进行判断，先将该头结点放到栈2中，如果该节点有左子树则放入栈1， 有右子树也放到栈1
            while stack1:
                current = stack1.pop()
                stack2.append(current)
                if current.left:
                    stack1.append(current.left)
                if current.right:
                    stack1.append(current.right)
            # 直接遍历输出stack2即可
            while stack2:
                print(stack2.pop().data)

    # 求一颗二叉树的最大宽度
    def width(self, root):
        if root is None:
            return
        else:
            # 如果是访问根节点
            if self.i == 0:
                # 第一层加一
                self.n[0] =1
                # 到达第二层
                self.i += 1
                if root.left:
                    self.n[self.i] += 1
                if root.right:
                    self.n[self.i] += 1
                # print('临时数据：', self.n)
            else:
                # 访问子树
                self.i += 1
                # print('二叉树所在层数：', self.i)
                if root.left:
                    self.n[self.i] += 1
                if root.right:
                    self.n[self.i] += 1
            # 开始判断, 取出最大值
            # maxwidth = max(maxwidth, n[i])
            # maxwidth.append(max(max(maxwidth), n[i]))
            self.maxwidth= max(self.maxwidth, self.n[self.i])
            # 遍历左子树
            self.width(root.left)
            # 往上退一层
            self.i -= 1
            # 遍历右子树
            self.width(root.right)

            return self.maxwidth


if __name__ == '__main__':
    # 手动创建一课二叉树
    print('手动创建一课二叉树')
    tree = Tree(1)
    tree.root.left = Node(2, None, None)
    tree.root.right = Node(3, None, None)
    tree.root.left.left = Node(4, None, None)
    tree.root.left.right = Node(5, None, None)
    tree.root.right.left = Node(6, None, None)
    tree.root.right.right = Node(7, None, None)
    tree.root.left.left.left = Node(8, None, None)
    tree.root.left.left.right = Node(9, None, None)
    tree.root.left.right.left = Node(10, None, None)
    tree.root.left.right.left = Node(11, None, None)
    # 测试一下是否创建成功
    print('测试一下是否创建成功')
    print(tree.root.data)
    print(tree.root.left.data)
    print(tree.root.right.data)
    print(tree.root.left.left.data)
    print(tree.root.left.right.data)
    # 调用方法打印一下效果：以层次遍历实现
    print('调用方法打印一下效果：以层次遍历实现')
    tree.print()
    print('前序遍历递归实现')
    # 前序遍历递归实现
    tree.qianxuDG(tree.root)
    # 中序遍历递归实现
    print('中序遍历递归实现')
    tree.zhongxuDG(tree.root)
    # 后序遍历递归实现
    print('后序遍历递归实现')
    tree.houxuDG(tree.root)
    # 求取二叉树的高度
    print('求取二叉树的高度')
    print(tree.height(tree.root))
    # 求取二叉树的深度
    print('求取二叉树的深度')
    print(tree.deepth(tree.root))
    # 二叉树的非递归先序遍历实现
    print('二叉树的非递归先序遍历实现')
    tree.xianxu()
    print('中序非递归遍历测试')
    tree.zhongxu()
    print('后序非递归遍历测试')
    tree.houxu()
    print('二叉树的最大宽度为： {}'.format(tree.width(tree.root)))
    print('二叉树的节点数目为： {}'.format(tree.getsize()))

运行的效果如下：

D:\Software\Python3\python.exe E:/Code/Python/Python3/CommonTest/datastructor/TwoBranchTree.py
手动创建一课二叉树
测试一下是否创建成功
1
2
3
4
5
调用方法打印一下效果：以层次遍历实现
1       2       3       4       5       6       7       8       9       11      前序遍历递归实现
1
2
4
8
9
5
11
3
6
7
中序遍历递归实现
8
4
9
2
11
5
1
6
3
7
后序遍历递归实现
8
9
4
11
5
2
6
7
3
1
求取二叉树的高度
4
求取二叉树的深度
3
二叉树的非递归先序遍历实现
1
2
4
8
9
5
11
3
6
7
中序非递归遍历测试
8
4
9
2
11
5
1
6
3
7
后序非递归遍历测试
8
9
4
11
5
2
6
7
3
1
二叉树的最大宽度为： 4
二叉树的节点数目为： 10

Process finished with exit code 0

霍夫曼树实现

原理

霍夫曼在编码上有很大的用途，虽然还需要很多地方的改进。其目标就是尽可能使用最少的编码集来最大限度的进行编码，以此来节省空间。

算法也很简单，我们不妨先看一个小例子。

有这么一个序列 1，2，3，4，5。现在要用它来实现霍夫曼
-----------------------------------------------------------
/**
*  武功秘籍： 先对序列进行排序，然后永远找到序列中最小的两个值，然后在序列中去掉这俩。加和之后放到原来的序列中，再次进行排序。进行下一次循环的执行，直到序列中只剩下一个元素就可以停止了。
**/
-----------------------------------------------------------
所以第一次要找到两个最小的元素：1， 2。
此时序列内容为3，4，5
对1，2求和之后得到结果3，然后把这个3放到原来的序列中，此时序列变成了3，3，4，5
-----------------------------------------------------------
第二次：还是找最小的俩元素：3，3
求和得到6，放到原序列中，变成了4,5,6
-----------------------------------------------------------
第三次： 找最小4，5
求和得9，放到原序列：6，9
-----------------------------------------------------------
第四次：最小6，9
求和得到15，放到原序列15
-----------------------------------------------------------
第五次： 序列长度为1，不满足运算条件，执行完毕。
所以最终可以得到如下的一颗二叉树：
                      15
                     /  \
                    9     6
                  / \    /  \
                 4   5   3   3
                            /  \
                           1    2

代码实现一

以面向对象的方式实现：

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

class Huffman(object):

    def __init__(self, items=[]):
        while len(items)!=1:
            a, b = items[0], items[1]
            newvalue = a.value + b.value
            newnode = Node(value=newvalue)
            newnode.left, newnode.right = a, b
            items.remove(a)
            items.remove(b)
            items.append(newnode)
            items = sorted(items, key=lambda node: int(node.value))
            # 每次都要记得更新新的霍夫曼树的根节点
            self.root = newnode

    def print(self):
        queue = [self.root]
        while queue:
            current = queue.pop(0)
            print(current.value, end='\t')
            if(current.left):
                queue.append(current.left)
            if current.right:
                queue.append(current.right)
        print()

实现方式2

以面向过程的方式实现：

def sortlists(lists):
    return sorted(lists, key=lambda node: int(node.value))

def create_huffman_tree(lists):
    while len(lists)>1:
        a, b = lists[0], lists[1]
        node = Node(value=int(a.value+b.value))
        node.left, node.right = a, b
        lists.remove(a)
        lists.remove(b)
        lists.append(node)
        lists = sorted(lists, key=lambda node: node.value)
    return lists


def scan(root):
    if root:
        queue = [root]
        while queue:
            current = queue.pop(0)
            print(current.value, end='\t')
            if current.left:
                queue.append(current.left)
            if current.right:
                queue.append(current.right)

最终效果

if __name__ == '__main__':
    ls = [Node(i) for i in range(1, 5)]
    huffman = Huffman(items=ls)
    huffman.print()
    print('===================================, ')
    lssl = [Node(i) for i in range(1, 5)]
    root = create_huffman_tree(lssl)[0]
    scan(root)

运行结果：

D:\Software\Python3\python.exe E:/Code/Python/Python3/CommonTest/datastructor/霍夫曼树创建.py
10  4   6   3   3   1   2   
===================================, 下面的方式不正确的原因是ls已经被上面代码修改过了，需要重新设置一下！
10  4   6   3   3   1   2   
Process finished with exit code 0

总结

“好记性，不如烂笔头”。与君共勉。