首页 > 代码库 > 算法9---二叉树的遍历不用栈和递归
算法9---二叉树的遍历不用栈和递归
二叉树的遍历不用栈和递归
转自：ACM之家 http://www.acmerblog.com/inorder-tree-traversal-without-recursion-and-without-stack-5988.html
我们知道，在深度搜索遍历的过程中，之所以要用递归或者是用非递归的栈方式，参考二叉树非递归中序遍历，都是因为其他的方式没法记录当前节点的parent,而如果在每个节点的结构里面加个parent 分量显然是不现实的，那么Morris是怎么解决这一问题的呢？好吧，他用得很巧妙，实际上是用叶子节点的空指针来记录当前节点的位置，然后一旦遍历到了叶子节点，发现叶子节点的右指针指向的是当前节点，那么就认为以当前节点的左子树已经遍历完成。Morris 遍历正是利用了线索二叉树 的思想。
以inorder为例，初始化当前节点为root，它的遍历规则如下：
- 如果当前节点为空，程序退出。
- 如果当前节点非空，
- 如果当前节点的左儿子为空，那么输出当前节点，当前节点重置为当前节点的右儿子。
- 如果当前节点的左儿子非空，找到当前节点左子树的最右叶子节点（此时最右节点的右儿子有两种情况，一种是指向当前节点，一种是为空,你也许感到奇怪，右节点的右儿子怎么可能非空，注意，这里的最右叶子节点只带的是原树中的最右叶子节点。），若其最右叶子节点为空，令其指向当前节点，将当前节点重置为其左儿子，若其最右节点指向当前节点，输出当前节点，将当前节点重置为当前节点的右儿子,并恢复树结构，即将最右节点的右节点再次设置为NULL
1 #include<stdio.h> 2 #include<stdlib.h> 3 4 struct tNode 5 { 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 else27 {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 =http://www.mamicode.com/ data;56 tNode->left = NULL;57 tNode->right = NULL;58 59 return(tNode);60 }61 62 /* 测试*/63 int main()64 {65 66 /* 构建树结构如下：67 168 / 69 2 370 / 71 4 572 */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 }
算法9---二叉树的遍历不用栈和递归
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。