Python 二叉树

python 二叉树

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

  • 一个节点被标记为根节点。
  • 除根之外的每个节点都与一个父节点相关联。
  • 每个节点可以有一个数字的节点号。

我们使用前面讨论的概念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

 

travesring一棵树

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

下一节:python 搜索树

python 数据结构

相关文章