二叉树一次向左异或右移一个节点

Question

我想根据用户输入“遍历”二叉树。例如，如果回答否，则将一个节点向下移动到左侧。如果是，将一个节点向右下移。有点像 20 题游戏

class Node:
    
    def __init__(self, data):
        
        self.left = None
        self.right = None
        self.data = data
  
        
    def insert(self, data):
        
        #compare if left none insert, otherwiese rigt 
       # Compare the new value with the parent node
        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()

如何移动

def move(text):
    if text == 'y':
        print('move right')

    else:
        print('move left')
       
        
def menu(choices):
    ans = 'NONE'
   
    for i in theNodes:
        text = input("Please select y xor n: ")
        move(text)
        ans = i
        print(ans)
        
        
        if ans in endNode:
            break
        
            
print('You position ' + ans)

theNodes = ['A','B','C','D','E' ,'F', 'G']
endNode = 'EDFG'

如何在树结构中一次移动一个节点？

Answer 1

我们以20题游戏为例

在 20 题游戏中，您需要根据用户输入遍历您的二叉树，并始终牢记您在任何给定时刻在树中的位置。

要实现这一点，您需要一个可以记住您在树中的当前位置的数据结构。

你可以像这样实现这个数据结构：

class TreeCursor:
    node = None

    def __init__(self, root):
        self.node = root
    
    def move_left(self):
        self.node = self.node.left

    def move_right(self):
        self.node = self.node.right

使用该数据结构，您可以像这样实现树遍历：

N_QUESTIONS = 20 # number of questions you want to ask

def traverse_tree(tree_cursor):
    for i_question in range(N_QUESTIONS):
        text = input("Please select y xor n: ")
        if text == 'y':
            tree_cursor.move_right()
        elif text == 'n':
            tree_cursor.move_left()

现在假设您已经创建了一个二叉树并且您想要遍历它。让我们创建一个二叉树并遍历它。

您可以这样做。以下是创建树的方法：

tree = Node('A')
tree.left = Node('B')
tree.right = Node('C')

以下是遍历我们在上一步中创建的树的方法：

tree_cursor = TreeCursor(tree)
traverse_tree(tree_cursor)

二叉树一次向左异或右移一个节点

Binary Tree move left XOR right exactly one node at a time

python

binary-tree