除了队列，栈等数据结构，树也是另一种数据结构。最常见的树结构就是家谱了，从祖先开始，若干个儿子，孙子等等。文件系统也是树结构的应用之一。

树用递归的定义来说就是，树有一个根节点，然后（可有可无）有若干个分支（子树），每个子树其实也是一棵树，也有若干个子树。如果每个节点最多有两个分支，那就是二叉树，如果最多有n个分支，那就是n叉树。

我才用列表嵌套的方式实现了二叉树。从递归的形式上说树的列表形式是[根节点，左子树，右子树]，而每个子树也是一棵树，所以每棵子树也是一个列表。

这样的话，初始化一棵树，即只有一个根节点，即[根节点，[]，[]]的形式。

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

然后有插入左子树的方法，插入左子树，要给出插入哪个节点的左子树，即有一个相对节点。而且插入左子树就是如果原始的左子树为空，那就直接插入列表。如果原始的左子树不是空，也就是把原来的左子树的列表直接替换掉，原始的左子树成为新的左子树的左子树。

def insertLeft(root,newBranch):
	# 先把原始的左子树取出来
    t = root.pop(1)
    # 判断原始左子树是否为空
    if len(t) > 1:
        root.insert(1,[newBranch,t,[]])
    else:
        root.insert(1,[newBranch, [], []])
    return root123456789

插入右子树同理。

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

然后就是获取这个树的根节点的值，比较简单，直接最外层的列表的第一个元素就是。修改根节点的值，直接索引赋值即可。

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

获取左子树，获取右子树，和上面一样，直接索引即可。

def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]12345

嵌套列表的形式实现树比较容易理解，容易查看树的逻辑出位置，变相的可视化吧。下面是整体的代码，测试一下。

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)

setRootVal(l,9)
print(r)
insertLeft(l,11)
print(r)
print(getRightChild(getRightChild(r)))

作者：qq_42907161

链接：https://blog.csdn.net/qq_42907161/article/details/108415902

来源：CSDN
著作权归作者所有，转载请联系作者获得授权，切勿私自转载。