快捷導(dǎo)航

python數(shù)據(jù)結(jié)構(gòu)之二叉樹的建立實(shí)例

更新時(shí)間：2014年04月29日 09:02:42 作者：

這篇文章主要介紹了python數(shù)據(jù)結(jié)構(gòu)之二叉樹的建立實(shí)例,采用了類似遞歸方式建立,需要的朋友可以參考下

先建立二叉樹節(jié)點(diǎn)，有一個(gè)data數(shù)據(jù)域，left，right 兩個(gè)指針域

# -*- coding: utf - 8 - *-

                 
class TreeNode(object):

    def __init__(self, left=0, right=0, data=0):
        self.left = left
        self.right = right
        self.data = data

復(fù)制代碼代碼如下:

class BTree(object):

    def __init__(self, root=0):
        self.root = root

手動(dòng)建立二叉樹

復(fù)制代碼代碼如下:

node1 = TreeNode(data=1)
node2 = TreeNode(node1, 0, 2)
node3 = TreeNode(data=3)
node4 = TreeNode(data=4)
node5 = TreeNode(node3, node4, 5)
node6 = TreeNode(node2, node5, 6)
node7 = TreeNode(node6, 0, 7)
node8 = TreeNode(data=8)
root = TreeNode(node7, node8, 'root')

bt = BTree(root)

然后會(huì)生成下面的二叉樹

復(fù)制代碼代碼如下:

# 生成的二叉樹

# ------------------------
#          root
#       7        8
#     6
#   2   5
# 1    3 4
#
# -------------------------

除了手動(dòng)一個(gè)個(gè)的制定 node 節(jié)點(diǎn)，還可以創(chuàng)建一個(gè) create 方法，接受用戶輸入添加二叉樹節(jié)點(diǎn)。。。使用前續(xù)方式添加，代碼如下：

復(fù)制代碼代碼如下:

# -*- coding: utf - 8 - *-

           
class TreeNode(object):

    def __init__(self, left=0, right=0, data=0):
        self.left = left
        self.right = right
        self.data = data

           
class BTree(object):

    def __init__(self, root=0):
        self.root = root

    def is_empty(self):
        if self.root is 0:
            return True
        else:
            return False

    def create(self):
        temp = input('enter a value:')
        if temp is '#':
            return 0
        treenode = TreeNode(data=temp)
        if self.root is 0:
            self.root = treenode

        treenode.left = self.create()
        treenode.right = self.create()

使用create創(chuàng)建二叉樹

復(fù)制代碼代碼如下:

#運(yùn)行文件 在交互解釋器下面運(yùn)行

bt = BTree()

bt.create()
enter a value:9
enter a value:7
enter a value:6
enter a value:2
enter a value:1
enter a value:'#'
enter a value:'#'
enter a value:'#'
enter a value:5
enter a value:3
enter a value:'#'
enter a value:'#'
enter a value:4
enter a value:'#'
enter a value:'#'
enter a value:'#'
enter a value:8
enter a value:'#'
enter a value:'#'