预购Python中的树形遍历

Question

我试图写一个函数，它接受一个节点作为参数，并返回该二叉树的PreOrder遍历的字符串。

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

root = Node(1)
root.left = Node(2)
root.left.right = Node(4)
root.left.left = Node(5)
root.right = Node(3) 

def PreOrder(node): 

    path = ''

    if node:
        #print(node.value)
        path += (str(node.value) + "_")
        PreOrder(node.left)
        PreOrder(node.right)

    return path

print(PreOrder(root))

输出。1_

谢谢 :)

Answer 1

我认为你需要在路径中添加PreOrder(node.left)和PreOrder(node.right)。

因此，代码看起来会是这样的。

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

#                   1
#               2       3
#           5       4

def PreOrder(node): 

    path = ''

    if node:
        path += (str(node.value) + "_")
        path += PreOrder(node.left) 
        path += PreOrder(node.right)

    return path

print(PreOrder(root))

# prints 1_2_5_ 4_  3_

Answer 2

检查这个链接. 这是一个参考链接，从这里你可以看到更多的遍历技术。我在下面提供了Pre-Order遍历的代码。检查这个参考，并比较你的代码与你需要纠正的地方。

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data
# Insert Node
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the Tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Preorder traversal
# Root -> Left ->Right
    def PreorderTraversal(self, root):
        res = []
        if root:
            res.append(root.data)
            res = res + self.PreorderTraversal(root.left)
            res = res + self.PreorderTraversal(root.right)
        return res

root = Node(1)
root.insert(2)
root.insert(3)
root.insert(4)
root.insert(5)
print(root.PreorderTraversal(root))