Python实现二叉树的定义、前序、中序、后序、层次遍历

本文主要是介绍Python实现二叉树的定义、前序、中序、后序、层次遍历，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

定义二叉树类，实现二叉树的插入、查找和赋值：

#!/usr/bin/python3
# -*- coding: utf-8 -*-


class BinaryTree:
    def __init__(self, root_obj):
        self.key = root_obj
        self.leftChild = None
        self.rightChild = None

    def insert_left(self, new_node):
        if self.leftChild is None:
            self.leftChild = BinaryTree(new_node)
        else:
            temp = BinaryTree(new_node)
            temp.leftChild = self.leftChild
            self.leftChild = temp

    def insert_right(self, new_node):
        if self.rightChild is None:
            self.rightChild = BinaryTree(new_node)
        else:
            temp = BinaryTree(new_node)
            temp.rightChild = self.rightChild
            self.rightChild = temp

    def get_right_node(self):
        return self.rightChild

    def get_left_node(self):
        return self.leftChild

    def set_root_val(self, obj):
        self.key = obj

    def get_root_val(self):
        return self.key


# tree = BinaryTree('root')
# print(tree.get_left_node())
# tree.insert_left('left001')
# tree.insert_right('right001')
# tree.get_left_node().insert_left('left002')
# print(tree.get_left_node().get_left_node().get_root_val())

实现二叉树的前序、中序、后序递归与非递归遍历，实现二叉树的层次遍历：

#!/usr/bin/python3
# -*- coding: utf-8 -*-

from Tree.BinaryTree import BinaryTree


tree = BinaryTree('root')
tree.insert_left('left001')
tree.insert_right('right001')
tree.get_left_node().insert_left('left-left-001')
tree.get_left_node().insert_right('left-right-001')
tree.get_right_node().insert_left('right-left-001')
tree.get_right_node().insert_right('right-right-001')


# 前序遍历（递归）: 根-左-右
def pre_order_recursive(root_node):
    if not root_node:
        return
    print(root_node.key)
    pre_order_recursive(root_node.leftChild)
    pre_order_recursive(root_node.rightChild)


# 前序遍历2（递归，带返回值）
def pre_order_recursive2(root_node):
    res = []

    def helper(root):
        if not root:
            return None
        res.append(root.key)
        helper(root.leftChild)
        helper(root.rightChild)
    helper(root_node)
    return res


# 前序非递归遍历
def pre_order_non_recursive(root_node):
    stack = [root_node]
    while stack:
        print(root_node.key)
        if root_node.rightChild:
            stack.append(root_node.rightChild)
        if root_node.leftChild:
            stack.append(root_node.leftChild)
        root_node = stack.pop()


# 前序非递归遍历（带返回值）
def pre_order_non_recursive2(root_node):
    res = []
    if not root_node:
        return res
    stack = [root_node]
    while stack:
        root_node = stack.pop()
        res.append(root_node.key)
        if root_node.rightChild:
            stack.append(root_node.rightChild)
        if root_node.leftChild:
            stack.append(root_node.leftChild)
    return res


# 中序遍历（递归）：左-根-右
def mid_order_recursive(root_node):
    if not root_node:
        return
    mid_order_recursive(root_node.leftChild)
    print(root_node.key)
    mid_order_recursive(root_node.rightChild)


# 中序递归遍历，带返回值
def mid_order_recursive2(root_node):
    res = []

    def helper(root):
        if not root:
            return
        helper(root.leftChild)
        res.append(root.key)
        helper(root.rightChild)
    helper(root_node)
    return res


# 中序非递归遍历
def mid_order_non_recursive(root_node):
    stack = []
    pos = root_node
    while pos or len(stack) > 0:
        if pos:
            stack.append(pos)
            pos = pos.leftChild
        else:
            pos = stack.pop()
            print(pos.key)
            pos = pos.rightChild


# 中序非递归遍历，带返回值
def mid_order_non_recursive2(root_node):
    res = []
    stack = []
    pos = root_node
    while pos or len(stack) > 0:
        if pos:
            stack.append(pos)
            pos = pos.leftChild
        else:
            pos = stack.pop()
            res.append(pos.key)
            pos = pos.rightChild
    return res


# 后续递归遍历：左-右-根
def post_order_recursive(root_node):
    if not root_node:
        return
    post_order_recursive(root_node.leftChild)
    post_order_recursive(root_node.rightChild)
    print(root_node.key)


# 后续递归遍历，带返回值
def post_order_recursive2(root_node):
    res = []

    def helper(root):
        if not root:
            return
        helper(root.leftChild)
        helper(root.rightChild)
        res.append(root.key)
    helper(root_node)
    return res


# 后序非递归遍历
# 使用两个栈结构，第一个栈类似前序遍历进栈（注意左右子节点入栈顺序和前序遍历的差别）；
# 第一个栈是先放根，再放右子树，再放左子树，在入栈的同时，也把每次的根节点放入stack2 ；
# 所以第二个栈stack2的入栈顺序是：根-右子树的根-右子树叶节点（先右后左）-左子树的根-左子树叶节点（先右后左）；
def post_order_non_recursive(root_node):
    stack = [root_node]
    stack2 = []
    while len(stack) > 0:
        node = stack.pop()
        stack2.append(node)
        if node.leftChild:
            stack.append(node.leftChild)
        if node.rightChild:
            stack.append(node.rightChild)
    while len(stack2) > 0:
        print(stack2.pop().key)


# 后序非递归遍历，带返回值
def post_order_non_recursive2(root_node):
    res = []
    stack = [root_node]
    stack2 = []
    while len(stack) > 0:
        node = stack.pop()
        stack2.append(node)
        if node.leftChild:
            stack.append(node.leftChild)
        if node.rightChild:
            stack.append(node.rightChild)
    while len(stack2) > 0:
        res.append(stack2.pop().key)
    return res


# 层次遍历
def layer_traverse(root_node):
    if not root_node:
        return None
    queue = [root_node]  # 因为是先进先出，所以用queue定义变量名更合适
    while len(queue) > 0:
        node = queue.pop(0)
        print(node.key)
        if node.leftChild:
            queue.append(node.leftChild)
        if node.rightChild:
            queue.append(node.rightChild)


# 层次遍历，带返回值
def layer_traverse2(root_node):
    res = []
    if not root_node:
        return None
    queue = [root_node]
    while len(queue) > 0:
        node = queue.pop(0)
        res.append(node.key)
        if node.leftChild:
            queue.append(node.leftChild)
        if node.rightChild:
            queue.append(node.rightChild)
    return res


print(layer_traverse2(tree))

这篇关于Python实现二叉树的定义、前序、中序、后序、层次遍历的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！