网站目录是什么,wordpress显示文章阅读数,网站服务器崩溃怎么办,学编程的步骤二叉树的遍历不用栈和递归 转自#xff1a;ACM之家 http://www.acmerblog.com/inorder-tree-traversal-without-recursion-and-without-stack-5988.html我们知道#xff0c;在深度搜索遍历的过程中#xff0c;之所以要用递归或者是用非递归的栈方式#xff0c;参考二叉树非…二叉树的遍历不用栈和递归 转自ACM之家 http://www.acmerblog.com/inorder-tree-traversal-without-recursion-and-without-stack-5988.html 我们知道在深度搜索遍历的过程中之所以要用递归或者是用非递归的栈方式参考二叉树非递归中序遍历都是因为其他的方式没法记录当前节点的parent,而如果在每个节点的结构里面加个parent 分量显然是不现实的那么Morris是怎么解决这一问题的呢好吧他用得很巧妙实际上是用叶子节点的空指针来记录当前节点的位置然后一旦遍历到了叶子节点发现叶子节点的右指针指向的是当前节点那么就认为以当前节点的左子树已经遍历完成。Morris 遍历正是利用了线索二叉树 的思想。 以inorder为例初始化当前节点为root它的遍历规则如下 - 如果当前节点为空程序退出。 - 如果当前节点非空 - 如果当前节点的左儿子为空那么输出当前节点当前节点重置为当前节点的右儿子。 - 如果当前节点的左儿子非空找到当前节点左子树的最右叶子节点此时最右节点的右儿子有两种情况一种是指向当前节点一种是为空,你也许感到奇怪右节点的右儿子怎么可能非空注意这里的最右叶子节点只带的是原树中的最右叶子节点。若其最右叶子节点为空令其指向当前节点将当前节点重置为其左儿子若其最右节点指向当前节点输出当前节点将当前节点重置为当前节点的右儿子,并恢复树结构即将最右节点的右节点再次设置为NULL 1 #includestdio.h2 #includestdlib.h3 4 struct tNode5 {6 int data;7 struct tNode* left;8 struct tNode* right;9 };
10
11 void MorrisTraversal(struct tNode *root)
12 {
13 struct tNode *current,*pre;
14
15 if(root NULL)
16 return;
17
18 current root;
19 while(current ! NULL)
20 {
21 if(current-left NULL)
22 {
23 printf( %d , current-data);
24 current current-right;
25 }
26 else
27 {
28 /* 找到current的前驱节点 */
29 pre current-left;
30 while(pre-right ! NULL pre-right ! current)
31 pre pre-right;
32
33 /* 将current节点作为其前驱节点的右孩子 */
34 if(pre-right NULL)
35 {
36 pre-right current;
37 current current-left;
38 }
39
40 /* 恢复树的原有结构更改right 指针 */
41 else
42 {
43 pre-right NULL;
44 printf( %d ,current-data);
45 current current-right;
46 } /* End of if condition pre-right NULL */
47 } /* End of if condition current-left NULL*/
48 } /* End of while */
49 }
50
51 struct tNode* newtNode(int data)
52 {
53 struct tNode* tNode (struct tNode*)
54 malloc(sizeof(struct tNode));
55 tNode-data data;
56 tNode-left NULL;
57 tNode-right NULL;
58
59 return(tNode);
60 }
61
62 /* 测试*/
63 int main()
64 {
65
66 /* 构建树结构如下
67 1
68 / \
69 2 3
70 / \
71 4 5
72 */
73 struct tNode *root newtNode(1);
74 root-left newtNode(2);
75 root-right newtNode(3);
76 root-left-left newtNode(4);
77 root-left-right newtNode(5);
78
79 MorrisTraversal(root);
80 return 0;
81 } 转载于:https://www.cnblogs.com/tao-alex/p/5894348.html
