二分木の代替レベルの順序トラバーサル

debugcn 投稿 Dev

Raghav patnecha

二分木のレベル順トラバーサルを実行しようとしています。しかし、トリックは通常のレベルの順序トラバーサルではなく、代わりに実行したいと思います。例えば

通常レベルの順序トラバーサル： 1 2 3 4 5

私が探しているのは、ルートを印刷するとしましょう。今、私はすべての偶数レベルについて反時計回りに行きたいと思います、そしてすべての奇数レベルについて私は時計回りに行きます：

この種のトラバーサルの場合、出力は次のようになります。 1 2 3 4 5

これは私がこれまでに試したことですが、これは私が達成しようとしているものとはわずかに異なる出力を生成します。

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


    # Function to  print level order traversal of tree
    def printLevelOrder(root):
        h = height(root)
        for i in range(1, h+1):     
           printGivenLevel(root, i)

    def printGivenLevel(root , level):
        if root is None:
           return
        if level == 1:
           print(root.val)
        elif level > 1 and level%2 == 0:
             #print("level",level)
             printGivenLevel(root.right , level-1)
             printGivenLevel(root.left , level-1)

        else:
           #print("level",level)
            printGivenLevel(root.left, level-1)
            printGivenLevel(root.right , level-1)


    def height(node):
        if node is None:
           return 0
        else :
        # Compute the height of each subtree 
           lheight = height(node.left)
           rheight = height(node.right)

           #Use the larger one
           if lheight > rheight :
              return lheight+1
           else:
              return rheight+1

# Driver code
root = Node(1)
root.left      = Node(2)
root.right     = Node(3)
root.left.left  = Node(4)
root.left.right  = Node(5)
root.right.left  = Node(6)
root.right.right  = Node(7)
root.left.left.left  = Node(8)
root.left.left.right  = Node(9)
root.right.left.left  = Node(10)
root.right.right.right  = Node(11)


print ("Level order traversal of binary tree is -")
printLevelOrder(root)

このプログラムは次の出力を生成します。

1 3 2 5 4 7 6 10 11 9 8

必要なもの：

1 2 3 7 6 5 4 8 9 10 11。

Soumen

関数printGivenLevel（）を次のように変更します

def printGivenLevel(root , levelrem, level):                                    
    if root is None:                                                            
       return                                                                   
    if levelrem == 1:                                                           
       print(root.val)                                                          
    elif level > 1 and level%2 == 0:                                            
         printGivenLevel(root.left , levelrem-1, level)    # you had root.right                      
         printGivenLevel(root.right , levelrem-1, level)   # you had root.left                       

    else:                                                                       
        printGivenLevel(root.right, levelrem-1, level)     # you had root.left                    
        printGivenLevel(root.left , levelrem-1, level)     # you had root.right

ここで、levelrem変数はリーフを印刷するタイミングを示し、levelはリーフの実際のレベルを示します。printGivenLevel（）を次のように呼び出しますprintGivenLevel(root, i, i)

また、Pythonではインデントが非常に重要です。質問で指定したコードは、そのままでは機能しません。クラスNodeにはinit（）メソッドしかないことを理解する必要があります。

この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。

侵害の場合は、連絡してください[email protected]