快捷導(dǎo)航

教你如何使用Python實(shí)現(xiàn)二叉樹結(jié)構(gòu)及三種遍歷

更新時(shí)間：2021年06月18日 10:25:26 作者：小白地瓜

什么是二叉樹：每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu),通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）二叉樹由兩個(gè)對(duì)象組成,一個(gè)是節(jié)點(diǎn)對(duì)象,一個(gè)是樹對(duì)象,需要的朋友可以參考下

一：代碼實(shí)現(xiàn)

class TreeNode:
    """節(jié)點(diǎn)類"""
    def __init__(self, mid, left=None, right=None):
        self.mid = mid
        self.left = left
        self.right = right


# 樹類
class Tree:
    """樹類"""
    def __init__(self, root=None):
        self.root = root

    def add(self, item):
        # 將要添加的數(shù)據(jù)封裝成一個(gè)node結(jié)點(diǎn)
        node = TreeNode(item)
        if not self.root:
            self.root = node
            return
        queue = [self.root]
        while queue:
            cur = queue.pop(0)
            if not cur.left:
                cur.left = node
                return
            else:
                queue.append(cur.left)

            if not cur.right:
                cur.right = node
                return
            else:
                queue.append(cur.right)
               
tree = Tree()
tree.add(0)
tree.add(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
tree.add(6)

二：遍歷

在上述樹類代碼基礎(chǔ)上加遍歷函數(shù)，基于遞歸實(shí)現(xiàn)。

在這里插入圖片描述

先序遍歷：

先序遍歷結(jié)果是：0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6

# 先序遍歷
    def preorder(self, root, result=[]):
        if not root:
            return
        result.append(root.mid)
        self.preorder(root.left, result)
        self.preorder(root.right, result)
        return result
        
print("先序遍歷")
print(tree.preorder(tree.root))
"""
先序遍歷
[0, 1, 3, 4, 2, 5, 6]
"""

中序遍歷：

中序遍歷結(jié)果是：3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 6

# 中序遍歷
    def inorder(self, root, result=[]):
        if not root:
            return result
        self.inorder(root.left, result)
        result.append(root.mid)
        self.inorder(root.right, result)
        return result
        
print("中序遍歷")
print(tree.inorder(tree.root))
"""
中序遍歷
3, 1, 4, 0, 5, 2, 6]
"""

后續(xù)遍歷

后序遍歷結(jié)果是：3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0

# 后序遍歷
    def postorder(self, root, result=[]):
        if not root:
            return result
        self.postorder(root.left, result)
        self.postorder(root.right, result)
        result.append(root.mid)

        return result
        
print("后序遍歷")
print(tree.postorder(tree.root))
"""
后序遍歷
[3, 4, 1, 5, 6, 2, 0]
"""

到此這篇關(guān)于教你如何使用Python實(shí)現(xiàn)二叉樹結(jié)構(gòu)及三種遍歷的文章就介紹到這了,更多相關(guān)Python實(shí)現(xiàn)二叉樹結(jié)構(gòu)及三種遍歷內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: