Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <stdio.h>
- using namespace std;
- typedef struct Node
- {
- int data;
- struct Node* pLeft;
- struct Node* pRight;
- }NODE;
- typedef NODE* Tree;
- void Init(Tree& t)
- {
- t = NULL;
- }
- Node* CreateNode(int newdata)
- {
- Node* p = new Node;
- if (!p)
- {
- return NULL;
- }
- else
- {
- p->data = newdata;
- p->pLeft = p->pRight = NULL;
- }
- return p;
- }
- void AddNode(Tree& t, Node* p)
- {
- if (t == NULL)
- {
- t = p;
- t->pLeft = t->pRight = NULL;
- }
- else
- {
- if (p->data < t->data)
- {
- AddNode(t->pLeft, p);
- }
- else
- {
- AddNode(t->pRight, p);
- }
- }
- }
- void Input(Tree& t)
- {
- ifstream inp;
- inp.open("input.txt");
- if (!inp.is_open())
- {
- cout << "ERROR: Cannot open the input file!";
- }
- else
- {
- int newdata;
- Node* p = new Node;
- while (inp >> newdata)
- {
- p = CreateNode(newdata);
- AddNode(t, p);
- }
- }
- }
- void LNR(Tree t)
- {
- if (t != NULL)
- {
- LNR(t->pLeft);
- cout << t->data << " ";
- LNR(t->pRight);
- }
- }
- bool Search(const Tree t, int value)
- {
- if (t == NULL)
- return false;
- if (t->data == value)
- {
- return true;
- }
- else if (t->data > value)
- {
- return Search(t->pLeft, value);
- }
- else if (t->data < value)
- {
- return Search(t->pRight, value);
- }
- }
- int MostLeft(Tree t)
- {
- while (t->pLeft != NULL)
- {
- t = t->pLeft;
- }
- return t->data;
- }
- //
- //Node* Delete(Tree &t, int value)
- //{
- // if (t == NULL)
- // return t;
- // if (t->data > value)
- // t->pLeft = Delete(t->pLeft, value);
- // else if (t->data < value)
- // t->pRight = Delete(t->pRight, value);
- // else
- // {
- // if (t->pLeft == NULL)
- // {
- // Node* newRoot = t->pRight;
- // t = NULL;
- // return newRoot;
- // }
- // if (t->pRight == NULL)
- // {
- // Node* newRoot = t->pLeft;
- // t = NULL;
- // return newRoot;
- // }
- // t->data = MostLeft(t->pRight);
- // t->pRight = Delete(t->pRight, t->data);
- // }
- // return t;
- //}
- //Node* Delete(Tree& t, int value)
- //{
- // if (t == NULL)
- // return t;
- // if (t->data > value)
- // t->pLeft = Delete(t->pLeft, value);
- // if (t->data < value)
- // t->pRight = Delete(t->pRight, value);
- // else
- // {
- // if (t->pLeft == NULL)
- // {
- // Node* newRoot = t->pRight;
- // t = NULL;
- // return newRoot;
- // }
- // if (t->pRight == NULL)
- // {
- // Node* newRoot = t->pLeft;
- // t == NULL;
- // return newRoot;
- // }
- // t->data = MostLeft(t->pRight);
- // t->pRight = Delete(t->pRight, t->data);
- // }
- // return t;
- //}
- //
- //Node* Delete(Tree& t, int value)
- //{
- // if (t == NULL)
- // return t;
- // if (t->data > value)
- // t->pLeft = Delete(t->pLeft, value);
- // if (t->data < value)
- // t->pRight = Delete(t->pRight, value);
- // else
- // {
- // if (t->pLeft == NULL)
- // {
- // Node* newRoot = t->pRight;
- // t = NULL;
- // return newRoot;
- // }
- // if (t->pRight == NULL)
- // {
- // Node* newRoot = t->pLeft;
- // t = NULL;
- // return newRoot;
- // }
- // t->data = MostLeft(t->pRight);
- // t->pRight = Delete(t->pRight, t->data);
- // }
- // return t;
- //}
- Node* Delete(Tree& t, int value)
- {
- if (t == NULL)
- return t;
- if (t->data > value)
- t->pLeft = Delete(t->pLeft, value);
- if (t->data < value)
- t->pRight = Delete(t->pRight, value);
- else
- {
- if (t->pLeft == NULL)
- {
- Node* newRoot = t->pRight;
- t = NULL;
- return newRoot;
- }
- if (t->pRight == NULL)
- {
- Node* newRoot = t->pLeft;
- t = NULL;
- return newRoot;
- }
- t->data = MostLeft(t->pRight);
- t->pRight = Delete(t->pRight, t->data);
- }
- return t;
- }
- int main()
- {
- Tree t;
- int x, m;
- Init(t);
- Input(t);
- LNR(t);
- cout << "\nNhap x= ";
- cin >> x;
- if (Search(t, x))
- {
- cout << "Tim thay " << x << endl;
- }
- else
- {
- cout << "Khong tim thay " << x << endl;
- }
- cout << "Nhap m= ";
- cin >> m;
- Delete(t, m);
- cout << "Da xoa node: " << m << endl;
- LNR(t);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement