栈队列二叉树的python实现

2021-01-20

二叉树

建立

即通过不断插入节点来建立出一棵二叉树。Node类定义树中每个节点的结构，Tree类定义一棵树，包括根节点和一个表示元素父子关系的队列。当树为空，待插入节点就作为根节点。否则针对当前队首的元素，查看它的左右孩子情况，若队首左孩子为空，待插入节点作为队首左孩子，并将此节点的值加入队列。若队首左孩子不为空，待插入节点作为队首元素的右孩子，同时将此节点的elem加入队列。队首元素被弹出，从而配合下一轮插入时myQueue[0]。

非递归的中序先序遍历

之所以放在一个小标题写，就是两者大体思路一致。

中序 : 1.先找到最左边的结点且依次入栈

2.对栈顶元素出栈如果它没有右孩子则将它出栈否则对其右孩子执行1。

先序：借助栈，先访问结点

1.再找到最左的结点

2.如果栈顶元素有右孩子，对其执行1。

后序遍历

考研用的是借助栈。

1.找到最左的结点依次入栈

2.对栈顶元素出栈如果有右孩子且未被访问对右孩子执行1 否则出栈

之后都用双栈，stack1记录后序遍历的逆序，存放在stack2里，最后输出stack2，即后序遍历。

# -*- coding:utf-8 -*-
"""
author: jueluo
annotation： 二叉树的创建 三种非递归遍历
"""
class Node:
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class Tree:
    def __init__(self):
        self.root = Node()
        self.myQueue = []

    def add(self, elem):
        """ 为二叉树添加节点"""
        node = Node(elem)  # 接收element参数
        if self.root.elem == -1:  # 根节点为空
            self.root = node  # 涉及到对tree的结构 tree包含root和myQueue 该两步分别解决root和myQueue
            self.myQueue.append(self.root)
        else:
            treeNode = self.myQueue[0]  # 队首的节点只有左右孩子都齐了 才能被pop出队
            if treeNode.lchild is None:
                treeNode.lchild = node
                self.myQueue.append(treeNode.lchild)
            else:
                treeNode.rchild = node  # 能不判断rchild是否None 就直接赋值 因为else只会走一次 待会儿队首元素就弹出去
                self.myQueue.append(treeNode.rchild)
                self.myQueue.pop(0)

    def preOrder(self, root):
        stack = []
        if root is None:
            return
        node = root
        while node or stack:
            while node:
                print(node.elem)  # 相当于伪代码的visit 这里为1 不断找最左的节点 访问后 并且入栈
                stack.append(node)
                node = node.lchild
            # 退出while循环 已经找到最左的节点 出栈 如果它有右孩子 则对其执行1
            node = stack.pop()
            node = node.rchild

    def inOrder(self, root):
        stack = []
        if root is None:
            return
        node = root
        while node or stack:
            while node:
                stack.append(node)
                node = node.lchild
            node = stack.pop()
            print(node.elem)
            node = node.rchild

    def postOrder(self, root):
        # 使用双栈 stack1记录后序排序(左右根)的逆序(根右左) 存入stack2 最后输出
        if root is None:
            return
        stack1 = []
        stack2 = []
        stack1.append(root)  # 根
        while stack1:
            node = stack1.pop()  # pop默认移除最后一个元素 此处node是上一轮最后append的rchild
            if node.lchild:
                stack1.append(node.lchild)
            if node.rchild:
                stack1.append(node.rchild)
            stack2.append(node)
        while stack2:
            print(stack2.pop().elem, end=' ')  # stack是列表 不是Stack类


if __name__ == '__main__':
    elements = range(10)
    tree = Tree()
    for element in elements:
        tree.add(element)
    tree.postOrder(tree.root)

栈

# -*- coding:utf-8 -*-
"""
author: jueluo
annotation: 实现栈及栈的5大基本操作初始化建栈  判栈满 入栈 判空 出栈
"""
class Stack:
    def __init__(self):
        self.__data = []

    def is_empty(self):
        """判断栈是否为空"""
        return self.__data == []

    def push(self, data):
        """在栈顶添加元素"""
        self.__data.append(data)

    def pop(self):
        """弹出顶部元素 出栈"""
        return self.__data.pop()

    def peek(self):
        """返回栈顶元素"""
        # 先判断是否为空
        if self.is_empty():
            return
        else:
            return self.__data[-1]

    def size(self):
        """判断长度"""
        return len(self.__data)

    def travel(self):
        """遍历所有元素"""
        self.__data = self.__data[::-1]
        for i in self.__data:
            print(i)


if __name__ == '__main__':
    a = Stack()
    print(a.is_empty())
    a.push(1)
    a.push(9)
    a.push(9)
    a.push(7)
    a.travel()

队列

# -*- coding:utf-8 -*-
"""
author: jueluo
annotation: 实现队列及基本操作
"""
class Queue:
    def __init__(self):
        self.__data = []

    def enqueue(self, data):
        """往队列头中添加一个新元素"""
        self.__data.insert(0, data)  # append只能插到最后 insert可以指定位置

    def travel(self):
        """遍历所有元素"""
        for i in self.__data:
            print(i, end='')
        print('')

    def dequeue(self):
        """从队列尾删除一个元素"""
        print(self.__data.pop())
        self.__data.pop()

    def is_empty(self):
        """判断队列是否为空"""
        return self.__data == []

    def size(self):
        """返回队列的元素个数"""
        return len(self.__data)


if __name__ == '__main__':
    q = Queue()
    q.enqueue(1)
    q.enqueue(9)
    q.enqueue(9)
    q.enqueue(7)  # 全入队后是 7 9 9 1 因为enqueue采用insert方法 位置参数为0 相当于次次头插   出队用pop pop默认弹出最后一个元素 按照 1 9 9 7 的顺序出队 书本上的思维先进先出 对的
    q.dequeue()

in a word

继续开垦，数据结构的实现，很基础，很必要。

二叉树

建立

非递归的中序 先序遍历

后序遍历

栈

队列

in a word

非递归的中序先序遍历