Python编写二叉树和递归报错

Question

我用Python编写二叉树时，代码如下

class Node(object):
    def __init__(self, data=None, lchild=None, rchild=None):
        self.elem = data  # 表示数据域
        self.lchild = lchild  # 表示左子树
        self.rchild = rchild  # 表示右子树

    def PreOrder(self, root):
        if root == None:
            return
        print(root.elem)
        self.PreOrder(root.lchild)  # 先序遍历左子树
        self.PreOrder(root.rchild)  # 先序遍历右子树

    def InOrder(self, root):
        if root == None:
            return
        self.InOrder(root.lchild)  # 中序遍历左子树
        print(root.elem)
        self.InOrder(root.rchild)  # 中序遍历右子树

    def PostOrder(self, root):
        if root == None:
            return
        self.PostOrder(root.lchild)  # 后序遍历左子树
        self.PostOrder(root.rchild)  # 后序遍历右子树
        print(root.elem)

    def breath_travel(self, root):  # 层序遍历
        if root == None:
            return
        queue = []
        queue.append(root)
        while queue:
            node = queue.pop(0)
            print(node.elem)
            if node.lchild != None:
                queue.append(node.lchild)
            if node.rchild != None:
                queue.append(node.rchild)

    def createBiTree(self, root):
        data = input()
        if data == '#':  # 如果当前元素为'#'，则认为其为None
            return
        else:
            root.elem = data
            root.lchild = root.createBiTree(root)  # 构造左子树
            root.rchild = root.createBiTree(root)  # 构造右子树
        return root


root = Node()  # 创建根节点

root.createBiTree(root)  # 构造整个二叉树

# 遍历二叉树
root.PreOrder(root)  # 先序遍历
root.InOrder(root)  # 中序遍历
root.PostOrder(root)  # 后序遍历
root.breath_travel(root)  # 层序遍历

输入：

然后发现递归出错

同时遍历输入结果如下：

请问要怎么修改

Answer 1

RecursionError: maximum recursion depth exceeded while calling a Python object

这个错误是因为递归调用的层数超过了最大限制，没有合适的终止条件，因为递归函数中传递了自身节点root,导致死递归了。
创建新节点，参数应该是Node()，跟第一次创建root根节点一样的。

 
class Node(object):
    def __init__(self, data=None, lchild=None, rchild=None):
        self.elem = data  # 表示数据域
        self.lchild = lchild  # 表示左子树
        self.rchild = rchild  # 表示右子树
 
    def PreOrder(self, root):
        if root == None:
            return
        print(root.elem)
        self.PreOrder(root.lchild)  # 先序遍历左子树
        self.PreOrder(root.rchild)  # 先序遍历右子树
 
    def InOrder(self, root):
        if root == None:
            return
        self.InOrder(root.lchild)  # 中序遍历左子树
        print(root.elem)
        self.InOrder(root.rchild)  # 中序遍历右子树
 
    def PostOrder(self, root):
        if root == None:
            return
        self.PostOrder(root.lchild)  # 后序遍历左子树
        self.PostOrder(root.rchild)  # 后序遍历右子树
        print(root.elem)
 
    def breath_travel(self, root):  # 层序遍历
        if root == None:
            return
        queue = []
        queue.append(root)
        while queue:
            node = queue.pop(0)
            print(node.elem)
            if node.lchild != None:
                queue.append(node.lchild)
            if node.rchild != None:
                queue.append(node.rchild)
 
    def createBiTree(self, root):
        data = input()
        if data == '#':  # 如果当前元素为'#'，则认为其为None
            return
        else:
            root.elem = data
            root.lchild = root.createBiTree(Node())  # 构造左子树
            root.rchild = root.createBiTree(Node())  # 构造右子树
        return root
 
 
root = Node()  # 创建根节点
 
root.createBiTree(root)  # 构造整个二叉树
 
# 遍历二叉树
root.PreOrder(root)  # 先序遍历
root.InOrder(root)  # 中序遍历
root.PostOrder(root)  # 后序遍历
root.breath_travel(root)  # 层序遍历