1
// ctdl.cpp : cac thao tac tim kiem tren danh sach don
//Anh Phi-K13T01
Code:
#include "stdafx.h"
#include <iostream.h>
Khai báo 1 danh sách liên kết:
struct Node
{
int key;
Node *next;
};
typedef Node *ref;
Khởi tạo 1 danh sách rỗng:
Code:
void init(ref &head)
{ head=NULL;
}
Cấp phát 1 node mới trong danh sách:
Code:
Node* New(int x){
ref p;
p=new Node;
if(p==NULL) return NULL;
p->key=x;
p->next=NULL;
return p;
}
Chèn phần tử vào đầu danh sách:
Code:
void InsertFirst(ref &head,int x)
{
ref p= new Node;
p->key=x;
p->next=head;
head=p;
}
Chèn phần tử vào danh sách chưa có thứ tự:
Code:
void InsertMiddle(ref q,int x)
{
ref p;
p=new Node;
p->key=x;
p->next=q->next;
q->next=p;
}
Thêm phần tử vào danh sách đã có thứ tự:
Code:
void InsertOrder(ref &head,int x)
{
ref q,p,r;
p=new Node;
p->key=x;
r=head;
int count=1;
while(r!=NULL && count)
if(r->key<x)
{
q=r;
r=r->next;
}
else count=0;
if(r==head)
head=p;
else p->next=q->next;
p->next=r;
}
Tìm phần tử x trong danh sách chưa có thứ tự:
Code:
ref search(ref &head,int x)
{
ref q;
q=head;
while(q!=NULL && q->key!=x)
q=q->next;
return q;
}
Tìm phần tử x trong danh sách đã có thứ tự:
Code:
ref search(ref &head,int x)
{
ref q;
q=head;
while(q!=NULL && q->key!=x&&q->key<x)
q=q->next;
if (q->key==x)return q;
else return NULL;
}
Xóa phần tử đầu tiên trong danh sách:
Code:
void DelFirst(ref &head)
{
ref q;
q=head;
head=q->next;
delete(q);
}
Xóa phần tử giữa và cuối danh sách:
Code:
void DelMiddleEnd(ref p)
{
ref q;
q=p->next;
p->next=q->next;
delete(q);
}
Xóa nodecó giá trị x:
Code:
void DelX(ref &head,int x)
{
ref q,p;
int Found=0;
q=head;
while(q!=NULL && !Found)
if(q->key!=x)
{
p=q;
q=q->next;
}
else Found=1;
if(Found)
{
if(q==head)
head=q->next;
else
p->next=q->next;
delete(q);
}
}
Xóa phần tử sau vị trí k(1 2 3 4 5)nhập vị trí k=2,xóa phần tử 4
Code:
void XoaPhanTuSauk(ref &head,int k)
{
ref r,p;
int count=0,found=0;
r=head;
while(r!=NULL&&found==0)
{
if(count==k)
{
p=r->next;
r->next=p->next;
delete(p);
found=1;
}
count++;
r=r->next;
}
}
Xóa toàn bộ danh sách:
Code:
void DelList(ref &head)
{
ref q=head;
while(q!=NULL)
{
DelFirst(head);
q=head;
}
}
Hiển thị danh sách liên kết đơn:
Code:
void Display(ref &head)
{
ref q;
q=head;
while(q!=NULL)
{
cout<<q->key<<" ";
q=q->next;
}
cout<<endl;
}
Hàm tính trung bình cộng của các node trong danh sách:
Code:
double TBC(ref &head)
{
int sum,count;
sum=count=0;
ref q=head;
while(q!=NULL)
{
sum+=q->key;
count++;
q=q->next;
}
if(count!=0)
return double(sum)/count;
else return 0.0;
}
Đếm số node có trong danh sách:
Code:
int DemPhantu(ref &head)
{
int count=0;
ref q=head;
while(q!=NULL)
{
count++;
q=q->next;
}
return count;
}
Kiểm tra số nguyên tố:
Code:
int KTSNT(int n){
if(n<2) return 0;
for(int i=2;i<=n/2;i++)
if(n%i==0) return 0;
return 1;
}
Đếm số nguyên tố:
Code:
int DemSNT(ref &head){
ref p=head;
int count=0;
if(p==NULL) return 0;
while(p!=NULL)
{ if(KTSNT(p->key)) count++;
p=p->next;
}
return count;
}
Tính trung bình số nguyên tố trong danh sách:
Code:
double TBSNT(ref &head)
{
ref p=head;
int Sum=0;
int count=0;
if(p==NULL) return 0.0;
while(p!=NULL){
if(KTSNT(p->key))
{ count++;
Sum+=p->key;
}
p=p->next;
}
if(count!=0) return (double)Sum/count;
else return 0.0;
}
Hoán đổi 2 node trong danh sách:
Code:
void HoanDoi(ref &head,ref &q,ref &r){
if(q!=NULL) // p q r
{
r=q->next;
if(q!=head)
{
ref p=head;
while(p->next!=q)
p=p->next;
p->next=q->next;
}
else head=q->next;
q->next=r->next;
r->next=q;
}
}
In số nguyên tố có trong danh sách :
Code:
void InSNT(ref &head)
{
ref p=head;
if(p==NULL) return;
while(p!=NULL){
if(KTSNT(p->key))
cout<<p->key<<" ";
p=p->next;
}
}
In đảo ngược danh sách (note:In lậu liên kết giữa các node chưa đảo ngươc được)
Pa kon nào làm được xin pm.
Code:
void InDaoNguoc(ref &head)
{ int dem=0,count=0;
ref p=head;
while(p!=NULL)
{ count++;
p=p->next;
}
ref q;
while(count>0)
{
if(dem>=0) q=head;
for(int i=0;i<count;i++)
if(i>0) q=q->next;
printf("%d\t",q->key);
count--;
dem++;
}
}
Chèn x vào giá trị chẵn đầu tiên trong danh sách:
Code:
void ChenVaoChanDau(ref &head,int x)
{
ref p=head;
if(p==NULL) InsertFirst(head,x);
int found=0;
while(p!=NULL&&found==0){
if(p->key%2==0)
{
InsertMiddle(p,x);
found=1;}
else p=p->next;
}
}
Tìm node la chẵn cuối cùng trong danh sách:
Code:
ref ChanCuoi(ref &head)
{
ref p=head;
ref q;
int found=0;
if(p==NULL) return NULL;
while(p!=NULL){
if(p->key%2==0){q=p;found=1;}
p=p->next;
}
if(found)return q;
else return NULL;
}
Xét xem danh sách tăng hay giảm hay không có thứ tự:
Code:
int XetDS(ref &head)
{
ref p,r;
p=head;
if(p==NULL) return 0;
r=p->next;
int count1=0;
int count2=0;
while(r!=NULL){
if(p->key<r->key) count1++;
else if(p->key>r->key) count2++;
else{ count1=0,count2=0;}
p=p->next;
r=p->next;
}
if(count1==DemPhantu(p)-1) return 1;//tang
if(count2==DemPhantu(p)-1) return 2;//giam
else return 0;
}
Tách danh sách ban đầu thành 2 danh sách con
danh sách 1:chứa các node là số nguyên tố.
danh sách 2:chứa các node còn lại.
Code:
void TachNT(ref head,ref &l1,ref &l2)
{
init(l1);
init(l2);
ref q,p=head;
if(p==NULL) return ;
while(p!=NULL){
int k=p->key;
q=New(k);
if(KTSNT(k))InsertFirst(l1,q->key);
else InsertFirst(l2,q->key);
p=p->next;
}
cout<<"
Danh sach so nguyen to:"<<endl;
Display(l1);
cout<<"
Danh sach so con lai:"<<endl;
Display(l2);
}
Tìm node x trong danh sách nếu tìm thấy thì tách danh sách ra thành 2 danh sách.
danh sách 1 là danh sách từ đầu đến vị trí node x.
danh sách 2 là danh sách tính từ vi trí node x đến cuối danh sách ban đầu.
Code:
void TachDSX(ref &head,ref &l,int x)
{
init(l);
ref q=head;
if(q==NULL) return;
q=search(head,x);
while(q!=NULL){
InsertFirst(l,q->key);
q=q->next;
}
ref r=q=search(head,x);
while(r!=NULL){
r=r->next;
DelX(head,q->key);
q=r;
}
cout<<"Dach sach tu dau den x:"<<endl;
Display(head);
cout<<"Dach sach x den cuoi danh sach:"<<endl;
InDaoNguoc(l);
}
Hàm main viết hơi tùm lum.
Bạn nào cần dùng hàm gì thì xây dựng lại hàm main ha...
//---------int main---------
Code:
int main(int argc, char* argv[])
{
int x;
ref head,head1,head2;
ref q,r;
cout<<"Nhap gia tri duong(am ket thuc):";
cin>>x;
init(head);
while(x>=0)
{
InsertFirst(head,x);
cout<<"Nhap gia tri duong(am ket thuc):";
cin>>x;
}
cout<<"Danh sach theo chieu nghich:"<<endl;
Display(head);
cout<<endl;
TachNT(head,head1,head2);
int c;cout<<"Nhap c can tim:";cin>>c;
cout<<endl;
TachDSX(head,head1,c);
cout<<"
Danh sach theo chieu thuan :"<<endl;
InDaoNguoc(head);
cout<<"
Cac so nguyen to trong danh sach:"<<endl;
InSNT(head);
int t;cout<<"
Nhap phan tu de chen vao phan tu chan dau tien=",cin>>t;
ChenVaoChanDau(head,t);
cout<<"
Chen "<<t<<" vao phan tu chan dau tien:"<<endl;
Display(head);*/
if(ChanCuoi(head)==NULL)cout<<"
Danh sach rong or khong co phan tu chan nao."<<endl;
else cout<<"
Chan cuoi trong danh sach="<<ChanCuoi(head)->key<<endl;
if(XetDS(head)==1) cout<<"
Tang"<<endl;
else if(XetDS(head)==2) cout<<"
Giam"<<endl;
else cout<<"
Khong Thu tu or danh sach rong."<<endl;
cout<<"
Trung binh cong cua cac phan tu trong danh sach:"<<TBC(head)<<endl;
cout<<"
So phan tu la so nguyen to="<<DemSNT(head)<<endl;
cout<<"
Trung binh cong cua cac phan tu la so nguyen to trong danh sach:"<<TBSNT(head)<<endl;
cout<<"
So phan tu trong danh sach la="<<DemPhantu(head)<<endl;
int y;cout<<"Nhap gia tri can xoa=",cin>>y;
DelX(head,y);
cout<<"Dang sach sau khi da xoa "<<y<<":"<<endl;
Display(head);
int z;cout<<"Nhap vi tri can xet=",cin>>z;
if(z<0||z>=DemPhantu(head)-1)
cout<<"
Sau vi tri "<<z<<" khong co phan tu hoac khong co trong mang!"<<endl;
else{
XoaPhanTuSauk(head,z);
cout<<"
Sau khi xoa phan tu sau vi tri "<<z<<":"<<endl;
Display(head);
}
cout<<"Nhap gia tri can tim:";
cin>>x;
q=search(head,x);
if(q!=NULL) //tim thay
{
cout<<"Nhap gia tri can them:";
cin>>x;
InsertMiddle(q,x);//chen phan tu q sau x
Display(head);
}
else cout<<"Khong tim thay!!!"<<endl;
//hoan doi 2 vi tri trong danh sach
HoanDoi(head,q,r);
cout<<"Danh sach sau khi hoan doi 2 vi tri vua nhap:"<<endl;
Display(head);
DelList(head);
if(head==NULL) cout<<"Xoa thanh cong"<<endl;
else cout<<"Khong thanh cong"<<endl;
return 0;
}
Danh Sách Liên Kết
Nguyễn Thanh Hiên
Danh Sách Liên Kết (Linked List)
• Gồm nhiều phần tử (gọi mỗi phần tử là
một node)
• Các phần tử nối kết với nhau thông qua
vùng liên kết
• Các phần tử được try xuất tuần tự và bao
gồm: vùng dữ liệu và các vùng liên kết
Ai
A node in a
linked list
A header node
A tail node
2
Các loại danh sách liên kết
• DSLK đơn
• DSLK kép
• DSLK vòng
A1 A2 A3 AN
A1 A2 A3 AN
A1 A2 A3 AN
Các Tác Vụ
• Khởi tạo (init)
• Kiểm tra DSLK rỗng (IsEmpty)
• Xác định kích thước (Size)
• Chèn (Insert)
• Xóa (Remove)
• Tìm kiếm (Retrieve)
• Thay thế (Replace)
• Duyệt (Traverse)
3
DSLK Đơn- Cấu trúc dữ liệu
• typedef struct node{
T info; // T là kiểu đã định nghĩa trước
struct node* link; // con trỏ chỉ đến cấu trúc node
}NODE;
• T là kiểu dữ liệu cơ bản hoặc kiểu dữ liệu
tự định nghĩa
DSLK Đơn- Cấu trúc dữ liệu
• typedef struct node
{
int info;
struct node* link;
}NODE; CTDL cho một
phần tử của DS
các số nguyên
4
DSLK Đơn- Cấu trúc dữ liệu
• typedef struct SinhVien
{
char Ten[30];
int MaSV;
}SV;
• typedef struct svNode
{
SV info;
struct svNode* link;
}SVNODE;
CTDL cho một
phần tử của DS
các sinh viên
DSLK Đơn- Cấu trúc dữ liệu
• typedef struct phanso
{
int tu;
int mau;
}PS;
• typedef struct psNode
{
PS info;
struct psNode* link;
}PSNODE;
CTDL cho một
phần tử của DS
các phân số
5
DSLK Đơn- Cấu trúc dữ liệu
• typedef struct
{
NODE* pHead;
NODE* pTail;
} LIST;
pHead
pTail
A1 A2 A3 AN
DSLK Đơn- Các Tác Vụ
• Khởi tạo DS
void init (LIST &list){
list.pHead=NULL;
list.pTail=NULL;
}
6
DSLK Đơn- Các Tác Vụ
• Tạo một Node mới cho DS
NODE* getNode(T x){
NODE* p;
p=new NODE;
if (p==NULL)
return NULL;
p-> info = x;
p-> link=NULL;
return p;
}
x
DSLK Đơn- Các Tác Vụ
• Chèn một phần tử vào DS
- Chèn vào đầu (insertHead)
- Chèn vào cuối (insertTail)
- Chèn sau phần tử q (insertMid)
7
DSLK Đơn- Các Tác Vụ
• Chèn vào đầu (insertHead)
A1 A2 A3 AN
pTail
pHead
x
newNode
(2) (1)
DSLK Đơn- Các Tác Vụ
• Chèn vào đầu (insertHead)
void insertHead(LIST &ds, NODE* newNode)
{
if (ds.pHead==NULL) //ds rỗng
{
ds.pHead = newNode; ds.pTail = ds.pHead;
}
else
{
newNode ->link = ds.pHead;
ds.pHead = newNode;
}
}
8
DSLK Đơn- Các Tác Vụ
• Chèn vào cuối (insertTail)
pHead
pTail
A1 A2 A3 AN
x
(1)
(2)
DSLK Đơn- Các Tác Vụ
• Chèn vào cuối (insertTail)
void insertTail(LIST &ds, NODE *newNode)
{
if (ds.pHead==NULL)
{
ds.pHead = newNode; ds.pTail = ds.pHead;
}
else
{
ds.pTail->link = newNode;
ds.pTail = newNode;
}
}
9
DSLK Đơn- Các Tác Vụ
• Chèn sau phần tử q (insertMid)
pHead
pTail
A1 A2 A3 AN
x
(2) (1)
q
DSLK Đơn- Các Tác Vụ
• Chèn sau phần tử q (insertMid)
void insertMid(LIST &ds,NODE *q, NODE* newNode)
{
if ( q!=NULL)
{
newNode ->link = q-> link;
q-> link = newNode;
if(q == ds.pTail)
ds.pTail = newNode;
}
else //chèn vào đầu danh sách
insertHead(ds, newNode);
}
10
DSLK Đơn- Các Tác Vụ
• Tìm một phần tử trong DS
NODE * Retrieve(LIST ds, Data k)
{
NODE *p;
p = ds.pHead;
while((p!= NULL)&&(p->info != x))
p = p->link;
return p;
}
DSLK Đơn- Các Tác Vụ
• Duyệt DS
void * Traverse(LIST ds)
{
NODE *p;
p = ds.pHead;
while(p!= NULL){
process(p);
p = p->link;
}
}
11
DSLK Đơn- Các Tác Vụ
• Xoá một phần tử
- Xoá phần tử đầu
- Xoá phần tử sau phần tử q
- Xoá phần tử có khoá k
DSLK Đơn- Các Tác Vụ
• Xoá phần tử đầu
A1 A2 A3 AN
pTail
pHead
12
DSLK Đơn- Các Tác Vụ
• Xoá phần tử đầu
Data RemoveHead(LIST &ds)
{
NODE *p;
Data x = NULLDATA;
if ( ds.pHead != NULL)
{
p = ds.pHead; x = p->info;
ds.pHead = ds.pHead->link;
delete p;
if(ds.pHead == NULL) ds.pTail = NULL;
}r
eturn x;
}
DSLK Đơn- Các Tác Vụ
• Xoá phân ftử sau phần tử q
A1 A2 A3 AN
pTail
pHead
q p
13
DSLK Đơn- Các Tác Vụ
• Xoá phần tử sau phần tử q
void RemoveAfter (LIST &ds, NODE *q)
{ NODE *p;
if ( q != NULL)
{
p = q ->link ;
if ( p != NULL)
{
if(p == ds.pTail) ds.pTail = q;
q->link = p->link;
delete p;
}
}
else
RemoveHead(ds);
}
DSLK Đơn- Các Tác Vụ
• Xoá phần tử có khoá k
int RemoveNode(LIST &ds, Data k)
{
NODE *p = ds.pHead;
NODE *q = NULL;
while( p != NULL)
{
if(p->info == k) break;
q = p; p = p->link;
}
if(p == NULL) return 0;
//Không tìm thấy k
if(q != NULL)
{
if(p == ds.pTail)
ds.pTail = q;
q->link = p->link;
delete p;
}
else //p là phần tử đầu ds
{
ds.pHead = p->link;
if(ds.pHead == NULL)
ds.pTail = NULL;
}
return 1;
}
14
DSLK Đơn- Hủy danh sách
void ReamoveList(LIST &ds)
{ NODE *p;
while (ds.pHead!= NULL)
{
p = ds.pHead;
ds.pHead = p->link;
delete p;
}
ds.pTail = NULL;
}
DSLK Kép- Cấu trúc dữ liệu
typedef struct DNode
{
T info;
struct DNode* pPre;
struct DNode* pNext;
}DNODE;
15
DSLK Kép- Cấu trúc dữ liệu
DNODE* GetNode(T x)
{
DNODE *p;
p = new DNODE;
if ( p==NULL) return NULL
p ->Info = x;
p->pPrev = NULL;
p->pNext = NULL;
return p;
}
DSLK Kép- Insert
• Chèn đầu
• Chèn cuối
• Chèn sau phần tử q
• Chèn trước phần tử q
16
DSLK Kép- Insert
DSLK Kép- Insert
void Insert(DLIST &ds, DNODE* q, DNODE* newNode)
{ DNODE* p = q->pNext;
if ( q!=NULL) {
newNode->pNext = p; //(1)
newNode->pPrev = q; //(2)
q->pNext = newNode; //(3)
if(p != NULL)
p->pPrev = newNode; //(4)
if(q == ds.pTail)
ds.pTail = newNode;
}
else //chèn vào đầu danh sách
InsertHead(ds, newNode);
}
17
DSLK Kép- Remove
• Xóa đầu
• Xóa cuối
• Xóa sau phần tử q
• Xóa trước phần tử q
• Xóa có khóa k
DSLK Kép- Remove sau q
void Remove(DLIST &ds, DNODE *q)
{ DNODE *p;
if ( q != NULL)
{
p = q ->pNext ;
if ( p != NULL)
{
q->pNext = p->pNext;
if(p == ds.pTail) ds.pTail = q;
else p->pNext->pPrev = q;
delete p;
}
}
else
RemoveHead(ds);
}
18
STACK
56
31
29
179
52
21 Bottom_of_stack
(this is where the
stack started)
Empty/unfilled
portion of stack
Direction
in which
stack grows
•Danh sách hạn chế
•Các phần tử được
thêm vào và lấy ra ở
đỉnh stack
• Hiện thực dùng dslk
hoặc array
Stack - Tác vụ
• Init()
• Push()
• Pop()
• IsEmpty()
• IsFull()
typedef struct {
T *theArray;
int size;
}STACK;
void init (STACK &s, int size) {
s.size = size;
s.theArray = new T[size];
s.top = -1;
}
19
Stack- Push()
void push(STACK &s, T x){
if (!isFull(s)){
s.top++;
s.theArray[s.top]=x;
}
}
bool isFull(STACK s) {
if(s.top < s.size-1) return false;
else return true;
}
Stack- Pop(), Top()
T pop(STACK &s){
if (!isEmpty(s))
return s.theArray[s.top--];
}
T top(STACK s){
return s.theArray[s.top];
}
bool isEmpty(STACK s) {
if(s.top == -1) return true;
else return false;
}
20
Stack-Ví dụ
56
31
29
179
52
21
56
31
29
179
21
56
31
29
179
2
21
push(2)
56
31
29
179
2
21
Return 2
Return 52
Queue
• Danh sách hạn chế
• Chèn vào một đầu, lấy ra ở đầu kia
• Hiện thực dùng dslk hoặc array
• Linear and Circular Queues
front back empty portion
of the queue
12 31 79 5 63
21
Queue-Tác vụ
• EnQueue()
Input: element to be enqueued
Algorithm:
increment back by 1
add element to the empty location pointed to by back
Return: void
• DeQueue()
Input: void
Algorithm:
return the element pointed to by front
increment front by 1
Return: the element dequeued
Queue - Ví dụ
front back
12 31 79 5 63
front back
12 31 79 5 63 17
front back
31 79 5 63 17
front back
31 79 5 63 17 52
front back
79 5 63 17 52
enqueue(17)
dequeue
enqueue(52)
dequque
22
Queue - Ví dụ
front back
79 5 63 17
front back
79 5 63 17 52 enqueue(23)
dequeue
52 23
back
5 63 17 52 23
front
back
63 17 52 23
front
17 52 23
front back
dequeue
dequeue
enqueue(44):
QUEUE_FULL
Circular Queue
23
Circular Queue
• In enqueue:
back = (back +1) mod ARRAY_SIZE
• In dequeue:
front = (front + 1) mod ARRAY_SIZE
Ghi chú: back giữ vị trí phần tử có
giữ liệu
front giữ vị trí phần tử không có giữ
liệu
Circular Queue - ĐK Rỗng
DeQueue-> Queue empty: back == front
24
Circular Queue - ĐK Đầy
EnQueue-> Queue full:
(back +1)%size == front
Circular Queue
typedef struct {
int size;
int front;
int back;
T* values;
} QUEUE;
25
Circular Queue
void init(QUEUE &q, int size) {
q.size = size;
q.values = new T[size];
q.front = 0;
q.back = 0;
}
Circular Queue
bool isFull(QUEUE q) {
if( (q.back+1)% q.size == q.front) return true;
else return false;
}
bool isEmpty(QUEUE q) {
if(q.back == q.front) return true;
else return false;
}
26
Circular Queue
void enqueue(QUEUE &q,T x) {
if(!isFull(q)) {
q.back = (q.back+1) % q.size;
q.values[q.back] = x;
}
}
T dequeue(QUEUE &q) {
if(!isEmpty(q)) {
q.front = (q.front+1) % q.size;
return values[q.front];
}
return NULLDATA;
}
CÂY
A
B C D E F
G H I J K L
T1 leaf T3 T5
T2 T4
edge
• Cây N node sẽ có N-1 cạnh
subtree
Path: n1->nk là một chuỗi các nút n1 ->nk sao cho ni là cha ni+1, 1 <= i <=k
depth
27
CÂY
A
B C D E F
G H I J K L
T1 leaf T3 T5
T2 T4
depth
Cây nhị phân là cây
mà mỗi nút có tối
đa hai nút con
CÂY NHỊ PHÂN
28
CÁC PHÉP DUYỆT
• PreOrder
- Duyệt gốc
- Duyệt các cây con bên trái
- Duyệt cây con bên phải
• InOrder
- Duyệt cây con bên trái
- Duyệt gốc
- Duyệt cây con bên phải
• PostOrder
- Duyệt cây con bên trái
- Duyệt cây con bên phải
- Duyệt gốc
CÂY NHỊ PHÂN- CTDL
typedef struc TNode{
T info;
TNode* left;
TNode* right;
}TNODE;
TNODE *root=NULL;
29
CÂY NHỊ PHÂN- Duyệt
void PreOrder(TNODE *root){
if (root!=NULL){
process(root);
PreOrder(roo->left);
PreOrder(root->right);
}
}
void InOrder(TNODE *root){
if (root!=NULL){
InOrder (root->left);
process(root);
InOrder (root->right);
}
}
void PostOrder(TNODE *root){
if (root!=NULL){
PostOrder (root->left);
PostOrder (root->right);
process(root);
}
}
VÍ DỤ
• Cho cây nhị phân, mỗi nút có info (không trùng
nhau) là một số nguyên
- Đếm số nút trên cây
- Tính tổng các info trên cây
- Cho biết tổ tiên của nút có info là x
- Cho biết info các nút ở mức 3
- Cho biết tổng info trên cây
- Cho biết các nút có tổng info các conlà bội số của info
của cha nó
- Cho biết tổng số nút lá
- Cho biết tổng số nút bậc một
- Cho biết cây có bị suy biến không
30
LAN TRUYỀN THÔNG TIN
• Tham số
- Tham biến
- Tham trị
• Hỏi-đáp
Hỏi
a
Hỏi
a, b
CÂY NHỊ PHÂN TÌM KIẾM (BST)
31
BST-Retrieval
TNODE* Retrieval(TNODE* root, T x){
if (root != NULL) {
If (root->info==x) return root;
if (x < root->info)
return Retrieveal (root->left, x);
else
return Retrieveal (root->right, x);
}
return NULL;
}
BST-Retrieval
x
32
BST-Insert
• Tạo BSTvới các info: 5 9 7 3 8 12 6 4 20
BST-Insert
33
BST-Insert
BST-Insert
34
BST-Insert
int Insert(TNODE*& root, T x)
{
if (root != NULL) {
if (root->info==x) return 0;
if (x < root ->info)
return Insert(root ->left, x);
else
return Insert(root ->right, x);
}r
oot = new TNODE;
If (root==NULL) return -1
root ->right = NULL;
root ->left = NULL:
root ->info = x;
return 1;
}
Bạn đang đọc truyện trên: Truyen2U.Pro