数据结构学习-python实现-树--0413

# 用嵌套列表实现二叉树
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 getrootvalue(root):
    return root[0]

def setrootvalue(root, newvalue):
    root[0] = newvalue

def getleftchild(root):
    return root[1]

def getrightchild(root):
    return root[2]

r = binarytree(3)
insertleft(r, 4)
insertright(r, 5)
insertright(r, 6)
insertright(r, 7)

l = getleftchild(r)
print(l)

setrootvalue(l, 9)
print(r)

insertleft(l, 11)
print(r)

# 递归的思想生成二叉树
class BinaryTree:
    def __init__(self, rootobj):
        self.key = rootobj  # 节点值
        self.leftchild = None  # 左子树
        self.rightchild = None  # 右子树

    def insertleft(self, newnode):  # 记住每个节点的插入，都是子树，叶子只是子树为None。
        t = BinaryTree(newnode)
        if self.leftchild is None:
            self.leftchild = t
        else:
            t.leftchild = self.leftchild
            self.leftchild = t

    def insertright(self, newnode):
        t = BinaryTree(newnode)
        if self.rightchild is None:
            self.rightchild = t
        else:
            t.rightchild = self.rightchild
            self.rightchild = t

    def getrightchild(self):
        return self.rightchild

    def getleftchild(self):
        return self.leftchild

    def setrootvalue(self, obj):
        self.key = obj

    def getrootvalue(self):
        return self.key

r = BinaryTree('a')
r.insertleft('b')
r.insertright('c')
r.getrightchild().setrootvalue('hello')
r.getleftchild().insertright('d')

# 生成的是树，需要使用遍历的方法查看。此方法是中序遍历。
def printexp(tree):
    sval = ''
    if tree:
        sval = printexp(tree.getleftchild())
        sval = sval + str(tree.getrootvalue())
        sval = sval + printexp(tree.getrightchild())
        if len(sval) != 1:
            sval = '(' + sval + ')'
    return sval
    

def preorder(tree):  # 前序遍历，记住递归的思想
    if tree:
        print(tree.getrootvalue())
        preorder(tree.getleftchild())
        preorder(tree.getrightchild())


def postorder(tree):  # 后序遍历
    if tree is not None:
        postorder(tree.getleftchild())
        postorder(tree.getrightchild())
        print(tree.getrootvalue())


def inorder(tree):  # 中序遍历
    if tree is not None:
        inorder(tree.getleftchild())
        print(tree.getrootvalue())
        inorder(tree.getrightchild())