数据结构之二叉树遍历--非递归实现

一.前序遍历:前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。递归实现：//递归实现前序遍历...





一. 前序遍历:

前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。

    递归实现：

1. //递归实现前序遍历
2. void pre_order_traversal(BTreeNode* root)
3. {
4.     if(NULL != root)
5.     {
6.         printf("%c, ", ((Node*)root)->v);
8.         pre_order_traversal(root->left);
9.         pre_order_traversal(root->right);
10.     }
11. }

非递归实现：

       根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。

1. //非递归实现前序遍历
2. void pre_orther_traversal(BTreeNode* root)
3. {
4.     /*
5.     对于任一结点P：
7.      1)访问结点P，并将结点P入栈;
9.      2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，
10.        并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的
11.        左孩子置为当前的结点P;
13.      3)直到P为NULL并且栈为空，则遍历结束。
14.     */
15.     LinkStack* stack = LinkStack_Create();
17.     BTreeNode* p = root;
19.     while((NULL != p) || (!LinkStack_Empty(stack)))
20.     {
21.         while(NULL != p)
22.         {
23.             printf("%c, ", ((Node*)p)->v);
25.             LinkStack_Push(stack, p);
27.             p = p->left;
28.         }
30.         if(!LinkStack_Empty(stack))
31.         {
32.             p = LinkStack_Top(stack);
34.             LinkStack_Pop(stack);
36.             p = p->right;
37.         }
38.     }
40.     LinkStack_Destroy(stack);
41. }

二. 中序遍历:

中序遍历按照“左孩子-根结点-右孩子”的顺序进行访问。

    递归实现：

1. //递归实现中序遍历
2. void middle_order_traversal(BTreeNode* root)
3. {
4.     if(NULL != root)
5.     {
6.         middle_order_traversal(root->left);
8.         printf("%c, ", ((Node*)root)->v);
10.         middle_order_traversal(root->right);
11.     }
12. }

非递归实现：

       根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。

1. //非递归实现中序遍历
2. void middle_orther_traversal(BTreeNode* root)
3. {
4.     /*
5.     对于任一结点P，
7.   1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
9.   2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
11.   3)直到P为NULL并且栈为空则遍历结束
13.     */
14.     LinkStack* stack = LinkStack_Create();
16.     BTreeNode* p = root;
18.     while((NULL != p) || (!LinkStack_Empty(stack)))
19.     {
20.         while(NULL != p)
21.         {
24.             LinkStack_Push(stack, p);
26.             p = p->left;
27.         }
29.         if(!LinkStack_Empty(stack))
30.         {
31.             p = LinkStack_Top(stack);
33.             printf("%c, ", ((Node*)p)->v);
35.             LinkStack_Pop(stack);
37.             p = p->right;
38.         }
39.     }
41.     LinkStack_Destroy(stack);
42. }

三. 后序遍历

后序遍历按照“左孩子-右孩子-根结点”的顺序进行访问。

    递归实现：

1. //递归实现后序遍历
2. void post_order_traversal(BTreeNode* root)
3. {
4.     if(NULL != root)
5.     {
6.         post_order_traversal(root->left);
7.         post_order_traversal(root->right);
9.         printf("%c, ", ((Node*)root)->v);
10.     }
11. }

    非递归实现：

1. //非递归实现后序遍历
2. void post_orther_traversal(BTreeNode* root)
3. {
4.     /*
5.     要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。
6.              如果P不存在左孩子和右孩子，则可以直接访问它；
7.              或者P存在左孩子或者右孩子，
8.              但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。
9.     若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，
10.     左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
11.     */
12.     LinkStack* stack = LinkStack_Create();
14.     BTreeNode* cur ;//当前结点
15.     BTreeNode* pre = NULL;//前一次访问的结点
17.     LinkStack_Push(stack, root);
19.     while(!LinkStack_Empty(stack))
20.     {
21.         //如果当前结点没有孩子结点或者孩子节点都已被访问过
22.         cur = (BTreeNode*)LinkStack_Top(stack);
24.         if(((NULL==cur->left)&&(NULL==cur->right)) ||
25.           (
26.             (NULL!=pre) && ((pre==cur->left) || (pre==cur->right))  ))
27.           {
28.                 printf("%c, ", ((Node*)cur)->v);
30.                 LinkStack_Pop(stack);
32.                 pre = cur;
33.         }
34.         else
35.         {
36.             if(NULL != cur->right)
37.             {
38.                 LinkStack_Push(stack, cur->right);
39.             }
40.             if(NULL != cur->left)
41.             {
42.                 LinkStack_Push(stack, cur->left);
43.             }
44.         }
45.     }
47.     LinkStack_Destroy(stack);
48. }

长按二维码,选择“识别图中二维码”进行关注

▲长按二维码“识别.”关注

    关注 PC国度