当前位置: 首页 > 文档资料 > Python 数据结构 >

Binary Tree

优质
小牛编辑
136浏览
2023-12-01

树表示由边连接的节点。 它是一种非线性数据结构。 它具有以下属性。

  • 一个节点标记为根节点。
  • 除根之外的每个节点都与一个父节点相关联。
  • 每个节点可以具有arbiatry数量的chid节点。

我们使用前面讨论的概念os节点在python中创建树数据结构。 我们将一个节点指定为根节点,然后添加更多节点作为子节点。 下面是创建根节点的程序。

创建根

我们只创建一个Node类并添加为节点赋值。 这将成为仅具有根节点的树。

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data
    def PrintTree(self):
        print(self.data)
root = Node(10)
root.PrintTree()

执行上述代码时,会产生以下结果 -

10

插入树中

要插入到树中,我们使用上面创建的相同节点类,并为其添加插入类。 insert类将节点的值与父节点进行比较,并决定将其添加为左节点或右节点。 最后,PrintTree类用于打印树。

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data
    def insert(self, data):
# Compare the new value with the parent node
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()
# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
root.PrintTree()

执行上述代码时,会产生以下结果 -

3 6 12 14

穿越一棵树

可以通过决定访问每个节点的序列来遍历树。 我们可以清楚地看到我们可以从一个节点开始,然后访问左子树,然后是第一个和右子树。 或者我们也可以先访问右子树,然后访问左子树。 因此,这些树遍历方法有不同的名称。 我们在这里实现树遍历算法的章节中详细研究它们。