Các Thao Tác Trên Cây AVL

* Cac thao tac tren cay AVL
1. Them node vao cay AVL
2. Loai node tren cay AVL
3. Tim node tren cay AVL
4. Duyet theo thu tu truoc
5. Duyet theo thu tu giua
6. Duyet theo thu tu sau
7. chieu cao cua cay AVL

code :

#include <iostream>
#include <stdlib.h>
using namespace std;
// dinh nghia Node
typedef int item;
typedef struct Node {
item data;
struct Node *left;
struct Node *right;
item height;
};
void init (Node *T){
T = NULL;
}
int Max (int a, int b){
return (a>b) ? a : b;
}
int height (Node *T){
if (T == NULL)
return 0;
return T->height;
}
// tao 1 node moi
Node *makeNode (int data){
Node *p = new Node;
p->data = data;
p->left = NULL;
p->right = NULL;
return p;
}
//tim node co gia tri x
Node *search (Node *T, int x) {
if (T==NULL || T->data == x)
return T;
if (T->data < x)
return search (T->right,x);
return search (T->left,x);
}
// quay phai tai node T
Node *Qright (Node *T){
Node *x = T->left;
Node *T2 = x->right;
// xoay
x->right = T;
T->left = T2;
// cap nhat chieu cao
T->height = Max (height(T->left), height(T->right)) +1;
x->height = Max (height (x->left), height (x->right)) +1;

return x;
}
// quay trai tai node T
Node *Qleft (Node *T){
Node *y = T->right;
Node *T2 = y->left;
// xoay
y->left = T ;
T->right = T2;
// cap nhat chieu cao
T->height = Max (height(T->left), height (T->right)) + 1;
y->height = Max (height(y->left), height (y->right)) + 1;

return y;
}
int getCB (Node *T){
if (T == NULL)
return 0;
return height (T->left) - height (T->right);
}
Node *Insert (Node *node , int data){
// B1
if (node == NULL) {
return (makeNode (data));
}
if (data < node->data) {
node->left = Insert (node->left,data);
}else
node->right = Insert (node->right,data);
//B2

node->height = max (height(node->left),height (node->right)) +1 ;

//B3
int CB = getCB(node);
// left - left - case
if (CB > 1 && data < node->left->data )
return Qright(node);
// right - right - case
if (CB <-1 && data > node->right->data)
return Qleft (node);
// left right case
if (CB > 1 && data > node->left->data) {
node->left = Qleft(node->left);
return Qright(node->right);
}
// right left case
if (CB < -1 && data < node->right->data){
node->right = Qright (node->right);
return Qleft (node);
}
return node;
}
void NLR(Node *root){//duyet NLR
if(root != NULL) {
cout << root->data;
NLR(root->left);
NLR(root->right);
}
}
void LNR(Node *root){//duyet LNR
if(root != NULL) {
LNR(root->left);
cout << root->data;
LNR(root->right);
}
}
void LRN(Node *root){//duyet LRN
if(root != NULL) {
LRN(root->left);
LRN(root->right);
cout << root->data;
}
}
Node * minValueNode(Node *node){
Node *current = node;
while (current->left != NULL)
current = current->left;
return current;
}
Node* deleteNode (Node *root, int key){
if (root == NULL)
return root;
if ( key < root->data )
root->left = deleteNode(root->left, key);
else if( key > root->data )
root->right = deleteNode(root->right, key);
else {
if( (root->left == NULL) || (root->right == NULL) ){
Node *temp = root->left ? root->left : root->right;
if(temp == NULL){
temp = root;
root = NULL;
}
else
*root = *temp;
free(temp);
}
else {
Node* temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
if (root == NULL)
return root;
root->height = max(height(root->left), height(root->right)) + 1;
int CB = getCB(root);
if (CB > 1 && getCB(root->left) >= 0)
return Qright(root);
if (CB > 1 && getCB(root->left) < 0) {
root->left = Qleft(root->left);
return Qright(root);
}
if (CB < -1 && getCB(root->right) <= 0)
return Qleft(root);
if (CB < -1 && getCB(root->right) > 0) {
root->right = Qright(root->right);
return Qleft(root);
}
return root;
}
//tim do cao cua cay
int maxDepth(Node* node) {
if (node==NULL)
return 0;
else {
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}
int main(){
Node *root = NULL;
Node *tmp;
int data, LC;
do {
system("cls");
cout << "\n-------MENU-------\n";
cout << "\n Cac thao tac tren cay AVL";
cout << "\n 1. Them node vao cay AVL";
cout << "\n 2. Loai node tren cay AVL";
cout << "\n 3. Tim node tren cay AVL";
cout << "\n 4. Duyet theo thu tu truoc";
cout << "\n 5. Duyet theo thu tu giua";
cout << "\n 6. Duyet theo thu tu sau";
cout << "\n 7. chieu cao cua cay AVL";
cout << "\n 0. Thoat khoi chuong trinh";
cout << "\n------------------------\n";
cout << "\n Dua vao lua chon:";cin >> LC;
switch(LC) {
case 1:
cout << "\n Gia tri node can them:"; cin >> data;
root = Insert(root, data);
cout << "\n nhap bat ki de quay lai \n";
system("pause");
break;
case 2:
cout << "\n Gia tri node can loai:"; cin >> data;
root = deleteNode(root, data);
cout << "\n nhap bat ki de quay lai \n";
system("pause");
break;
case 3:
cout << "\n Gia tri node can tim:"; cin >> data;
tmp = search(root, data);
if (tmp==NULL) cout<< "\n Node khong co tren cay";
else cout << "\n Node co tren cay";
cout << "\n nhap bat ki de quay lai \n";
system("pause");
break;
case 4:
NLR(root);
cout << "\n nhap bat ki de quay lai \n";
system("pause");
break;
case 5:
LNR(root);
cout << "\n nhap bat ki de quay lai \n";
system("pause");
break;
case 6:
LRN(root);
cout << "\n nhap bat ki de quay lai \n";
system("pause");
break;
case 7:
cout << "chieu cao cua cau luc nay la: " << maxDepth(root) << endl;
cout << "\n nhap bat ki de quay lai \n";
system("pause");
break;
default:
if(LC!=0) cout << "\n Lua chon sai";
cout << "\n nhap bat ki de quay lai \n";
system("pause");
break;
}
// cout << "\n Duyet truoc:"; NLR(root);
// cout << "\n Duyet giua:"; LNR(root);
// cout << "\n Duyet sau:"; LRN(root);
} while(LC!=0);
}

GIẤC MƠ GIỮA MÙA ĐÔNG

GIẤC MƠ GIỮA MÙA ĐÔNG Chìm vào trong nỗi nhớ Lòng tôi vẫn bâng khuâng Dở mơ hay giấc mông Em đến như công chúa Bước ra từ cổ tích Cùng tôi phưu lưu ký Giữa phố thị xôn xao Em kể đôi câu chuyện Lòng tôi thấy yên bình Chuyện ngày càng lôi quấn Hút tôi khỏi thực tại Chìm vào giấc mộng ảo Được cùng em bước tiếp Trên những phố quen thuộc Giấc mộng đang khôn lớn Em bỗng nói chia xa Để ... Về trong chuyện cổ tích Mộng đẹp bỗng tan vỡ Lòng tôi lạc giữa phố đông Theo dòng chảy thời gian Bào mòn từng ký ức Lòng tôi càng lạc lõng Chẳng biết thực hay hư Chỉ thấy lòng trống vắng Nhớ em đến dại khờ. TRANSLATE with x English Arabic Hebrew Polish Bulgarian Hindi Portuguese Catalan Hmong Daw Romanian Chinese Simplified Hungarian Russian Chinese Traditional Indonesian Slovak Czech Italian Slovenian Danish Japanese Spanish Dutch Klingon Swedish English Korean Thai Estonian Latvian Turkish Finnish Lithuanian Ukrainian French Malay Urdu German Maltese Vi...

Đọc thêm

Coding

Tìm kiếm Blog này