-
Notifications
You must be signed in to change notification settings - Fork 0
/
7.05morristree.cpp
102 lines (100 loc) · 2.1 KB
/
7.05morristree.cpp
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <stdio.h>
using namespace std;
struct bst_node
{
int key;
bst_node *left;
bst_node *right;
};
void bst_morris_inorder_middle(struct bst_node *root)
{
struct bst_node *p = root,*tmp;
while(p)
{
if(p->left == NULL)//if has no left node,output and turn to the right node
{
printf("%d\n", p->key);
p = p->right;
}
else//has the left node
{
tmp = p->left;
while(tmp->right!=NULL && tmp->right!=p)//turn to the left node's rightest node
tmp = tmp->right;
if(tmp->right == NULL)//if the rightest node's right is NULL,make it point to p.And turn to p's left
//In this way,when p's left scan over,it can turn back to p
{
tmp->right = p;
p = p->left;
}
else//it mines the rightest node's right is point to p,it mines p's left have been scan then come back to p
{ //so we should output p and make the rightest node to be NULL,and turn to p's right,say goodbye to the left tree
printf("%d\n", p->key);
tmp->right = NULL;
p = p->right;
}
}
}
}
void bst_morris_inorder_first(struct bst_node *root)
{
struct bst_node *p = root,*tmp;
while(p)
{
printf("%d\n", p->key);
if(p->left == NULL)
p = p->right;
else
{
tmp = p->left;
while(tmp->right!=NULL&tmp->right!=p)
tmp=tmp->right;
if(tmp->right == NULL)
{
tmp->right = p->right;
p = p->left;
}
else
{
tmp->right == NULL;
p = p->right;
}
}
}
}
//if want to use morris tree to do the last scan,the noleaf node should point to the right tree
//so,is that possible??????????????????
// void bst_morris_inorder_last(struct bst_node *root)
// {
// struct bst_node *p = root,*tmp;
// while(p)
// {
// if(p->left == NULL)
// {
// tmp = p->right;
// while(tmp->right!=NULL&&tmp->right!=p)
// tmp = tmp->right;
// p =
// }
// }
// }
int main()
{
bst_node t[9];
for(int i=0;i<9;i++)
{
t[i].key = i;
t[i].left = NULL;
t[i].right = NULL;
}
t[0].left = &t[1];
t[0].right = &t[2];
t[1].left = &t[3];
t[1].right = &t[4];
t[2].right = &t[5];
t[4].left = &t[6];
t[4].right = &t[7];
t[5].left = &t[8];
bst_morris_inorder_middle(t);
return 0;
}