Python中有關(guān)樹的使用方法

本篇文章給大家分享的是有關(guān)Python中有關(guān)樹的使用方法，小編覺得挺實用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

樹的存儲、表示與遍歷

樹的存儲與表示

順序存儲:將數(shù)據(jù)結(jié)構(gòu)存儲在固定的數(shù)組中,然在遍歷速度上有一定的優(yōu)勢,但因所占空間比較大,是非主流二叉樹。二叉樹通常以鏈?zhǔn)酱鎯Α?/p>

某個節(jié)點為空是用0表示。

節(jié)點的結(jié)構(gòu)：

二叉樹的建立

class Node(object):
    """二叉樹節(jié)點的封裝"""
    def __init__(self, element=None, lchild=None, rchild=None):
        self.element = element
        self.lchild = lchild
        self.rchild = rchild
class Tree(object):
    """二叉樹的封裝"""
    def __init__(self, root=None):
        self.root = root
    def __add__(self, element):
        # 插入節(jié)點的封裝
        node = Node(element)
        # 1.判斷是否為空，則對根結(jié)點進行賦值
        if not self.root:
            self.root = node
        # 2. 如果存在跟結(jié)點，將根結(jié)點放入隊列
        else:
            queue = []
            # 將根結(jié)點放入隊列中
            queue.append(self.root)
            # 對隊列中的所有節(jié)點進行遍歷
            # 這里的循環(huán)每次都是從根結(jié)點往下循環(huán)的
            while queue:
                # 3.彈出隊列中的第一個元素(第一次彈出的為根節(jié)點，然后是根的左節(jié)點，根的右節(jié)點，依次類推)
                cur = queue.pop(0)
                if not cur.lchild:
                    cur.lchild = node
                    return
                elif not cur.rchild:
                    cur.rchild = node
                    return
                else:
                    # 左右子樹都存在就將左右子樹添加到隊列中去
                    queue.append(cur.lchild)
                    queue.append(cur.rchild)

二叉樹的遍歷

遍歷是指對樹中所有結(jié)點的信息的訪問,即依次對樹中每個結(jié)點訪問一次且僅訪問一次,我們把這種對所有節(jié)點的訪問稱為遍歷(traversal)

廣度優(yōu)先遍歷（層次遍歷）

遍歷結(jié)果為1，2，3，4，5，6，7

  def breadth_travel(self):
        """利用隊列實現(xiàn)樹的層次遍歷"""
        if self.root == None:
            return
        # 將二叉樹的節(jié)點依次放入隊列中，通過訪問隊列的形式實現(xiàn)樹的遍歷
        queue = []
        queue.append(self.root)
        while queue:
            node = queue.pop(0)
            print(node.element, end=',')
            if node.lchild != None:
                queue.append(node.lchild)
            if node.rchild != None:
                queue.append(node.rchild)
        print()

深度優(yōu)先遍歷

深度優(yōu)先遍歷有三種方式：

先序遍歷（根->左->右）：先訪問根結(jié)點，再先序遍歷左子樹，最后再先序遍歷右子樹，

中序遍歷（左->根->右）：先中序遍歷左子樹，然后再訪問根結(jié)點，最后再中序遍歷右子樹，

后序遍歷（左->右->根）：先后序遍歷左子樹，然后再后序遍歷右子樹，最后再訪問根結(jié)點。

先序遍歷： 1 2 4 5 3 6 7

中序遍歷： 4 2 5 1 6 3 7

后序遍歷： 4 5 2 6 7 3 1

遞歸實現(xiàn)先序遍歷

# 深度優(yōu)先遍歷：先序遍歷---根 左 右
    def preorder(self, root):
        """遞歸實現(xiàn)先序遍歷"""
        if not root:
            return
        print(root.element, end=',')
        self.preorder(root.lchild)
        self.preorder(root.rchild)

遞歸實現(xiàn)中序遍歷

# 深度優(yōu)先遍歷：中序遍歷---左 根 右
    def inorder(self, root):
        """遞歸實現(xiàn)中序遍歷"""
        if not root:
            return
        self.inorder(root.lchild)
        print(root.element, end=',')
        self.inorder(root.rchild)

遞歸實現(xiàn)后序遍歷

    # 深度優(yōu)先遍歷：后序遍歷---左 右 根
    def postorder(self, root):
        """遞歸實現(xiàn)后序遍歷"""
        if not root:
            return
        self.postorder(root.lchild)
        self.postorder(root.rchild)
        print(root.element, end=',')

測試代碼：

if __name__ == '__main__':
    binaryTree = Tree()
    for i in range(7):
        binaryTree.__add__(i+1)
    # 廣度優(yōu)先遍歷
    print("廣度優(yōu)先：")
    binaryTree.breadth_travel()
    # 深度優(yōu)先，先序遍歷
    root = binaryTree.root
    binaryTree.preorder(root)
    print('深度優(yōu)先--先序遍歷')
    binaryTree.inorder(root)
    print('深度優(yōu)先--中序遍歷')
    binaryTree.postorder(root)
    print('深度優(yōu)先--后序遍歷')

廣度優(yōu)先：
1,2,3,4,5,6,7,
1,2,4,5,3,6,7,深度優(yōu)先--先序遍歷
4,2,5,1,6,3,7,深度優(yōu)先--中序遍歷
4,5,2,6,7,3,1,深度優(yōu)先--后序遍歷

和我們預(yù)期的結(jié)果完全相同。

以上就是Python中有關(guān)樹的使用方法，小編相信有部分知識點可能是我們?nèi)粘９ぷ鲿姷交蛴玫降?。希望你能通過這篇文章學(xué)到更多知識。更多詳情敬請關(guān)注億速云行業(yè)資訊頻道。