二元樹走訪 by iteration

Posted on | In |  
Symbols : 842 字

binary tree iterative traversal

1.postorder

參考 這篇

解法1

需要用到2個 pointer : nowNode 和 preNode
且可以依照他們的關係去分為下面2種情況

  1. traverse down : preNode 是 nowNode 的 parent

    • 繼續往下走 : nowNode 的 left child 、 right child 、 visit nowNode

  2. traverse up : nowNode 是 preNode 的 parent

    • 如果 preNode 是 nowNode 的 left child : traverse right child
    • 如果 preNode 是 nowNode 的 right child : visit nowNode

code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
void postorderIterative(void) const
{
	pNode nowNode, preNode = nullptr;
	stack<pNode> nstack;
	
	if (root == nullptr)
		return;
	
	nstack.push(root);
	
	while (!nstack.empty())
	{
		nowNode = nstack.top();
		//traverse down
		if (preNode == nullptr || preNode->left == nowNode || preNode->right == nowNode) //註1
		{
			if (nowNode->left)
				nstack.push(nowNode->left);
			else if (nowNode->right)
				nstack.push(nowNode->right);
			else
			{
				cout << nowNode->data << " ";
				nstack.pop();
			}
		}
		//traverse up
		else if (nowNode->left == preNode)
		{
			if (nowNode->right)
				nstack.push(nowNode->right);
			else
			{
				cout << nowNode->data << " ";
				nstack.pop();
			}
		}
		//traverse up
		else if (nowNode->right == preNode)
		{
			cout << nowNode->data << " ";
			nstack.pop();
		}
	
		preNode = nowNode;
	}
}

注意這邊的if (preNode == nullptr || preNode->left == nowNode || preNode->right == nowNode)
因為最一開始 nowNode=root 、 preNode=nullptr
所以為了避免存取到 nullptr，使用 preNode == nullptr 判斷
這裡利用到了 Logic OR “||” 的特性
只要前面是 true ，後面就不用判斷了

refactored code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void postorderIterative(void) const
{
	pNode nowNode, preNode = nullptr;
	stack<pNode> nstack;
	
	if (root == nullptr)
		return;
	
	nstack.push(root);
	
	while (!nstack.empty())
	{
		nowNode = nstack.top();
	
		if (preNode == nullptr || preNode->left == nowNode || preNode->right == nowNode)
		{
			if (nowNode->left)
				nstack.push(nowNode->left);
			else if (nowNode->right)
				nstack.push(nowNode->right);
		}
		else if (nowNode->left == preNode)
		{
			if (nowNode->right)
				nstack.push(nowNode->right);
		}
		else
		{
			cout << nowNode->data << " ";
			nstack.pop();
		}
	
		preNode = nowNode;
	}
}

另外這邊是先 push left 再 push right
和下面 two stack 版本 與 preorder 不一樣
因為這邊是合在一起的 if-else 條件判斷
因此一次只能選擇往左（push left) 或往右（push right)
下面 preorder traversal 是2個獨立的 if 判斷式
所以2個都有可能會push進去
因此要先判斷後面順序的那一個
==>preoeder 是 VLR 所以要先判斷R再L

解法2

利用2個 stack
使用 VRL (換順序的preorder(VLR)) 輸出到 output stack
再從 output stack 輸出，就變 LRV 了
code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void postorderTwoStack(void) const
{
	pNode nowNode;
	stack<pNode> nstack;
	stack<pNode> output;
	
	nstack.push(root);
	
	// VRL
	while (!nstack.empty())
	{
		nowNode = nstack.top();
	
		output.push(nowNode);
	
		nstack.pop();
	
		//first in last out
		if (nowNode->left)
			nstack.push(nowNode->left);
	
		//所以right會先出
		if (nowNode->right)
			nstack.push(nowNode->right);
	}
	
	// LRV
	while (!output.empty())
	{
		nowNode = output.top();
		output.pop();
	
		cout << nowNode->data << " ";
	}
}

2.preorder

這是iterative版本，手繪筆記區的筆記是 iterator class的版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void preorderIterative(void) const
{
	pNode nowNode;
	stack<pNode> nstack;
	
	nstack.push(root);
	
	while (!nstack.empty())
	{
		nowNode = nstack.top();
	
		cout << nowNode->data << " ";
	
		nstack.pop();
	
		if (nowNode->right)
			nstack.push(nowNode->right);
	
		if (nowNode->left)
			nstack.push(nowNode->left);
	}
}

注意 preorder 的順序是VLR
但 stac k是 first in last out
所以要先 push right 再 push left
這樣 pop 時才會是 left 先出來

3.inorder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void inorderIterative(void) const
{
	if(!root)
		return;

	pNode nowNode;
	stack<pNode> nstack;
	
	nowNode = root;
	
	while (true)
	{
		while (nowNode)
		{
			nstack.push(nowNode);
			nowNode = nowNode->left;
		}
	
		if (nstack.empty())
			break;
	
		nowNode = nstack.top();
		cout << nowNode->data << " ";
		nstack.pop();
		
		nowNode = nowNode->right;
	}
}

4.level order

利用 Queue 來實作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void levelorder(void) const
{
	if (!root)
		return;

	std::queue<pNode> que;
	pNode now_node;

	que.push(root);
	
	while (!que.empty())
	{
		now_node = que.front();
		que.pop();

		std::cout << std::setw(4) << std::left << now_node->data;

		if (now_node->left)
			que.push(now_node->left);

		if (now_node->right)
			que.push(now_node->right);
	}
}
0%