Cấp bậc tác giả:

JAVA

Cây nhị phân

Được viết bởi webmaster ngày 13/05/2015 lúc 06:35 PM
Là cây mà tại mỗi nút có tối đa 2 con
  • 0
  • 11286

Cây nhị phân

I. Định nghĩa và khái niệm
1. Định nghĩa: Là cây mà tại mỗi nút có tối đa 2 con
2. Khái niệm:
- Nút gốc
- Nút lá
- Chiều cao của cây
. Nút gốc có chiều cao là 1
. Nút cha có chiều cao là h
thì nút con có chiều cao là h+1
3. Tổ chức dữ liệu
Struct NUT
{
  <Type> Data;
  NUT *left; *right;
};
typedef NUT *Tree;

Vd:

cay-nhi-phan.jpg

4. Các phép duyệt cây
- NLR(duyệt trái)   A B C D E F
- LNR(duyệt giữa) C B D A E F
- LRN(duyệt phải) C D B F E A
- Theo mức           A B E C D F

void NLR(Tree Root)
{
  if(Root!= NULL)
  {
    <Thăm Root->Data>;
    NLR(Root->left);
    NLR(Root->right);
  }
}

void LNR(Tree Root)
{
  if(Root!= NULL)
  {
    LNR(Root->left);
    <Thăm Root->Data>;
    LNR(Root->right);
  }
}

void LRN(Tree Root)
{
  if(Root!= NULL)
  {
    LRN(Root->left);
    LRN(Root->right);
    <Thăm Root->Data>;
  }
}

void DuyetMuc(Tree Root)
{
  Queue = 0;
  PUSH(Root, Queue);
  While(Quee!=0){
  x = POP(Queue);
  <Thăm x->Data>;
  if(x->left!=NULL) PUSH(x->left, Queue);
  if(x->right!=NULL) PUSH(x->right, Queue);
  }
}

Bài tập:
Tổ chức cây nhị phân chứa các số nguyên
1. Đếm cây có bao nhiêu nút
2. Tính tổng giá trị của các nút lá
3. Tính chiều cao của cây

Struct NUT
{
  int x;
  NUT *left, *right;
};
typedef NUT *Tree;

1. Đếm xem cây có bao nhiêu nút(dùng đệ quy)
int Dem(Tree Root)
{
if(Root==NULL) return 0;
else
return 1+Dem(Root->left) + Count(Root->right);
}

2. Tính tổng giá trị của các nút lá

int leafSum(Tree Root)
{
if(Root==NULL) return 0;
else if((Root->left)==NULL)&&(Root->right==NULL)) return Root->x;
else return leafSum(Root->left)+leafSum(Root->right);
}

3. Tính chiều cao của cây

int max(int a, int b)
{
  if(a>b) return a;
  else return b;
}

int hight(Tree Root)
{
  if(Root==NULL) return 0;
  else return 1+ max(hight(Root->left),hight(Root->right));
}

II. Cây tìm kiếm nhị phân(BST = Binary Search Tree)
1. Định nghĩa: Là cây nhị phân mà khóa ở mọi nút nó luôn luôn >= khóa của tất cả các nút ở cây con bên trái và đồng thời <= khóa của tất cả các nút ở cây con bên phải.
2. Các thao tác cơ bản
a. Bổ sung giá trị x vào cây

void insert(int x, Tree &Root)
{
  if(Root==NULL)
  {
    Root=new (NUT);
    Root->Data = x;
    Root->left=Root->right=NULL;
  }
  else if(x<Root->Data) insert(x, Root->left);
  else if(x>Root->Data) insert(x, Root->right);
}

b. Tìm kiếm(kiểm tra) giá trị x có trên cây hay không(BST)
- Không tìm thấy trả về giá trị NULL.
- Tìm thấy: trỏ đến nút tìm được

Tree Search(int x, Tree Root)
{
  if(Root==NULL) return NULL;
  else if(x==Root->Data) return Root;
  else if(x<Root->Data) return Search(x, Root->left);
  else return Search(x, Root->right);
}

Nguồn bài viết: DOTNET.VN

BÌNH LUẬN BÀI VIẾT

Bài viết mới nhất

LIKE BOX

Bài viết được xem nhiều nhất

HỌC HTML