# C语言实现二叉树-02版

---恢复内容开始---

Problem

#include <stdio.h>#include <stdlib.h>typedef struct _node {int data;struct _node *link[2];}Node;typedef struct _tree{struct _node *root;}Tree;Tree * init_tree(){Tree *temp = (Tree*)malloc(sizeof(Tree));temp->root = NULL;return temp;}

int insert(Tree *tree, int data){ if(tree->root == NULL){ //TODO }else{ //TODO } return 1;}

int insert(Tree *tree, int data){ if(tree->root == NULL){ tree->root = make_node(data); }else{ //TODO } return 1;}

int insert(Tree *tree, int data){if(tree->root == NULL){tree->root = make_node(data);}else{Node * it = tree->root;for(;;){//TODO}} return 1;}

ok那么我们继续分析；

int insert(Tree *tree, int data){if(tree->root == NULL){tree->root = make_node(data);}else{Node * it = tree->root;int dir;for(;;){dir = it->data < data;if(it->data == data){return 0;}else if(it->link[dir] == NULL){break;}it = it->link[dir];}//TODO} return 1;}

6<8显然，成立；

dir = it->data < data;

if(it->data < data){ dir = 1;}else{ dir = 0;}

if(it->data == data){ return 0; }else if(it->link[dir] == NULL){ break; }

take break可能更加是人类需要的；

int insert(Tree *tree, int data){if(tree->root == NULL){tree->root = make_node(data);}else{Node * it = tree->root;int dir ;for(;;){dir = it->data < data;if(it->data == data){return 0;}else if(it->link[dir] == NULL){break;}it = it->link[dir];}//TODO}return 1;}

( ⊙ o ⊙ )！怎么还有一个TODO啊！你会惊讶到我们不是已经找到啦目标啦吗；

int insert(Tree *tree, int data){if(tree->root == NULL){tree->root = make_node(data);}else{Node * it = tree->root;int dir ;for(;;){dir = it->data < data;if(it->data == data){return 0;}else if(it->link[dir] == NULL){break;}it = it->link[dir];}it->link[dir] = make_node(data);}return 1;}

#include <stdio.h>#include <stdlib.h>typedef struct _node {int data;struct _node *link[2];}Node;typedef struct _tree{struct _node *root;}Tree;Tree * init_tree(){Tree *temp = (Tree*)malloc(sizeof(Tree));temp->root = NULL;return temp;}Node * make_node(int data){Node *temp = (Node*)malloc(sizeof(Node));temp->link[0] = temp->link[1] = NULL;temp->data = data;return temp;}int insert(Tree *tree, int data){if(tree->root == NULL){tree->root = make_node(data);}else{Node * it = tree->root;int dir ;for(;;){dir = it->data < data;if(it->data == data){return 0;}else if(it->link[dir] == NULL){break;} it = it->link[dir];} it->link[dir] = make_node(data);} return 1;}void print_inorder_recursive(Node *root){if(root){print_inorder_recursive(root->link[0]);printf("data:%d/n",root->data);print_inorder_recursive(root->link[1]);}return ;}void print_inorder(Tree *tree){print_inorder_recursive(tree->root);return ;}int main(void){Tree * tree = init_tree();insert(tree,6);insert(tree,7);insert(tree,5);insert(tree,8);print_inorder(tree);return 0;}

Problem

Solution

int remove(Tree *tree, int data){if(tree->root != NULL){//TODO}return 1;}

int remove(Tree *tree, int data){if(tree->root != NULL){Node *p = NULL;Node *succ;Node *it = tree->root;int dir;for(;;){//TODO}}return 1;}

p其实是parent（父亲）的缩写，succ是successor（继承者）的缩写；

int remove(Tree *tree, int data){if(tree->root != NULL){Node *p = NULL;Node *succ;Node *it = tree->root;int dir;for(;;){if( it == NULL){return 0;}else if(it->data == data){break;}dir = it->data < data;p = it;it = it->link[dir];}}return 1;}

p=it就是说p指向7；

int remove(Tree *tree, int data){if(tree->root != NULL){Node *p = NULL;Node *succ;Node *it = tree->root;int dir;for(;;){if( it == NULL){return 0;}else if(it->data == data){break;}dir = it->data < data;p = it;it = it->link[dir];}/***********************************************************************/if(it->link[0] != NULL && it->link[1] != NULL){//TODO}else{//TODO}}return 1;}

it->data = succ->data;

int remove(Tree *tree, int data){if(tree->root != NULL){Node *p = NULL;Node *succ;Node *it = tree->root;int dir;for(;;){if( it == NULL){return 0;}else if(it->data == data){break;}dir = it->data < data;p = it;it = it->link[dir];}/***********************************************************************/if(it->link[0] != NULL && it->link[1] != NULL){p = it;succ = it->link[1];while(succ->link[0] != NULL){p = succ;succ = succ->link[0];}it->data = succ->data;p->link[p->link[1] == succ] = succ->link[1];free(succ);/***********************************************************************/}else{//TODO}}return 1;}

Node *p = NULL;Node *succ;Node *it = tree->root;

it就是根的右子树；