Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings
This repository was archived by the owner on Sep 7, 2025. It is now read-only.
/pythonPublic archive

Commit8aae483

Browse files
zigzag traversal in a binary tree
The idea is to use two stacks. We can use one stack for printing from left to right and other stack for printing from right to left. In every iteration, we have nodes of one level in one of the stacks. We print the nodes, and push nodes of next level in other stack.
1 parent712b0df commit8aae483

File tree

1 file changed

+75
-0
lines changed

1 file changed

+75
-0
lines changed
Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
classNode:
2+
"""
3+
A Node has data variable and pointers to its left and right nodes.
4+
"""
5+
6+
def__init__(self,data):
7+
self.left=None
8+
self.right=None
9+
self.data=data
10+
11+
defmake_tree()->Node:
12+
root=Node(1)
13+
root.left=Node(2)
14+
root.right=Node(3)
15+
root.left.left=Node(4)
16+
root.left.right=Node(5)
17+
returnroot
18+
19+
defzigzag_iterative(root:Node):
20+
"""
21+
ZigZag traverse by iterative method: Print node left to right and right to left, alternatively.
22+
"""
23+
ifroot==None:
24+
return
25+
26+
# two stacks to store alternate levels
27+
s1= []# For levels to be printed from right to left
28+
s2= []# For levels to be printed from left to right
29+
30+
# append first level to first stack 's1'
31+
s1.append(root)
32+
33+
# Keep printing while any of the stacks has some nodes
34+
whilenotlen(s1)==0ornotlen(s2)==0:
35+
36+
# Print nodes of current level from s1 and append nodes of next level to s2
37+
whilenotlen(s1)==0:
38+
temp=s1[-1]
39+
s1.pop()
40+
print(temp.data,end=" ")
41+
42+
# Note that is left is appended before right
43+
iftemp.left:
44+
s2.append(temp.left)
45+
iftemp.right:
46+
s2.append(temp.right)
47+
48+
# Print nodes of current level from s2 and append nodes of next level to s1
49+
whilenotlen(s2)==0:
50+
temp=s2[-1]
51+
s2.pop()
52+
print(temp.data,end=" ")
53+
54+
# Note that is rightt is appended before left
55+
iftemp.right:
56+
s1.append(temp.right)
57+
iftemp.left:
58+
s1.append(temp.left)
59+
60+
defmain():# Main function for testing.
61+
"""
62+
Create binary tree.
63+
"""
64+
root=make_tree()
65+
print("\nZigzag order traversal(iterative) is: ")
66+
zigzag_iterative(root)
67+
print()
68+
69+
70+
if__name__=="__main__":
71+
importdoctest
72+
73+
doctest.testmod()
74+
main()
75+

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp