Cây nhị phân part2 search,xoa node lá ,xóa node có 1 con

#include<iostream> using namespace std; // 5 bước cơ bản khi thao tác với cây nhị phân //1. khai báo 1node //2. khởi tạo 1 tree //3. thêm 1 vào cây //4. tạo cây //5.duyệt cây // khai báo 1 node tren cây /// khai ;,báo 1 node struct node { int data;// dữ liệu chứa trong node struct node *pleft; struct node *pright; }; typedef struct node NODE; typedef NODE* tree; ///// khởi tạo cây void init(tree &t) { t = NULL; } // thêm 1 phần tử vào cây void insert(tree &t, int x) { /// nếu cây rỗng if (t == NULL) { NODE *q = new NODE; q->data = x; q->pleft = q->pright = NULL; t = q; } else { ///// nếu phần tử cần thêm vào mà nó nhỏ hơn nốt gốc thì ta thêm vào bên trái ///// còn lớn hơn thì thêm vào bên phải if (t->data > x) { insert(t->pleft, x); } else if (t->data < x) { insert(t->pright, x); } } } /// tạo cây void createtree(tree &t) { // đầu tiên khởi tạo cây init(t); int luachon; do { cout << "\n1.Nhap du lieu! "; cout << "\n0.thoat"; cout << "\nNhap lua chon! "; cin >> luachon; if (luachon == 1) { int x; cout << "\nNhap x"; cin >> x; insert(t, x);// thêm x vào cây } } while (luachon != 0); } /// duyệt cây void nlr(tree t) { if (t != NULL) { cout << "\n " << t->data; nlr(t->pleft); nlr(t->pright); } } void lnr(tree t) { if (t != NULL) { lnr(t->pleft); cout << "\n " << t->data; lnr(t->pright); } } void lrn(tree t) { if (t != NULL) { lrn(t->pleft); lrn(t->pright); cout << "\n " << t->data; } } void nrl(tree t) { if (t != NULL) { cout << "\n " << t->data; nrl(t->pright); nrl(t->pleft); } } void rnl(tree t) { if (t != NULL) { nrl(t->pright); cout << "\n " << t->data; nrl(t->pleft); } } void rln(tree t) { if (t != NULL) { rln(t->pright); rln(t->pleft); cout << "\n " << t->data; } } // tìm kiếm 1node NODE* search(tree t, int x) { if (t == NULL) { return NULL; } if (t->data > x) { search(t->pleft, x); } else if (t->data < x) { search(t->pright, x); } else { return t; } } //// xóa 1 node /* Nguyên tắc xóa nếu node là node lá thì --> xóa bình thường nếu nodse cần xóa có 1 con thì-> nối node con của nó lên rồi xóa bình thường // nếu node cần xóa có 2 con thì--> tìm pahn26 tử thế mạng cho nói + có 2 cách chọn phần tử thế mang5 c1: chọn trái nhất của cây con phải c2: chọn phải nhất của cây con trái */ /////////////////////// mô phỏng hàm xóa node 1 con void xoanode(tree &t, int x) { /// trước tiên ta sẽ xóa node có 1con và node lá if (t == NULL) { return;// kết thúc không duyệt nữa } if (t->data > x) { xoanode(t->pleft, x); } else if (t->data < x) { xoanode(t->pright, x); } else // t->data == x; { /// ngược lại nếu nó bằng thì xóa node *g = t; if (t->pleft == NULL) { t = t->pright; } else if (t->pright == NULL) { t = t->pleft; } delete g; } } int main() { tree t; createtree(t); cout << "\nnlr:\n"; nlr(t); cout << "\nnrl:\n"; nrl(t); cout << "\nlnr:\n"; lnr(t); cout << "\nlrn:\n"; lrn(t); cout << "\nrnl:\n"; rnl(t); cout << "\nrln:\n"; rln(t); cout << endl; int f; cout << "\nNhap gia tri can tim: "; cin >> f; NODE *p = search(t, f); if (p == NULL) { cout << "\nKhong co phna tu can tim xin kiem tra lai!"; } else { cout << "\nPhan tu co ton tai trong cay !" << p->data; } cout << "\nXoa 1 node :-------------------------------------------: "; int j; cout << "\nNhap gia tri can xoa: "; cin >> j; xoanode(t, j); cout << "\ncay sau khi xoa la! "; cout << "\nnlr:\n"; nlr(t); system("pause"); return 0; }