Khác biệt giữa bản sửa đổi của “Cây (cấu trúc dữ liệu)”

Nội dung được xóa Nội dung được thêm vào
Dòng 45:
*[[Duyệt cây|Duyệt trung thứ tự]]
*[[Duyệt cây|Duyệt hậu thứ tự]]
 
== Mã giả ==
<syntaxhighlight lang="c">
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
 
 
 
#define MaxLength 30
#define NIL -1 // khong ton tai nut
 
typedef char DataType;
typedef int Node;
typedef struct {
Node Parent[MaxLength]; // Luu tru cha cua nut
int MaxNode; // Luu tru nut hien tai tren cay
DataType Label[MaxLength]; // Luu tru nhan cua nut
}Tree;
 
 
 
 
// Tao cay rong
 
 
void MakeNull_Tree(Tree *T)
{
T->MaxNode=0;
 
 
}
 
 
// Kiem tra cay rong
 
int Empty_Tree(Tree T)
{
return (T.MaxNode)==0;
}
 
// Kiem tra cay day
 
int Full_Tree(Tree T)
{
return (T.MaxNode == MaxLength);
}
 
// Ham xac dinh cha cua nut n tren cay T
 
Node Parent(Node n, Tree T)
{
if ((Empty_Tree(T))||(n>T.MaxNode-1))
return NIL;
else return T.Parent[n];
}
 
 
// Ham xac dinh nhan cua nut n tren cay T
 
DataType Label(Node n,Tree T)
{
if ((Empty_Tree(T))||(n>T.MaxNode-1))
{
printf("Loi! Khong tim thay nhan!");
return '*';
}
else return T.Label[n];
}
 
 
// Ham tra ve nut goc trong cay T
 
Node Root(Tree T)
{
if(!Empty_Tree(T))
return 0;
else return NIL;
}
 
 
// Ham tra ve nut con trai nhat cua nut n trong cay T
 
Node LeftMostChild(Node n,Tree T)
{
Node i=n+1;
int found=0;
if ((n<0)||(Empty_Tree(T))||(n>=T.MaxNode-1))
return NIL;
else
{
while ((i<T.MaxNode)&&(found==0))
if (T.Parent[i]==n) found=1;
else i++;
if (found==0) return NIL;
else return i;
}
}
 
// Ham tra ve nut anh em ruot phai cua nut n tren cay T
 
Node RightSibling(Node n,Tree T)
{
Node i=n+1;
int found=0;
if (n<0) return NIL;
while ((i<=T.MaxNode-1)&&(found ==0))
if (T.Parent[n]==T.Parent[i])
found =1;
else i++;
if (found) return i;
else return NIL;
}
 
 
// Nhap cay
 
 
void ReadTree(Tree *T)
{
MakeNull_Tree(T);
int i=1,n=0;
// Nhap vao tong so nut cua cay cho den khi hop le
do
{
printf("\n\n Nhap vao tong so nut cua cay: ");
fflush(stdin);
scanf("%d",&n);
}
while ((n<1)||(n>MaxLength));
T->MaxNode=n;
// Nhap vao nut goc
printf("\n\n Nhap vao nut goc: ");
fflush(stdin); scanf("%c",&(*T).Label[0]);
T->Parent[0]=-1;
// Nhap cac nut con con lai
for (i=1;i<n;i++)
{
printf("Nhap vao nhan nut thu %d: ",i);
fflush(stdin); scanf("%c",&(*T).Label[i]);
printf("Nhap vao nut chua cua nut thu %d: ",i);
scanf("%d",&(*T).Parent[i]);
}
}
 
 
 
 
 
// Duyet tien tu
 
 
void PreOrder(Node n,Tree T)
{
Node i;
printf("%c",Label(n,T)); //Xu ly nut
i=LeftMostChild(n,T);
while (i!=NIL)
{
PreOrder(i,T);
i=RightSibling(i,T);
}
}
 
 
// Duyet trung tu
 
 
void InOrder(Node n,Tree T)
{
Node i=LeftMostChild(n,T);
if(i!=NIL) InOrder(i,T);
printf("%c",Label(n,T)); // Xy ly nut
i=RightSibling(i,T);
while(i!=NIL)
{
InOrder(i,T);
i=RightSibling(i,T);
}
}
 
// Duyet hau tu
 
void PostOrder(Node n,Tree T)
{
Node i;
i=LeftMostChild(n,T);
while (i!=NIL)
{
PostOrder(i,T);
i=RightSibling(i,T);
}
printf("%c",Label(n,T));
}
 
 
 
 
 
// Ham xac dinh bac cua nut n trong cay
 
int Nb_Child_Node(Node N,Tree T)
{
int kq=0;
Node i;
i=LeftMostChild(N,T);
while (i!=NIL)
{
kq++;
i=RightSibling(i,T);
}
return kq;
}
</syntaxhighlight>
 
== Các giải thuật chung ==