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

概要

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

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

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

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

    def preOrder(self):
        """
        先遍歷順序：
        1，根節(jié)點(diǎn)
        2，遍歷左子樹(shù)
        3，遍歷右子樹(shù)
        """
        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，遍歷左子樹(shù)
        2，根節(jié)點(diǎn)
        3，遍歷右子樹(shù)
        """
        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，遍歷左子樹(shù)
        2，遍歷右子樹(shù)
        3，根節(jié)點(diǎn)
        """
        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是一個(gè)雙向隊(duì)列，先進(jìn)先出是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源碼