內容理解
參考:https://blog.csdn.net/u013834525/article/details/80506126
二叉樹的增刪改查node
其餘都簡單就是刪除比較麻煩web
分三種狀況考慮
1.沒有子節點的狀況
2.有1個子節點
3.有兩個子節點
主要就是有兩個子節點狀況代碼步驟
a.當刪除節點是 頭節點的時候
============1.先用一個變量暫存遍歷到頭節點右邊的最左邊的節點
============2.將頭節點的左邊所有移到剛纔查找的變量的左邊
-===========3.再將頭節點變爲原來頭結點的右邊起始節點
b.當刪除的節點不是頭的話
============1.先判斷是在父親節點的左邊仍是右邊
============2.將要刪除的節點遍歷到右邊的最左邊
============3.將要刪除節點的左邊所有移動到要剛剛遍歷的最左邊
============4.在將剛剛判斷過的在父親節點的左邊仍是右邊將父節點和要刪除節點右邊起始節點相鏈接svg
刪除頭節點
刪除後
刪除中間
刪除後
.net
代碼code
#include <stdio.h> #include <stdlib.h> typedef struct tree{ int data; struct tree *left; struct tree *right; }Tree; //查找節點而且同時記錄節點的數值和父親節點的數值 Tree * find_node; Tree * parent_node; void find_tree(Tree *root,int data){ if(root != NULL){ //若是找到節點則返回 if(root->data == data){ find_node=root; parent_node=NULL; return ; }else if(root->data > data){//沒找到則根據大小進行便利而且同時記錄上節點的父親節點 parent_node = root; find_tree(root->left,data); }else{ parent_node=root ; find_tree(root->right,data); } } } //destory tree void destory_tree(Tree *root){ if(root){ destory_tree(root->left); destory_tree(root->right); free(root); } } //刪除節點 void delete_tree(Tree **root,int data){ Tree *temp_node; //找到要刪除的節點以及父親節點 find_tree(*root,data); //分三種種狀況討論 //第一種狀況也是最簡單就是不存在子節點的節點刪除 if(find_node->left==NULL&&find_node->right==NULL){ if(parent_node->left==find_node) parent_node->left = NULL; else parent_node->right = NULL; //進行2 free(find_node); return ; } //第二種狀況也就是中間節點,存在兩邊都是節點的狀況 else if(find_node->right!=NULL&&find_node->right!=NULL){ //刪除頭節點 if(find_node == *root){ printf("the node is head\n"); temp_node = (*root)->right; //便利到最左邊 while(temp_node->left!=NULL){ temp_node=temp_node->left; } temp_node->left = (*root)->left; *root=(*root)->right; free(find_node); return; } else{ //將這個節點插入到當前要刪除節點右邊的最左邊 Tree *temp_node2 = find_node; temp_node2=temp_node2->right; while(temp_node2->left=NULL){ temp_node2=temp_node2->left; } temp_node2->left = find_node->left; if(parent_node->left == find_node) parent_node->left = find_node->right; else parent_node->right = find_node->right; free(find_node); return ; } }else{ if(parent_node->left=find_node){ if(find_node->left!=NULL) parent_node->left = find_node->left; else parent_node->left = find_node->right; }else{ if(find_node->left!=NULL) parent_node->right = find_node->left; else parent_node->right = find_node->right; } free(find_node); return ; } } //前面 bianli void pre_order(Tree *node){ if(node == NULL) return ; printf("%d\n", node->data); pre_order(node->left); pre_order(node->right); } void middle_order(Tree *node){ if(node == NULL) return ; pre_order(node->left); printf("%d\n", node->data); pre_order(node->right); } void back_order(Tree *node){ if(node == NULL) return ; pre_order(node->left); pre_order(node->right); printf("%d\n", node->data); } //初始化節嗲 struct tree *init_tree(int data ){ Tree *newnode; newnode=(Tree *)malloc(sizeof(Tree)); newnode->data=data; newnode->left=NULL; newnode->right=NULL; return newnode; } //插入節點 void inser_tree(Tree **root,Tree * newnode) { if(*root == NULL) *root = newnode; else if(newnode->data > (*root)-> data) inser_tree(&((*root)->right),newnode); else inser_tree(&((*root)->left),newnode); } int main(int argc, char const *argv[]) { Tree *root=NULL; Tree *newnode=NULL; int data; int a[7]={5,3,1,4,8,6,9}; int i; for(i=0;i<7;i++){ newnode=init_tree(a[i]); inser_tree(&root,newnode); } data = 3; delete_tree(&root,data); pre_order(root); //find_tree(root,data); //printf("child Tree_node is:%d parent_node is %d\n",find_node->data,parent_node->data); return 0; }