除了链表嵌套法实现树，最形象就是节点链接法了。每个节点就相当于树的节点，树的节点是要连接的，并且有左子树和右子树，所以就和链表那样，用节点的某个变量保存下一个节点（两个子树），其实树是一个递归的数据结构。

首先定义一个树类，并初始化树。只有一个根节点，节点的值为定义时传进来的。因为需要左右两个子树，所以准备两个变量用于保存左右子树的引用。

class bin_tree(object):
    def __init__(self, root_value):
        self.key = root_value
        self.lc = None
        self.rc = None12345

然后定义了一个插入左子树的方法。和前面那篇文章一样，观察当然要插入的目标（子）树是否有没有左子树，如果没有，则直接赋值即可（当然首先要创建树再赋值）。如果有，则把原来的左子树替换掉，并把原来的左子树作为新插入左子树的左子树。

    def insert_lc(self, new_node):
        if self.lc == None:
            self.lc =  bin_tree(new_node)
        else:
            temp = bin_tree(new_node)
            temp.lc = self.lc
            self.lc = temp1234567

插入右子树同理。

    def insert_rc(self, new_node):
        if self.rc == None:
            self.rc =  bin_tree(new_node)
        else:
            temp = bin_tree(new_node)
            temp.rc = self.rc
            self.rc = temp1234567

然后就是一些小函数了，返回子树的值，设置根节点的值等等。

    def get_rc(self):
        return self.rc

    def get_lc(self):
        return self.lc

    def get_root_value(self):
        return self.key

    def set_root_value(self, new_obj):
        self.key = new_obj123456789101112

完整的代码测试一下。

# 链表实现树

class bin_tree(object):
    def __init__(self, root_value):
        self.key = root_value
        self.lc = None
        self.rc = None

    def insert_lc(self, new_node):
        if self.lc == None:
            self.lc =  bin_tree(new_node)
        else:
            temp = bin_tree(new_node)
            temp.lc = self.lc
            self.lc = temp

    def insert_rc(self, new_node):
        if self.rc == None:
            self.rc =  bin_tree(new_node)
        else:
            temp = bin_tree(new_node)
            temp.rc = self.rc
            self.rc = temp

    def get_rc(self):
        return self.rc

    def get_lc(self):
        return self.lc

    def get_root_value(self):
        return self.key

    def set_root_value(self, new_obj):
        self.key = new_obj
 
bt = bin_tree('a')
print(bt.get_root_value())

print(bt.get_lc())

bt.insert_lc('b')

print(bt.get_lc())

print(bt.get_lc().get_root_value())

bt.insert_rc('c')

print(bt.get_rc())

print(bt.get_rc().get_root_value())

bt.get_rc().set_root_value('hello')

print(bt.get_rc().get_root_value())

作者：qq_42907161

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

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