데이터 구조 기초 지식의 두 갈래 찾기 트 리

오랫동안 글 을 쓰 지 않 아 익숙 했 던 기초 지식 이 모호 해 지 는 것 을 느 꼈 습 니 다. 오늘부터 기본 지식 을 정리 하고 당신 과 함께 격려 하 는 것 을 증거 로 삼 겠 습 니 다.
이 진 트 리 찾기: 모든 노드 가 조건 을 만족 시 키 고 노드 의 key 값 은 모든 왼쪽 트 리 노드 의 key 값 보다 크 며 모든 오른쪽 트 리 노드 의 key 값 보다 작 습 니 다.
삽입: 현재 노드 p - > key, 삽입 할 key 값 과 비교, p - > key < key, 우회전;그렇지 않 으 면 좌회전.
삭제: 노드 x 를 삭제 하면 x 에 아이 가 없 으 면 바로 삭제 합 니 다.만약 x 에 아이 가 하나 밖 에 없다 면 x 의 아버 지 는 x 의 아 이 를 가리 키 고 x 를 삭제 합 니 다.만약 에 x 에 두 명의 아이 가 있다 면 x 의 중간 순서 후계 y 를 찾 으 면 y 는 반드시 한 명의 아이 만 있 을 것 이다. y 값 을 x 에 부여 하고 마지막 에 y 를 삭제 할 것 이다.

  1 #include <stdio.h>

  2 #include <math.h>

  3 #include <queue>

  4 typedef struct node

  5 {

  6     int key;

  7     struct node *left;

  8     struct node *right;

  9 }treeNode;

 10 

 11 //tree    

 12 treeNode* minimum(treeNode *x)

 13 {

 14     while(x->left)

 15         x = x->left;

 16     return x;

 17 }

 18 

 19 //tree    

 20 treeNode* maximum(treeNode *x)

 21 {

 22     while(x->right)

 23         x = x->right;

 24     return x;

 25 }

 26 //  x    

 27 //1.x    ，        

 28 //2.x     ，   x     y,   y      x   

 29 treeNode* tree_successor(treeNode *root, int value)

 30 {

 31     treeNode *p = root;

 32     treeNode *parent = NULL;

 33     while (p && p->key!=value)

 34     {

 35         if(p->key < value)

 36             p = p->right;

 37         else

 38         {

 39             parent = p;

 40             p = p->left;

 41         }

 42     }

 43     //    value 

 44     if (p == NULL)

 45     {

 46         return NULL;

 47     }

 48     if (p->right != NULL)

 49     {

 50         return minimum(p->right);

 51     }

 52     //  parent NULL，  x       

 53     return parent;

 54 

 55 }

 56 

 57 treeNode* insert(treeNode *root, int value)

 58 {

 59     treeNode *newNode = new node;

 60     newNode->key = value;

 61     newNode->left = NULL;

 62     newNode->right = NULL;

 63     if(root == NULL)

 64     {

 65         return newNode;

 66     }

 67     treeNode *cur = root;

 68     treeNode *p;

 69     while(cur != NULL)

 70     {

 71         p = cur;

 72         if(cur->key < value)

 73             cur = cur->right;

 74         else cur = cur->left;

 75     }

 76     if(p->key < value)

 77         p->right = newNode;

 78     else p->left = newNode;

 79 

 80     return root;

 81 }

 82 //    x

 83 //x    ，     

 84 //x      ，x     x   

 85 //x     ，x     y, y         x.key <- y.key    y

 86 void erase(treeNode *root, int value)

 87 {

 88     treeNode *x = root;

 89     treeNode *parent = root;

 90     while(x != NULL)

 91     {

 92         parent = x;

 93         if(x->key < value)

 94             x = x->right;

 95         else if (x->key > value)

 96             x = x->left;

 97         else break;

 98     }

 99     //    value 

100     if(x == NULL)

101         return;

102     treeNode *child;

103     child = (x->left == NULL) ? x->right : x->left;

104     //            

105     if(x->left==NULL || x->right==NULL)

106     {

107         if (parent->left == x)

108             parent->left = child;

109         else parent->right = child;

110         delete x;

111         return;

112     }

113     //x     

114     parent = x;

115     treeNode *y = x->right;

116     while(y->left)

117     {

118         parent = y;

119         y = y->left;

120     }

121     x->key = y->key;

122     //  y

123     if(parent->left == y)

124         parent->left = y->right;

125     else

126         parent->right = y->right;

127     delete y;

128 }

129 

130 void midOrder(treeNode *root)

131 {

132     if(root != NULL)

133     {

134         midOrder(root->left);

135         printf("%d ", root->key);

136         midOrder(root->right);

137     }

138 }

139 

140 void preOrder(treeNode *root)

141 {

142     if(root != NULL)

143     {

144         printf("%d ", root->key);

145         preOrder(root->left);

146         preOrder(root->right);

147     }

148 }

149 

150 int depth(treeNode *root)

151 {

152     if(root == NULL) return 0;

153     

154     int left = depth(root->left);

155     int right = depth(root->right);

156     return ((left > right) ? left+1 : right+1);

157     

158 }    

159 

160 int main()

161 {

162     printf("           -1    
");

163     int a, h;

164     treeNode *root = NULL;

165     while(scanf("%d", &a), a != -1)

166     {

167         root = insert(root, a);

168     }

169     printf("    
");

170     midOrder(root);

171     printf("
    
");

172     preOrder(root);

173     printf("
      key 
");

174     scanf("%d", &a);

175     erase(root, a);

176     printf("    
");

177     midOrder(root);

178     printf("
    
");

179     preOrder(root);

180 

181     system("pause");

182     return 0;

183 }