python 实现二叉树

Trami

程序如下：
def create_tree(root, val):
    newnode = tree()
    newnode.data = val
    newnode.left = left
    newnode.right = right

    if root == None:
        root = newnode
        return root
    else:
        current = root
        while current != None:
            backup = current
            if current.data > val:
                current = current.left
            else:
                current = current.right
        if backup.data > val:
            backup.left = newnode
        else:
            backup.right = newnode
        return root
我不太理解这段程序中backup的判断部分起到一个什么作用，希望了解的大牛能讲解一下吗，感激不尽

claws0n

呃……非常不好的命名……没有用过 python 写这样的程序，当作这个程序是没问题的~
backup 是双亲节点。 while current != None: 就是遍历到树的叶子节点，然后 if ... 就是把数据放到应该放的位置。

Trami

对啊，我也是觉得这个程序写的非常冗余，我自己看了一下，也看了一下网上的一般都是直接用递归，写起来简洁而且容易理解

claws0n

Trami 发表于 2018-9-30 21:17
对啊，我也是觉得这个程序写的非常冗余，我自己看了一下，也看了一下网上的一般都是直接用递归，写起来简洁 ...

递归一般都很简洁，但是如果要论效率的话，迭代的效率会比较好（会写的话）。递归调用的话，内存会限制树的深度，循环就没有这个问题。

RIXO

没什么啊，他就是想有个变量保存current的值，能把节点赋值给当前目录下左边的树，因为前面不是有个while true的循环吗？current的值就丢了，所以需要一个变量保存这个值

RIXO

呃，再补充一下吧，就是从根目录，你一直往下面找寻这个值，最底层的树保存的是这个值 （这个应该能理解把） ，但是这个逻辑是向着一个根就延续下去，到了倒数第二层的时候问题就出现了，你接着访问，如果没有访问到，实际上current还是被赋值了，然后就回不去了，肯定得在倒数第二层的左边树或者右边树开始找，这时候backup就起作用了，但是current这时候没有变，就比如说赋值了  current.left     因为这时候没有data  data是None，你就要在这里创建一个新的节点。
捋一捋   就是     current   =   None   的时候     backup是上一个节点    然后算   current  到哪一边去了，左边还是右边，然后在左边或者右边建个树对象，也就是创建个节点