Traverse binary trees

Algorithms 3rd Edition Learning note

Rooted trees with left child right sibling representation

n叉树的递归遍历： python实现

该树使用LCRS表示

即每个节点包括一个左节点和一个邻居节点

class Node:
    def __init__(self, data):
        self.val = data 
        self.left = None
        self.right = None



def rightSibling(root):
    list = []        
    while root is not None:
        list += [root.val]      
        if root.left is not None:
            list += rightSibling(root.left)
        root = root.right
    return list

root = Node(1)
root.left = Node(2)
root.left.right = Node(3)
root.left.right.right = Node(4)
root.left.right.left = Node(5)
root.left.right.left.right = Node(6)
list = rightSibling(root)
print(list)

时间复杂度O(n)

打印结果：

[1, 2, 3, 5, 6, 4]