Heim >Backend-Entwicklung >Python-Tutorial >Detaillierte Schritte zum Implementieren der Stapeldurchquerung eines Binärbaums in der richtigen Reihenfolge mit Python
使用堆栈无需递归就能遍历二叉树,下面是一个使用堆栈中序遍历二叉树的算法。
1)创建一个空栈S。
2)将当前节点初始化为root
3)将当前节点推入S并设置current=current->left直到current为NULL
4)如果current为NULL且堆栈不为空,则
a)从堆栈中弹出顶部项目。
b)输出弹出的项目,设置current=popped_item->right
c)转到步骤3)。
5)如果current为NULL并且stack为空,那么算法结束。
1
/\
2 3
/\
4 5
步骤1创建一个空堆栈:S=NULL
步骤2将current设置为root的地址:current->1
步骤3推送当前节点并设置current=current->left
直到当前为NULL
当前->1
推1:堆栈S->1
当前->2
推2:堆栈>2,1
当前->4
推4:堆栈S>4、2、1
当前=NULL
步骤4从S弹出
a)弹出4:堆栈S->2,1
b)打印“4”
c)current=NULL/*right of 4*/并转到步骤3
由于current is NULL step 3没有做任何事情。
步骤4再次弹出。
a)弹出2:堆栈S->1
b)打印“2”
c)current->;5/*right of 2*/并转到步骤3
第3步将5推入堆栈并使当前为NULL
堆栈S->5,1
当前=NULL
步骤4从S弹出
a)弹出5:堆栈S->1
b)打印“5”
c)current=NULL/*right of 5*/并转到步骤3
由于current is NULL step 3没有做任何事情
步骤4再次弹出。
a)弹出1:堆栈S->NULL
b)打印“1”
c)当前->3/*1的右边*/
第3步将3推入堆栈并使当前为NULL
堆栈S->3
当前=NULL
步骤4从S弹出
a)弹出3:堆栈S->NULL
b)打印“3”
c)current=NULL/*3的右边*/
由于堆栈S为空且当前为NULL,因此遍历已完成。
class Node: def __init__(self,data): self.data=data self.left=None self.right=None def inOrder(root): current=root stack=[] while True: if current is not None: stack.append(current) current=current.left elif(stack): current=stack.pop() print(current.data,end="") current=current.right else: break print() root=Node(1) root.left=Node(2) root.right=Node(3) root.left.left=Node(4) root.left.right=Node(5) inOrder(root)
Das obige ist der detaillierte Inhalt vonDetaillierte Schritte zum Implementieren der Stapeldurchquerung eines Binärbaums in der richtigen Reihenfolge mit Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!