/*二叉樹的基本操作:插入，刪除,查找,前序遍歷,中序遍歷,后序遍歷,層次遍歷*/#include<stdio.h>#include<stdlib.h>#define BLANK -1 #define LEFT -2#define RIGHT -3typedef struct BINARY_TREE{ // 左子樹 struct BINARY_TREE *left; // 右子樹 struct BINARY_TREE *right; int value;} Binary_tree;typedef struct NODE{ struct NODE *link; Binary_tree *value;} Node;// 二叉樹插入int insert(Binary_tree *root,int value,Node *node_root);// 二叉搜索樹插入int search_insert(Binary_tree *root,int value);// 二叉樹刪除 int erase(Binary_tree *roote,int value);// 二叉搜索樹查找int search_find(Binary_tree *root,int value);// 二叉樹前序遍歷void pre_print(Binary_tree *root);// 二叉樹中序遍歷void mid_print(Binary_tree *root);// 二叉樹后序遍歷void back_print(Binary_tree *root);// 層次遍歷void level_print(Binary_tree *root);// 彈出鏈表第一個元素Binary_tree* top(Node *root);// 將元素添加到鏈表末尾int append(Node *current,Binary_tree* value);int main(void){ Binary_tree *root = (Binary_tree*)malloc(sizeof(Binary_tree)); if(root == NULL) { printf("Malloc memory failed!/n"); exit(-1); } root->left = NULL; root->right = NULL; root->value = BLANK; Node *node_root = (Node*)malloc(sizeof(Node)); if(node_root == NULL) { printf("Malloc memory failed!/n"); exit(-1); } node_root->link = NULL; search_insert(root,10); search_insert(root,2); search_insert(root,2); search_insert(root,3); search_insert(root,4); search_insert(root,15); search_insert(root,6); search_find(root,15); /* insert(root,10,node_root); insert(root,2,node_root); insert(root,2,node_root); insert(root,3,node_root); insert(root,4,node_root); insert(root,15,node_root); insert(root,6,node_root); */ printf("前序遍歷: "); pre_print(root); puts(""); printf("中序遍歷: "); mid_print(root); puts(""); printf("后序遍歷: "); back_print(root); puts(""); printf("層次遍歷: "); level_print(root); puts(""); free(root); return 0;}// 二叉樹插入int insert(Binary_tree *root,int value,Node *node_root){ // 如果是空樹 if(root->left == NULL && root->right == NULL && root->value == BLANK) { root->value = value; append(node_root,root); printf("Insert %d into an empty link list!/n",value); } else { // 構(gòu)造一個新節(jié)點(diǎn) Binary_tree *new_tree_node = (Binary_tree*)malloc(sizeof(Binary_tree)); new_tree_node->value = value; new_tree_node->left = new_tree_node->right = NULL; // 得到鏈表第一個節(jié)點(diǎn)的值 Binary_tree *current = node_root->link->value; // 如果左子樹為空 if(current->left == NULL) {  current->left = new_tree_node;  append(node_root,current->left);  printf("Insert %d in parent's left node!/n",value); }  // 左子樹不為空 else {  current->right = new_tree_node;  append(node_root,current->right);  printf("Insert %d in parent's right node!/n",value);  top(node_root); } } return 0;}// 二叉搜索樹插入int search_insert(Binary_tree *root,int value){ // 如果左右子樹都為空且根節(jié)點(diǎn)值為小于0(BLANK 或者 LEFT 或者 RIGHT) if(root->left == NULL && root->right == NULL && root->value < 0) { if(root->value == BLANK)  printf("Insert %d into an empty binary tree succeed!/n",value); else if(root->value == LEFT)  printf("Insert %d into parent's left node succeed!/n",value); else  printf("Insert %d into parent's right node succeed!/n",value); root->value = value; return value; } if(value < root->value) { if(root->left == NULL) {  root->left = (Binary_tree*)malloc(sizeof(Binary_tree));  if(root->left == NULL)  {  printf("Malloc memory failed!/n");  exit(-1);  }  root->left->value = LEFT;  root->left->left = root->left->right = NULL; } search_insert(root->left,value); } else if(value > root->value) { if(root->right == NULL) {  root->right = (Binary_tree*)malloc(sizeof(Binary_tree));  if(root->right == NULL)  {  printf("Malloc memory failed!/n");  exit(-1);  }  root->right->value = RIGHT;  root->right->left = root->right->right = NULL; } search_insert(root->right,value); } else { printf("%d already exits in binary tree!/n"); return value; }}// 二叉搜索樹查找int search_find(Binary_tree *root,int value){ if(root->left == NULL && root->right == NULL && root->value < 0) { printf("Can't find %d in binary tree!/n",value); return -1; } if(root->value == value) { printf("Find %d in binary tree!/n",value); return 0; } else if(value < root->value) { if(root->left == NULL) {  printf("Can't find %d in binary tree!/n",value);  return -1; } search_find(root->left,value); }  else { if(root->right == NULL) {  printf("Can't find %d in binary tree!/n",value);  return -1; } search_find(root->right,value); } }// 二叉樹前序遍歷void pre_print(Binary_tree *root){ if(root->left == NULL && root->right == NULL && root->value < 0) return; printf("%d ",root->value); if(root->left != NULL) pre_print(root->left); if(root->right != NULL) pre_print(root->right);}// 二叉樹中序遍歷void mid_print(Binary_tree *root){ if(root->left == NULL && root->right == NULL && root->value < 0) return; if(root->left != NULL) pre_print(root->left); printf("%d ",root->value); if(root->right != NULL) pre_print(root->right);}// 二叉樹后序遍歷void back_print(Binary_tree *root){ if(root->left == NULL && root->right == NULL && root->value < 0) return; if(root->left != NULL) pre_print(root->left); if(root->right != NULL) pre_print(root->right); printf("%d ",root->value);}// 彈出鏈表第一個元素Binary_tree* top(Node *root){ if(root->link == NULL) { printf("Can't get top value from empty link list!/n"); exit(-1); } Node *current = root->link; root->link = current->link; return current->value;}// 將元素添加到鏈表末尾int append(Node *current,Binary_tree* value){ Node *new_node = (Node*)malloc(sizeof(Node)); new_node->value = value; while(current->link != NULL) { current = current->link; } current->link = new_node; new_node->link = NULL; return 0;}// 二叉樹層次遍歷void level_print(Binary_tree* root){ if(root->left == NULL && root->right == NULL && root->value < 0) return; Node *node_root = (Node*)(malloc(sizeof(Node))); node_root->link = NULL; append(node_root,root); Binary_tree* current; while(node_root->link != NULL) { current = top(node_root); printf("%d ",current->value); if(current->left != NULL)  append(node_root,current->left); if(current->right != NULL)  append(node_root,current->right); }}