ホームページ > バックエンド開発 > Python チュートリアル > Python を使用してバイナリ ツリーのスタック順トラバーサルを実装する詳細な手順

Python を使用してバイナリ ツリーのスタック順トラバーサルを実装する詳細な手順

WBOY
リリース: 2024-01-23 21:51:05
転載
678 人が閲覧しました

使用堆栈中序遍历二叉树详细步骤 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,因此遍历已完成。

Python实现堆栈中序遍历二叉树

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)
ログイン後にコピー

以上がPython を使用してバイナリ ツリーのスタック順トラバーサルを実装する詳細な手順の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

関連ラベル:
ソース:163.com
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート