Python实现树结构的两种方式

2022年 11月 7日

Python实现树结构的两种方式

1 实现树结构的列表方法是：嵌套列表法
这里把我踩的坑记录一下

'''
使用嵌套列表法实现树的基本功能
'''

def BinaryTree(r):
    return [r, [], []]

def insertLeft(root, newBranch):
    t = root.pop(1)
    if len(t) > 1:
        # 如果左子树非空，就把原来根节点上的左子树作为新的根的左节点的左子树
        root.insert(1, [newBranch, t, []])
    else:
        # 如果左子树为空，就直接插入新的树作为根节点的左子树
        root.insert(1, [newBranch, [], []])
    return root

def insertRight(root, newBranch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2, [newBranch, [], t])
    else:
        root.insert(2, [newBranch, [], []])
    return root

def getRootVal(root):
    return root[0]

def setRootVal(root, newVal):
    root[0] = newVal

def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]

r = BinaryTree(3)
insertLeft(r, 4)
insertLeft(r, 5)
insertRight(r, 6)
insertRight(r, 7)
l = getLeftChild(r)
print(l)
print(r)

这里需要强调的是，当在一棵树中插入新的节点或者分支时，应该首先要明确的是新的节点或分支的根是谁，这是插入任何节点或分支的先决条件，一般来说，不会一直往根节点插入新的节点或分支。
2 实现树结构的第二种方法是使用链表

'''
用节点链接法实现树
每个节点保存根节点的数据项，以及指向左右子树的链接
'''
class BinaryTree:
    def __init__(self, rootObj):
        # 成员key保存够根节点数据项
        # 成员left/rightChild保存指向左/右子树的引用（同样是BinaryTree）
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

    def insertLeft(self, newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t

    def insertRight(self, newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t

    def getRightChild(self):
        return self.rightChild

    def getLeftChild(self):
        return self.leftChild
    
    def setRootVal(self, obj):
        self.key = obj

    def getRootVal(self):
        return self.key
        
r = BinaryTree('a')
r.insertLeft('b')
r.insertRight('c')
r.getRightChild().setRootVal('hello')
r.getLeftChild().insertRight('d')