python-二叉树：前、中、后、层序遍历

摘要：概要本文只实现了二叉树基本的几种遍历，增删改查，预计明天写完，后面的功能也尽量完善定义数据结构左节点右节点先序遍历先遍历顺序，根节点，遍历左子树，遍历右子树中序遍历中序遍历中序遍历顺序，遍历左子树，根节点，遍历右子树后序遍历后序遍历后序遍历

概要

本文只实现了二叉树基本的几种遍历，增、删、改、查，预计明天写完，后面的功能也尽量完善

定义Node数据结构

class Node(object):
    def __init__(self, data):
        self.data = data
        self.lft = None #左节点
        self.rgt = None #右节点

class BTree(object):
    def __init__(self):
        self._root = None
        self._size = 0

    def preOrder(self):
        """
        先遍历顺序：
        1，根节点
        2，遍历左子树
        3，遍历右子树
        """
        btree = []
        
        def recurse(node):
            if node != None:
                btree.append(node.data)
                recurse(node.lft)
                recurse(node.rgt)
        
        recurse(self._root)
        return btree

中序遍历

class BTree(object):
    def __init__(self):
        self._root = None
        self._size = 0
    
    # 中序遍历
    def inOrder(self):
        """
        中序遍历顺序：
        1，遍历左子树
        2，根节点
        3，遍历右子树
        """
        btree = []
        
        def recurse(node):
            if node != None:
                recurse(node.lft)
                btree.append(node.data)
                recurse(node.rgt)
        
        recurse(self._root)
        return btree

后序遍历

class BTree(object):
    def __init__(self):
        self._root = None
        self._size = 0
    
    # 后序遍历
    def postOrder(self):
        """
        后序遍历顺序：
        1，遍历左子树
        2，遍历右子树
        3，根节点
        """
        btree = []
        
        def recurse(node):
            if node != None:
                recurse(node.lft)
                recurse(node.rgt)
                btree.append(node.data)
        
        recurse(self._root)
        return btree

层序遍历

from  collections import deque


class BTree(object):
    def __init__(self):
        self._root = None
        self._size = 0
    
    # 层序遍历
    def leverOrder(self):
        q = deque()
        q.append(self._root)
        btree = []
        while q:
            #dque是一个双向队列，先进先出是popleft
            node = q.popleft()
            btree.append(node.data)
            if node.lft:
                q.append(node.lft)
            if node.rgt:
                q.append(node.rgt)
        return btree

引用

github 源码Btree源码