Thứ Hai, 14 tháng 5, 2012

Tinh So Nut O Do Cao h

Posted by Unknown Thứ Hai, tháng 5 14, 2012, under |



#include "stdafx.h"
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

typedef int element_type;
typedef struct node
{
  element_type element;
  struct node *left, *right;
} NODE;

NODE *root;

void khoi_tao_cay(NODE ** root)
{
  *root = NULL;
}

void insert(NODE *tmp, NODE **root)
{

  if (tmp->element < (*root)->element)
    if ((*root)->left)
      insert(tmp, &(*root)->left);
    else
       (*root)->left = tmp;
  else
    if ((*root)->right)
      insert(tmp, &(*root)->right);
    else
       (*root)->right = tmp;
}

void insert_node(element_type e, NODE **root)
{
   NODE *tmp;

   tmp = (NODE *)malloc(sizeof(NODE));
   tmp->element = e;
   tmp->left = NULL;
   tmp->right = NULL;
   if (*root == NULL)
     *root = tmp;
   else
     insert(tmp, root);
}

void nhap_cay(NODE **root)
{
  element_type e;
  printf("\n NHAP CAY NHI PHAN ! \n");
  printf("\n Nhap -1 de ket thuc !\n ");
  int i=1;
  do {

    printf("\n Nhap phan tu thu %d :",i);
    scanf("%d", &e);
    if (e != -1)
      insert_node(e, root);
 i++;
  } while (e != -1);
}

int  Count_All(NODE *root)  {  // Dem tong cac nut tren cay
        if (root == NULL)
return 0;
        return ( 1 +Count_All(root->left) + Count_All(root->right));
}

int Count_h(NODE *root, int h) //  Dem tong so nut o do cao h.
{
if(h>=0)
{
        if (root == NULL)
return 0;
        if (h == 0)
return 1;
else
return( Count_h(root->left, h-1) + Count_h(root->right, h-1));
}
else
return 0;

}

int Count_Up(NODE *root,int h)
{
int dem=0;
while(h>=0)
{
dem=dem + Count_h(root, h);
h=h-1;
}
return dem;
}

int Count_Down(NODE *root,int h)
{
return(Count_All(root) - Count_Up(root,h-1));
}


void main()
{
   khoi_tao_cay(&root);
   nhap_cay(&root);

   printf("\n So nut cua cay :%d",Count_All(root));
 
   int h;
   printf("\n Nhap mut de tinh so phan tu t :");
   scanf("%d",&h);  
   
    printf("\n \n Co %d nut o do cao %d  ",Count_h(root,h),h );

printf("\n \n Co % d tu do cao %d  ve goc  ",Count_Up(root,h),h );

printf("\n \n Co % d tu do cao %d ve den cuoi ",Count_Down(root,h),h );

   getch();
}

In Nut Thu K Cua CNPTK

Posted by Unknown Thứ Hai, tháng 5 14, 2012, under |



#include "stdafx.h"
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

typedef int element_type;
typedef struct node
{
  element_type element;
  struct node *left, *right;
} NODE;

NODE *root;

void khoi_tao_cay(NODE ** root)
{
  *root = NULL;
}

void insert(NODE *tmp, NODE **root)
{

  if (tmp->element < (*root)->element)
    if ((*root)->left)
      insert(tmp, &(*root)->left);
    else
       (*root)->left = tmp;
  else
    if ((*root)->right)
      insert(tmp, &(*root)->right);
    else
       (*root)->right = tmp;
}

void insert_node(element_type e, NODE **root)
{
   NODE *tmp;

   tmp = (NODE *)malloc(sizeof(NODE));
   tmp->element = e;
   tmp->left = NULL;
   tmp->right = NULL;
   if (*root == NULL)
     *root = tmp;
   else
     insert(tmp, root);
}

void nhap_cay(NODE **root)
{
  element_type e;
  printf("\n NHAP CAY NHI PHAN ! \n");
  printf("\n Nhap -1 de ket thuc !\n ");
  int i=1;
  do {

    printf("\n Nhap phan tu thu %d :",i);
    scanf("%d", &e);
    if (e != -1)
      insert_node(e, root);
 i++;
  } while (e != -1);
}

void tim_xuat_nguoc(NODE *root, int x)
{
if(!root)
printf("\n Cay rong !");
else
if(root->element==x)
printf(" %d",root->element);
else
if(root->element>x)
{
tim_xuat_nguoc(root->left,x);
printf(" %d", root->element);
}
else
{
tim_xuat_nguoc(root->right,x);
printf(" %d", root->element);
}
}

void in_nut_thu_k(NODE *root, int k)
{
if(!root)
return;
if(k==0)
{
printf(" %d", root->element);
}
in_nut_thu_k(root->left,k-1);
in_nut_thu_k(root->right, k-1);
}

void in_nut_thu_k(NODE *root, int k);
void duyet_theo_mut(NODE *root, int x)
{
for(int k=x;k>=1;k--)
in_nut_thu_k(root,k);
}

void main()
{
   khoi_tao_cay(&root);
   nhap_cay(&root);
   // xuat cac phan tu , tu phan tu =x ve goc
   int x;
   printf("\n Nhap gia tri xuat nguoc :");
   scanf("%d",&x);
   tim_xuat_nguoc(root,x);

   int h; // do cao
   printf("\n Nhap mut can in:");
   scanf("%d",&h);
   printf("\n Gia tri cac nut o do cao %d:", h);
   in_nut_thu_k(root,h);

   // xuat cac phan tu tu do cao h ve goc
   printf("\n Xuat cac phan tu tu do cao %d ve goc :",h);
   duyet_theo_mut(root, h);

   getch();
}

Tinh Chieu Cao CNPTK

Posted by Unknown Thứ Hai, tháng 5 14, 2012, under |



#include "stdafx.h"
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

typedef int element_type;
typedef struct node
{
  element_type element;
  struct node *left, *right;
} NODE;

NODE *root;

void khoi_tao_cay(NODE ** root)
{
  *root = NULL;
}

void insert(NODE *tmp, NODE **root)
{

  if (tmp->element < (*root)->element)
    if ((*root)->left)
      insert(tmp, &(*root)->left);
    else
       (*root)->left = tmp;
  else
    if ((*root)->right)
      insert(tmp, &(*root)->right);
    else
       (*root)->right = tmp;
}

void insert_node(element_type e, NODE **root)
{
   NODE *tmp;

   tmp = (NODE *)malloc(sizeof(NODE));
   tmp->element = e;
   tmp->left = NULL;
   tmp->right = NULL;
   if (*root == NULL)
     *root = tmp;
   else
     insert(tmp, root);
}

void nhap_cay(NODE **root)
{
  element_type e;
  printf("\n NHAP CAY NHI PHAN ! \n");
  printf("\n Nhap -1 de ket thuc !\n ");
  int i=1;
  do {

    printf("\n Nhap phan tu thu %d :",i);
    scanf("%d", &e);
    if (e != -1)
      insert_node(e, root);
 i++;
  } while (e != -1);
}

int tinh_chieu_cao(NODE *root)
{
if(!root)
return 0;
int a=tinh_chieu_cao(root->left);
int b=tinh_chieu_cao(root->right);
if(a>b)
return (a+1);
else
return (b+1);
}

void main()
{
   khoi_tao_cay(&root);
   nhap_cay(&root);
 
   int h;
   h=tinh_chieu_cao(root);
   printf("\n Chieu cao cay :%d", h);


   getch();
}

Dem Nut La CNPTK

Posted by Unknown Thứ Hai, tháng 5 14, 2012, under |


// DemNutLaCNPTK.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

typedef int element_type;
typedef struct node
{
  element_type element;
  struct node *left, *right;
} NODE;

NODE *root;

void khoi_tao_cay(NODE ** root)
{
  *root = NULL;
}

void insert(NODE *tmp, NODE **root)
{

  if (tmp->element < (*root)->element)
    if ((*root)->left)
      insert(tmp, &(*root)->left);
    else
       (*root)->left = tmp;
  else
    if ((*root)->right)
      insert(tmp, &(*root)->right);
    else
       (*root)->right = tmp;
}

void insert_node(element_type e, NODE **root)
{
   NODE *tmp;

   tmp = (NODE *)malloc(sizeof(NODE));
   tmp->element = e;
   tmp->left = NULL;
   tmp->right = NULL;
   if (*root == NULL)
     *root = tmp;
   else
     insert(tmp, root);
}

void nhap_cay(NODE **root)
{
  element_type e;
  printf("\n NHAP CAY NHI PHAN ! \n");
  printf("\n Nhap -1 de ket thuc !\n ");
  int i=1;
  do {

    printf("\n Nhap phan tu thu %d :",i);
    scanf("%d", &e);
    if (e != -1)
      insert_node(e, root);
 i++;
  } while (e != -1);
}

int dem_nut(NODE *root)
{
if(!root)
return 0;
else
return (1 + dem_nut(root->left) + dem_nut(root->right));
}

int dem_nut_la(NODE *root)
{
if(!root)
return 0;
int dem=dem_nut_la(root->left)+dem_nut_la(root->right);
if(root->left==NULL&&root->right==NULL)
dem++;
return dem;
}

void main()
{
   khoi_tao_cay(&root);
   nhap_cay(&root);
 
   int sonutcay;
   sonutcay=dem_nut(root);
   printf("\n So nut cua cay:%d", sonutcay);

   int sonutlacay;
   sonutlacay=dem_nut_la(root);
   printf("\n So lut la cua cay: %d", sonutlacay);


   getch();
}

Tim Xoa 1 Nut Tren CNPTK

Posted by Unknown Thứ Hai, tháng 5 14, 2012, under |


// TmXoaNutCNP.cpp : Defines the entry point for the console application.
//C++ 2010

#include "stdafx.h"
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include<conio.h>

typedef struct node
{
int a;
struct node *left,*right;
}cay;

void duyetgiua(cay *root)
{
if(root!=NULL)
{
duyetgiua(root->left);
printf("%3d",root->a);
duyetgiua(root->right);
}
}
void duyetsau(cay *root)
{
if(root!=NULL)
{
duyetsau(root->left);
duyetsau(root->right);
printf("%3d",root->a);
}
}
void main()
{

cay *root,*temp,*temp1,*temp2;
int k,n,x;
root=NULL;

 //Them 1 nut//

printf("\n Tien hanh nhap du lieu cho cay:");
do
{
printf("\n Nhap X (Nhap -1 de ket thuc):");
scanf("%d",&x);
if(x==-1)
break;
temp=root;
k=0;
while(temp!=NULL)
{
if(x<temp->a)
temp=temp->left;
else if(x>temp->a)
temp=temp->right;
else
{
k=1;
break;
}
}
if(k==1)
{
printf("\n Trung khoa va nhap lai!!!\n");
continue;
}
if(root==NULL)
{
root=new cay;
temp=root;
}
else
{
temp1=root;
k=1;
while(temp1!=NULL)
{
temp=temp1;
if(x<temp1->a)
temp1=temp1->left;
else if(x>temp1->a)
temp1=temp1->right;
}
if(x<temp->a)
{
temp->left=new cay;
temp=temp->left;
}
else
{
temp->right=new cay;
temp=temp->right;
}

}
temp->a=x;
temp->left=temp->right=NULL;
}
while(1);
printf("\n Duyet giua:\n");
duyetgiua(root);
printf("\n Duyet sau:\n");
duyetsau(root);

 //Tim kiem 1 nut//

printf("\n Nhap gia tri can tim kiem:");
scanf("%d",&x);
temp=root;
while(temp!=NULL)
{
if(x<temp->a)
temp=temp->left;
else if(x>temp->a)
temp=temp->right;
else
break;
}
if(temp==NULL)
printf("\n Tim khong ra!!!");
else
printf("\n Tim thay!!!");
printf("\nTac vu tim kiem da xong.");
 
 //Xoa 1 nut trong cay//

printf("\n Nhap gia tri can xoa:");
scanf("%d",&x);
temp=root;
while(temp!=NULL)
{
if(temp->a==x)
break;
temp1=temp;
if(x<temp->a)
temp=temp->left;
else if(x>temp->a)
temp=temp->right;
}
printf("\n Nut can xoa la: %d, nut cha la %d\n",temp->a,temp1->a);
if(temp==NULL)
printf("\n Tim khong thay!!!");
else
if(temp->left==NULL&&temp->right==NULL)
if(temp->a<temp1->a)
temp1->left=NULL;
else
temp1->right=NULL;
else if(temp->left==NULL)
{
temp1->right=temp->right;
delete(temp);
}
else if(temp->right==NULL)
{
temp1->left=temp->left;
delete(temp);
}
else if(temp->right!=NULL&&temp->left!=NULL)
{
temp1=temp->left;
if(temp1->right==NULL)
{
temp->a=temp1->a;
temp->left=temp1->left;
delete(temp1);
}
else
{
while(temp1->right!=NULL)
{
temp2=temp1;
temp1=temp1->right;
}
temp->a=temp1->a;
temp2->right=NULL;
delete(temp1);
}
}
duyetsau(root);

getch();
}

Cay Nhi Phan Tim Kiem

Posted by Unknown Thứ Hai, tháng 5 14, 2012, under |


Cây tìm kiếm nhị phân:

Cây tìm kiếm nhị phân (viết tắt tiếng Anh: BST - Binary Search Tree) là một cấu trúc dữ liệu rất thuận lợi cho bài toán tìm kiếm.
Cây tìm kiếm ứng với n khóa  là cây nhị phân mà mỗi nút đều được gán một khóa sao cho với mỗi mỗi nút k:
Mọi khóa trên cây con trái đều nhỏ hơn khóa trên nút k
Mọi khóa trên cây con phải đều lớn hơn khóa trên nút k
Ảnh CNPTK
Cây tìm kiếm nhị phân là một cấu trúc dữ liệu cơ bản được sử dụng để xây dựng các cấu trúc dữ liệu trừu tượng hơn như các tập hợp, đa tập hợp, các dãy kết hợp.
Nếu một BST có chứa các giá trị giống nhau thì nó biểu diễn một đa tập hợp. Cây loại này sử dụng các bất đẳng thức không nghiêm ngặt. Mọi nút trong cây con trái có khóa nhỏ hơn khóa của nút cha, mọi nút trên cây con phải có nút lớn hơn hoặc bằng khóa của nút cha.
Nếu một BST không chứa các giá trị giống nhau thì nó biểu diễn một tập hợp đơn trị như trong lý thuyết tập hợp. Cây loại này sử dụng các bất đẳng thức nghiêm ngặt. Mọi nút trong cây con trái có khóa nhỏ hơn khóa của nút cha, mọi nút trên cây con phải có nút lớn hơn khóa của nút cha.
Việc chọn đưa các giá trị bằng nhau vào cây con phải (hay trái) là tùy theo mỗi người. Một số người cũng đưa các giá trị bằng nhau vào cả hai phía, nhưng khi đó việc tiìm kiếm trở nên phức tạp hơn.
Các phép toán trên BST

Tìm kiếm (Searching):

Việc tìm một khóa trên BST có thể thực hiện nhờ đệ quy. Chúng ta bắt đầu từ gốc. Nếu khóa cần tìm bằng khóa của gốc thì khóa đó trên cây, nếu khóa cần tìm nhỏ hơn khoa ở gốc, ta phải tìm nó trên cây con trái, nếu khóa cần tìm lớn hơn khóa ở gốc, ta phải tìm nó trên cây con phải. Nếu cây con (trái hoặc phải) là rỗng thì khóa cần tìm không có trên cây.


Search_binary_tree(node, key):
{
 if node is Null then
       return; None  /* key not found */
   
      if key < node.key:
          return search binary_tree(node.left, key);
           else
                if key > node.key  return search_binary_tree(node.right, key)
                else  /* key is equal to node key */
                    return node.value;  # found key
}


Thời gian tìm kiếm trung bình là O(log n), và là O(n) khi cây là không cân bằng chỉ là một danh sách liên kết.

Chèn (Insertion):

Phép chèn bắt đầu giống như phép tìm kiếm; Nếu khóa của gốc khác khóa cần chèn ta tìm nó trong cây con trái hoặc phải. Nếu cây con trái hoặc phải tương ứng là rỗng (không tìm thấy) thì thêm một nút và gán cho nút ấy khóa cần chèn.
Sau đây là mã trong C++ :
void InsertNode(struct node *&treeNode, struct node *newNode)
{ //Inserts node pointered by "newNode" to the subtree started by "treeNode"
    if (treeNode == NULL)
        treeNode = newNode; //Only changes "node" when it is NULL
    else if (newNode->value < treeNode->value)
        InsertNode(treeNode->left, newNode);
    else
        InsertNode(treeNode->right, newNode);
}

Xóa (Deletion)

Xét các trường hợp sau:

Xóa một lá: Vì lá không có con nên chỉ cần giải phóng nó khỏi cây.
Xóa nút có một con: Xóa và thay thế nó bằng con duy nhất của nó.


Xóa một nút có hai con: Xóa nút đó và thay thế nó bằng nút có khóa lớn nhất
trong các khóa nhỏ hơn khóa của nó (được gọi là "nút tiền nhiệm" -nút cực phải của cây con trái) hoặc nút có nhỏ nhất trong các khóa lớn hơn nó (được gọi là "nút kế vị" - nút cực trái của cây con phải) Cũng có thể tìm nút tiền nhiệm hoặc nút kế vị đổi chỗ nó với nút cần xóa và sau đó xóa nó. Vì các nút kiểu này có ít hơn hai con nên việc xóa nó được quy về hai trường hợp trước.


void DeleteNode(struct node*& node) {      
    if (node->left == NULL) { 
  struct node* temp = node;
        node = node->right;
        delete temp;
    } else if (node->right == NULL) {
     
        struct node* temp = node;
        node = node->left;
        delete temp;
       
    } else {
        // In-Order predecessor(right most child of left subtree) 
        // Node has two children - get max of left subtree

        struct node** temp = &(node->left); // get left node of the original node

        // find the right most child of the subtree of the left node
        while ((*temp)->right != NULL) {
            temp = &((*temp)->right);
        }
         
        // copy the value from the right most child of left subtree to the original node
        node->value = (*temp)->value;

        // then delete the right most child of left subtree since it's value is
        // now in the original node
        DeleteNode(*temp);
    }
}

Phép duyệt:

Khi một cây tìm kiếm nhị phân được tạo ra, tất cả các nút có thể được duyệt theo thứ tự giữa nhờ duyệt đệ qui cây con bên trái, in nút đang duyệt, rồi duyệt đệ qui cây con bên phải, tiếp tục làm như vây với mỗi nút của cây trong quá trình đệ qui. Với mọi cây nhị phân, cây có thể được duyệt theo thứ tự trước() hoặc theo thứ tự sau(), cả hai cách đều hữu dụng với cây tìm kiếm nhị phân.
Đoạn mã cho duyệt theo thứ giữa được viết dưới đây với C++ :
void traverse_binary_tree(struct node* n)
{
   if(n==null)     //Cay rong
       return;
   else
       {
           traverse_binary_tree(n->left);     //Duyet cay con trai theo thu tu giua
           printf("%d",n.key);                //Tham nut
           traverse_binary_tree(n->right);    //Duyet cay con phai theo thu tu giua
       }
}
Phép duyệt có độ phức tạp tính toán là Ω(n), vì nó phải duyệt qua tất cả các nút. Độ phức tạp trên cũng là O(“n”).

Nhap Xuat Duyet Cay Nhi Phan C++

Posted by Unknown Thứ Hai, tháng 5 14, 2012, under |


// Viet tren C++ 2010

#include "stdafx.h"

#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include<conio.h>

typedef int element_type;
typedef struct node {
  element_type element;
  struct node *left, *right;
} NODE;

NODE *root;

void khoi_tao_cay(NODE ** root)
{
  *root = NULL;
}

void insert(NODE *tmp, NODE **root)
{

  if (tmp->element < (*root)->element)
    if ((*root)->left)
      insert(tmp, &(*root)->left);
    else
       (*root)->left = tmp;
  else
    if ((*root)->right)
      insert(tmp, &(*root)->right);
    else
       (*root)->right = tmp;
}

void insert_node(element_type e, NODE **root)
{
   NODE *tmp;

   tmp = (NODE *)malloc(sizeof(NODE));
   tmp->element = e;
   tmp->left = NULL;
   tmp->right = NULL;
   if (*root == NULL)
     *root = tmp;
   else
     insert(tmp, root);
}

void nhap_cay(NODE **root)
{
  element_type e;
  printf("\n NHAP CAY NHI PHAN ! \n");
  printf("\n Nhap -1 de ket thuc !\n ");
  int i=1;
  do {

    printf("\n Nhap phan tu thu : ",i);
    scanf("%d", &e);
    if (e != -1)
      insert_node(e, root);
i++;
  } while (e != -1);
}

void NLR(NODE *root)
{
  if (root != NULL)
  {
    printf("%d ", root->element);
    NLR(root->left);
    NLR(root->right);
  }
}

void NRL(NODE *root)
{
  if (root != NULL)
  {
    printf("%d ", root->element);
    NRL(root->right);
    NRL(root->left);
  }
}

void LNR(NODE *root)
{
  if (root != NULL)
  {
    LNR(root->left);
    printf("%d ", root->element);
    LNR(root->right);
  }
}

void LRN(NODE *root)
{
  if (root != NULL)
  {
    LRN(root->left);
    LRN(root->right);
    printf("%d ", root->element);
  }
}

void RNL(NODE *root)
{
  if (root != NULL)
  {
    RNL(root->right);
    printf("%d ", root->element);
    RNL(root->left);
  }
}

void RLN(NODE *root)
{
  if (root != NULL)
  {
    RLN(root->right);
    RLN(root->left);
    printf("%d ", root->element);
  }
}

void main()
{
   khoi_tao_cay(&root);
   nhap_cay(&root);
   printf("\nDuyet cay NLR : ");
   NLR(root);
   printf("\nDuyet cay NRL : ");
   NRL(root);
   printf("\nDuyet cay LNR : ");
   LNR(root);
   printf("\nDuyet cay LRN : ");
   LRN(root);
   printf("\nDuyet cay RNL : ");
   RNL(root);
   printf("\nDuyet cay RLN : ");
   RLN(root);
   getch();
}

Cây Nhị Phân C++

Posted by Unknown Thứ Hai, tháng 5 14, 2012, under |




Trong khoa học máy tính, cây là một cấu trúc dữ liệu được sử dụng rộng rãi gồm một tập hợp các nút (tiếng Anh: node) được liên kết với nhau theo quan hệ cha-con. Cây trong cấu trúc dữ liệu đầu tiên là mô phỏng (hay nói cách khác là sự sao chép) của cây (có gốc) trong lý thuyết đồ thị. Hầu như mọi khái niệm trong cây của lý thuyết đồ thị đều được thể hiện trong cấu trúc dữ liệu. Tuy nhiên cây trong cấu trúc dữ liệu đã tìm được ứng dụng phong phú và hiệu quả trong nhiều giải thuật. Khi phân tích các giải thuật trên cấu trúc dữ liệu cây, người ta vẫn thường vẽ ra các cây tương ứng trong lý thuyết đồ thị.


Ảnh CNP
Các nút
Một nút có thể chứa một giá trị, một điều kiện, một cấu trúc dữ liệu riêng biệt hoặc chính một cây. Mỗi nút trong một cây có thể không có hoặc có một số nút con, các nút con có mức cao hơn nó (theo quy ước khác với cây tự nhiên, cây trong cấu trúc dữ liệu phát triển từ trên xuống). Một nút có con được gọi là nút cha của các nút con. Một nút có nhiều nhất một nút cha.
Nút gốc
Trong mỗi cây có một nút đặc biệt được gọi là nút gốc (hay nói đơn giản là gốc). Nút gốc là nút duy nhất không có nút cha. Nút gốc là nơi khởi đầu của nhiều giải thuật trên cây. Tất cả các nút khác được nối về nút gốc bằng một đường đi qua các cạnh hay các liên kết
Các nút lá
Các nút không có nút con được gọi là nút lá hay gọi đơn giản là lá.
Các nút trong
nút trong của một cây là nút trên cây có ít nhất một con, nghĩa là các nút không phải là lá. Các khái niệm về mức của mỗi nút, chiều cao của cây được định nghĩa giống như cây trong lý thuyết đồ thị.
Cây con
Một cây con là một bộ phận của cấu trúc dữ liệu cây mà tự nó cũng là một cây. Một nút bất kỳ trong cây T, cùng với các nút dưới nó tạo thành một cây con của T.
Cây trong lý thuyết đồ thị
Trong lý thuyết đồ thị, một cây là một đồ thị liên thông và không có chu trình. Cây như vậy còn được gọi là cây tự do. Một cây có gốc là một cây tư do, trong đó có một đỉnh được chọn làm gốc và các cạnh được định hướng là hướng của các đường đi đơn ra khỏi gốc tới các đỉnh khác. Trong trường hợp này, hai đỉnh bất kỳ dược nối với nhau bao hàm ‎ chúng có qua hệ cha-con. Một đồ thị không chu trình với nhiều thành phần liên thông được gọi là một rừng.
Cây sắp thứ tự
Có hai dạng cấu trúc cơ sở của cây là cây không thứ tự và cây có thứ tự. Một cây không thứ tự là cây có cấu trúc cây, trong đó giữa các con của một nút, không có thứ tự nào. Một cây, trong đó các con của một nút tuân theo một thứ tự xác định được gọi là cây có thứ tự. Các cây có thứ tự có nhiều ứng dụng sâu sắc trong cấu trúc của cây. Cây tìm kiếm nhị phân là một cây sắp thứ tự điển hình.
Cây tổng quát và cây nhị phân
Các cây trong đó mỗi nút có thể có nhiều hơn hai con được gọi là cây tổng quát, các cây trong đó mỗi nút có không quá hai con được gọi là cây nhị phân.
Biểu diễn cây
Có nhiều phương pháp biểu diễn cây. Cách thường dùng nhất là biểu diễn mỗi nút như một dữ liệu kiểu bản ghi, mỗi nút chứa các con trỏ tới các con hoặc cha của nó, hoặc cả hai. Cây cũng có thể biểu diễn bằng các mảng cùng với quan hệ giữa các vị trí trong mảng.
Biểu diễn bằng các nút với các con trỏ
Mỗi nút là một dữ liệu kiểu bản ghi với ba trường: Một trường thường gọi là INFOR, chứa thông tin lưu trữ tại nút đó. Thông tin này có thể chỉ là một số, một ký tự, cũng có thể là một tập hợp dữ liệu rất phức tạp. Hai trường LLINK và RLINK chứa các liên kết trái và phải. Nếu cây là cây nhị phân, LLINK trỏ tới con trái của nút, RLINK trỏ tới con phải của nút. Nếu cây là cây tổng quát, LLINK trỏ tới con cực trái và RLINK trỏ tới em kế cận phải của nút đó. Do đó danh sách các nút biểu diễn một cây tổng quát, khi được xem là biểu diễn của cây nhị phân sẽ cho một cây nhị phân. Cây nhị phân này được gọi là cây nhị phân tương đương với cây tổng quát ban đầu.
Biểu diễn cây nhị phân bằng mảng
Cây nhị phân mà mỗi đỉnh trong có đúng hai con được gọi là cây nhị phân đầy đủ(full binary tree)
Cây nhị phân đầy đủ mà tất cả các lá có cùng một mức được gọi là cây nhị phân hoàn chỉnh (perfect binary tree). Một số tài liệu gọi cây loại này là cây đầy đủ.
Cây nhị phân mà mỗi đỉnh của nó đã có con phải thì cũng có con trái được gọi là cây nhị phân gần hoàn chỉnh (almost complete binary tree).
Ta có thể dùng một mảng gồm  phần tử để biểu diễn cây nhị phân, bằng cách lần lượt lưu trữ thông tin của mỗi nút vào mảng theo thứ tự từ trên xuống dưới, từ trái sang phải. Khi đó con trái của nút thứ i là phần tử thứ 2*i, con phải là phần tử thứ 2*i+1. Cha của phần tử thứ i là phần tử thứ int(i/2).Ta gán giá trị Null cho các vị trí còn thiếu.
Một cách khác, dùng một mảng hai chiều trong dòng thứ nhất ghi các thông tin của nút, dòng thứ hai ghi chỉ số của nút cha của nút đó với dấu + nếu nút hiện tại là con trái, với dấu - nếu nút hiện tại là con phải của nút cha.
Các phương pháp duyệt cây
Duyệt một cây là một trình tự làm việc với các nút trong cây, trình tự này giống như một chuyến đi qua các nút trên cây theo các liên kết cha-con, bắt đầu từ nút gốc. Các giải thuật duyệt khác nhau về thứ tự “viếng thăm” giữa một nút cha và các nút con.
Duyệt tiền thứ tự
Duyệt trung thứ tự
Duyệt hậu thứ tự
Các giải thuật chung
Tìm kiếm một mục trên cây
Bổ sung một mục mới
Xóa một mục






Xem Nhiều

Bài đăng phổ biến

Lưu trữ blog

Blog Archive