摘要：概要本文只實現(xiàn)了二叉樹基本的幾種遍歷，增刪改查，預計明天寫完，后面的功能也盡量完善定義數(shù)據(jù)結(jié)構(gòu)左節(jié)點右節(jié)點先序遍歷先遍歷順序，根節(jié)點，遍歷左子樹，遍歷右子樹中序遍歷中序遍歷中序遍歷順序，遍歷左子樹，根節(jié)點，遍歷右子樹后序遍歷后序遍歷后序遍歷

概要

本文只實現(xiàn)了二叉樹基本的幾種遍歷，增、刪、改、查，預計明天寫完，后面的功能也盡量完善

定義Node數(shù)據(jù)結(jié)構(gòu)

class Node(object):
    def __init__(self, data):
        self.data = data
        self.lft = None #左節(jié)點
        self.rgt = None #右節(jié)點

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

    def preOrder(self):
        """
        先遍歷順序：
        1，根節(jié)點
        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，根節(jié)點
        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，根節(jié)點
        """
        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源碼