数据结构__堆实现优先队列，二叉树几种遍历，优先队列实现哈弗曼树

柔情只为你懂 2022-05-27 14:13 153阅读 0赞

## 前景 ##

之前把二叉树部分学完了，今天整理一下，大概是这几小块

*  基于list实现的stack和queue
 *  二叉树的递归遍历、BFS、三种DFS
 *  基于堆（完全二叉树）的优先队列实现
 *  HaffMan树的优先队列实现

### Stack ###

class Stack:
        def __init__(self):
            self._elems = []
    
        def push(self, item):
            self._elems.append(item)
    
        def pop(self):
            return self._elems.pop()
    
        def top(self):
            return self._elems[-1]
    
        def is_empty(self):
            return len(self._elems) == 0

### Queue ###

class UnBlockingQueue:
        def __init__(self):
            self._elems = []
    
        def enqueue(self, item):
            self._elems.append(item)
    
        def ququue(self):
            return self._elems.pop(0)
    
        def head(self):
            return self._elems[0]
    
        def is_empty(self):
            return len(self._elems) == 0

### 二叉树 ###

from 数据结构与算法.Stack import Stack
    from 数据结构与算法.UnBlockingQueue import UnBlockingQueue as Queue
    
    
    # 二叉数节点
    class Node(object):
        def __init__(self, data, left, right):
            self.data = data
            self.left = left
            self.right = right
    
    
    class Tree(object):
    
        def __init__(self, data):
            self.root = Node(data, None, None)
    
        # 队列实现BFS 广度优先遍历
        def bfs(self, root):
            queue = Queue()
            queue.enqueue(root)
            while not queue.is_empty():
                root = queue.ququue()
                print(root.data)
                if root.left is not None:
                    queue.enqueue(root.left)
                if root.right is not None:
                    queue.enqueue(root.right)
    
        # 递归实现先序遍历
        def xianxu(self,root):
            if root:
                print(root.data)
                self.xianxu(root.left)
                self.xianxu(root.right)
    
        # 递归实现后续遍历
        def houxu(self,root):
            if root:
                self.houxu(root.left)
                self.houxu(root.right)
                print(root.data)
    
        # 递归实现中序遍历
        def zhongxu(self,root):
            if root:
                self.zhongxu(root.left)
                print(root.data)
                self.zhongxu(root.right)
    
        # stack 实现先序深度优先遍历
        def NFS_xianxu(self, root):
            stack = Stack()
            stack.push(root)
            while not stack.is_empty():
                while root is not None:
                    print(root.data)
                    stack.push(root.right)
                    root = root.left
                root = stack.pop()
    
        # stack 实现中序深度优先遍历
        def NFS_zhongxu(self, root):
            stack = Stack()
            while not stack.is_empty() or root is not None:
                while root is not None:
                    stack.push(root)
                    root = root.left
                if not stack.is_empty():
                    root = stack.pop()
                    print(root.data)
                    root = root.right
    
        # stack 实现后序深度优先遍历
        def NFS_houxu(self, root):
            stack = Stack()
            while not stack.is_empty() or root is not None:
                while root is not None:
                    stack.push(root)
                    if root.left is not None:
                        root = root.left
                    else:
                        root = root.right
                root = stack.pop()
                print(root.data)
                if not stack.is_empty() and root is stack.top().left :
                    root = stack.top().right
                else:
                    root = None
    
        # 另一种栈实现后序DFS的算法，简单些
        def DFS_2houxu(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 bfs2(root):
            queue = Queue()
            queue.enqueue(root)
            while not queue.is_empty():
                root = queue.ququue()
                print(root.data)
                if root.left is not None:
                    queue.enqueue(root.left)
                if root.right is not None:
                    queue.enqueue(root.right)
    
    
    if __name__ == '__main__':
        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.right.right.right = Node(10, None, None)
        print('\n宽度优先算法')
        tree.bfs(tree.root)
        print('\n先序NFS算法')
        tree.NFS_xianxu(tree.root)
        print('\n中序NFS算法')
        tree.NFS_zhongxu(tree.root)
        print('\n后序NFS算法')
        tree.NFS_houxu(tree.root)

### 优先队列堆实现 ###

class PriorityQueue:
        def __init__(self, elems=[]):
            self._elems = elems
            if elems:
                self.buildheap()
    
        # 向上筛选，从最后一个节点向上和它的父节点比较，小的上移
        # 参数：
        # e:代表需要进行比较的元素
        # last:代表列表的最后一个index
        def siftup(self, e, last):
            elems, i , parent = self._elems, last, (last-1)//2
            # 如果父节点比e大，将父节点下移,i位置始终存放较小的那个最终的结果
            while i > 0 and e < elems[parent]:
                elems[i] = elems[parent]
                # 将i,parent依次上移
                i, parent = parent, (parent-1)//2
            elems[i] = e
    
        # 向下筛选，从最上面的一个节点向下和它的两个子节点进行比较
        # 参数：
        # e：代表需要比较的元素
        # start:代表从哪个索引位置开始比较
        # end:代表结束的索引
        def siftdown(self, e, start, end):
            elems, i, child = self._elems, start, 2*start+1
            while child < end:
                // 角逐出子节点中较小的那一个
                if child+1 < end and elems[child+1] < elems[child]:
                    child += 1
                if e < elems[child]:
                    break
                # 如果子节点的值小于父节点，子节点上移
                elems[i] = elems[child]
                # 位置向上移动
                i, child = child, 2*child+1
            elems[i] = e
    
        def enqueue(self, e):
            self._elems.append(None)
            self.siftup(e, len(self._elems)-1)
    
        def ququeue(self):
            e0 = self._elems[0]
            e = self._elems.pop()
            if len(self._elems) > 0:
                self.siftdown(e, 0, len(self._elems))
            return e0
    
        def buildheap(self):
            end = len(self._elems)
            for i in range(end//2, -1, -1):
                self.siftdown(self._elems[i], i, end)
    
        def print(self):
            print(self._elems)
    
        def get_number(self):
            return len(self._elems)
    
    if __name__ == '__main__':
        queue = PriorityQueue()
        queue.enqueue(10)
        queue.enqueue(2)
        queue.print()
        queue = PriorityQueue([10, 2, 1, 6])
        queue.print()

查过库里面的优先队列实现，它也是基于堆的，思路差不多，堆的实现相对于二叉树的实现，还是相对陌生一点的，需要多领会几次才行，如果是初学者，那么建议你去网上搜一搜这部分详细的解释为妙

### HaffManTree ###

from 数据结构与算法.二叉树 import Node,Tree
    from 数据结构与算法.PriorityQueue import PriorityQueue
    
    class HaffManTreeNode(Node):
    
        def __lt__(self, other):
            return self.data < other.data
    
    # 代表节点的权值
    weights = [2, 2, 5, 10, 4, 3, 7]
    
    
    def haffman(weights):
        queue = PriorityQueue()
        for w in weights:
            queue.enqueue(HaffManTreeNode(w, None, None))
        # 从队列中取出前两个组合成新节点加入队列
        while queue.get_number() > 1:
            t1 = queue.ququeue()
            t2 = queue.ququeue()
            new = HaffManTreeNode(t1.data+t2.data, t1, t2)
            queue.enqueue(new)
        result = queue.ququeue()
        return result
    
    if __name__=='__main__':
        root = haffman(weights)
        Tree.bfs2(root)