Ôn tập tốt nghiệp TC38, NC3 (2012)

Các môn: 1) Phƣơng pháp lập trình (1t) 2) Cấu trúc dữ liệu và giải thuật (2t) 3) Hệ cơ sở dữ liệu (2t) ÔN TẬP TỐT NGHIỆP TC38, NC3 (2012) GV: Bùi Thị Hạnh Tổ Công nghệ Thông tin Khoa Công nghệ Ngày 24/6/2012 1 I. Kiểu dữ liệu cơ bản trong C++ II. Cấu trúc điều khiển III. Các kiểu dữ liệu có cấu trúc PHƢƠNG PHÁP LẬP TRÌNH 2 I. Kiểu dữ liệu cơ bản Tên kiểu Kthước Miền giá trị Ghi chú Char 01 byte -128 đến 127 Có thể dùng như số nguyên 1 byte có dấu hoặc kiểu ký tự unsign char 01 byte 0 đến 255 Số nguyên 1 byte không dấu Int 02 byte -32738 đến 32767 unsign int 02 byte 0 đến 65335 Có thể gọi tắt là unsign Long 04 byte -232 đến 231 -1 unsign long 04 byte 0 đến 232-1 Float 04 byte 3.4E-38  3.4E38 Giới hạn chỉ trị tuyệt đối.Các giá trị <3.4E-38 được coi = 0. Tuy nhiên kiểu float chỉ có 7 chữ số có nghĩa. Double 08 byte 1.7E-308  1.7E308 long double 10 byte 3.4E-4932 1.1E4932 Ép kiểu  Thường sử dụng khi gán biểu thức gồm các toán hạng khác kiểu. Vd:  Muốn có giá trị chính xác trong phép chia hai số nguyên cần dùng phép ép kiểu : ((float)a)/b  Để đổi giá trị thực r sang nguyên, ta dùng : (int)(r+0.5) 4 Các toán tử đặc biệt  Toán tử tăng giảm k=5;++k + 10 ;// được 16 k++ +10; //được 15 --k+10; //được 14 k--+10; //được 15  Toán tử điều kiện toán hạng 1 ? toán hạng 2 : toán hạng 3 Vd: int m = 1, n = 2; int min = (m < n ? m : n); // min nhận giá trị 1  Toán tử sizeof(x): Trả lại số bye mà x chiếm trong bộ nhớ 5 II. Cấu trúc điều khiển  Tuần tự  Phân nhánh Không điều kiện : goto , break , continue , return Có điều kiện : if ; switch  Lặp :  for while  do … while 6 Goto  Lệnh nhảy goto là một lệnh nhảy đơn giản, cho phép chương trình nhảy vô điều kiện tới một vị trí trong chương trình thông qua tên nhãn  Cách sử dụng lệnh goto: Tạo một nhãn goto đến nhãn 7 main() { int i = 0; lap: // nhãn cout<<i<<“:”; i++; if ( i < 10 ) goto lap; // nhãy về nhãn lap return 0; } i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7 i:8 i:9 8 Câu lệnh if if (biểu thức điều kiện) { .... } [else { ... }] 9 int s; s = 3; s += 1; if (s > 5) { cout<<s; } else { cout<<s * 10; } 10 Câu lệnh switch switch (biểu thức điều kiện) { case : [default: ] } 11 int diem=7; switch (diem) { case 3: { cout<<"Yeu"; break; } case 5: { cout<<"Trung binh"; break; } default: { cout<<"Khong biet"; break; } } 12 Câu lệnh for for ([ phần khởi tạo] ; [biểu thức điều kiện]; [bước lặp]) { ; ; ; } 13 for (int i = 2; i < 10; i++) { for (int j = 1; j <= 10; j++) { cout<<i<<"x“<<j<<"=“<<i*j<<" \n "); } } 14 Câu lệnh while while (Biểu thức) { ; ; ; } true false Các câu lệnh thực hiện Điều kiện 15 char pass = "ABCD"; char chuoi[5]; int solan; solan = 0; while (solan < 3) { cout<<"Nhap pass : "; gets(chuoi); if strcmp(chuoi, pass) { cout<<"Dung roi"; solan = 4; } else { cout<<"Sai roi"; solan += 1; } } 16 Câu lệnh do/while do { ; ; ; } while ( điều kiện ) true false Các câu lệnh thực hiện Điều kiện 17 main() { int i = 11; do { cout<<i; i++; } while ( i < 10 ); } 18 III. Kiểu dữ liệu có cấu trúc 1. Kiểu chuỗi ký tự: Chuỗi ký tự trong C được cấu trúc như một chuỗi liên tiếp các ký tự kết thúc bằng ký tự có mã ASCII bằng 0 (NULL character). Như vậy, giới hạn chiều dài của một chuỗi ký tự trong C là 1 Segment (tối đa chứa 65335 ký tự), ký tự đầu tiên được đánh số là ký tự thứ 0. char S[10]; //Khai báo một chuỗi ký tự S có chiều dài // tối đa 10 (kể cả kí tự kết thúc) char S[]="ABC";// Khai báo một chuỗi ký tự S có chiều // dài bằng chiều dài của chuỗi "ABC" // và giá trị khởi đầu của S là "ABC" 19 2. Kiểu mảng: Kiểu dữ liệu mảng là kiểu dữ liệu trong đó mỗi phần tử của nó là một tập hợp có thứ tự các giá trị có cùng cấu trúc được lưu trữ liên tiếp nhau trong bộ nhớ. Mảng 1 chiều: [<Số phần tử>]; Ví dụ int a[100]; int a[5] = (1, 7, -3, 8, 19); int a[] = (1, 7, -3, 8, 19); Mảng 2 chiều hay nhiều chiều: [][]...; int a[100][150]; int a[][]={{1, 7, -3, 8, 19}, {4, 5, 2, 8, 9}, {21, -7, 45, -3, 4}}; 20 3. Kiểu cấu trúc là kiểu dữ liệu mà trong đó mỗi phần tử của nó là tập hợp các giá trị có thể khác cấu trúc. typedef struct { ; ; … }[]; Vd: struct nguoi {char HoTen[35]; int NamSinh; char NoiSinh[40]; char GioiTinh; char DiaChi[50]; char Ttgd; }NGUOI; 21 4. Kiểu con trỏ * Vd: int a, b, *pa, *pb; =& định vị con trỏ đến địa chỉ của một biến đang làm việc. * nội dung ô nhớ. 22 int main() { int a=2,b=3,c=4; int *x=&a; //x=2 int *y; *x=11; //a=11 y=&c; //y=4 c++; //c=5, y=5 x=&b; //x=3 b--;//b=2, x=2 cout<<a<<” “<<b<<endl; cout<<*x<<” “<<*y<<endl; return 0; } 11 2 2 5 23 Con trỏ và mảng * Con trỏ và mảng 1 chiều: //nhập phần tử mảng for(i=0;i<n;i++) { cout<<"Phan tu thu “<<i<<“:”;cin<<a+i; } //in ra mảng for(i=0;i<n;i++) cout<<*(a+i)<<“ “; * Con trỏ và mảng 2 chiều float *pa= (float*) calloc(m*n,sizeof(float)); Để truy nhập đến phần tử pa[i][j] trong thân hàm, dùng công thức: *(pa+ i*n + j) //n là số cột 24 Con trỏ và tham chiếu của hàm Khi nào sử dụng đối con trỏ (tham chiếu) Khi muốn bảo lƣu lại kết quả tính toán đƣợc của các đối số trong hàm để sử dụng cho chƣơng trình gọi hàm có đối số thì chúng ta phải khai báo đối số của hàm là tham chiếu (con trỏ hay dạng địa chỉ). 25 #include #include void HoanVi(int *a, int *b) { int c=*a; *a=*b; *b=c; } int main() { int m=20,n=30; clrscr(); cout<<"Truoc khi goi ham m=“<<m<<“ n=“<<n; HoanVi(&m,&n); cout<<"Sau khi goi ham m=“<<m<<“ n=“<<n; getch(); return 0; } 26 Con trỏ và cấu trúc -> (*). Ví dụ: struct Diem diemA={0,0}; struct Diem *pDiem; pDiem = &diemA; pDiem -> x = 5; (*pDiem). y = 10; 27 I. Các giải thuật tìm kiếm II. Các giải thuật sắp xếp III. Đệ quy IV. Danh sách đặc V. Danh sách liên kết đơn VI. Ngăn xếp (Stack) – Hàng đợi (Queue) VII. Danh sách liên kết đôi VIII. Cây nhị phân IX. Cây nhị phân tìm kiếm CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 28 I. Các giải thuật tìm kiếm  Tìm tuần tự (Tìm tuyến tính) (Linear Search) int LinearSearch (int a[], int n, int x) { int k = 0; a[n]=x; while (a[k] != x) k++; if (k <n) return (k);// trả về vị trí tìm thấy else return (-1); } 29  Tìm nhị phân (Binary Search) int BinarySearch( int a[], int n, int x) { int left=0, right=n-1, mid; do { mid=(left+right)/2; if(x==a[mid]) return(mid); if(x<a[mid]) right=mid-1; else left=mid+1; } while(left<=right); return (-1); } 30 II. Các giải thuật sắp xếp 1. Đổi chỗ (Interchange Sort) 2. Nổi bọt (Bubble Sort) 3. Chèn (Insertion Sort) 4. Chọn (Selection Sort) 5. Nhanh (Quick Sort) 31 1. Interchange Sort  Đi từ đầu tiên, nếu có phần tử nào sau nó nhỏ hơn thì thực hiện đổi chỗ.  void InterchangeSort(int a[], int N ) { int i, j; for (i = 0 ; i<N-1 ; i++) for (j =i+1; j < N ; j++) if(a[j ]< a[i]) // nếu có sự sai vị trí thì đổi chỗ Doicho(a[i],a[j]); } 32 33 Interchange Sort – Ví dụ 2 8 5 1 6 4 15 12 2 3 4 5 6 7 8 1 i j 1 34 Interchange Sort – Ví dụ 12 8 5 2 6 4 15 1 2 3 4 5 6 7 8 1 i j 2 35 Interchange Sort – Ví dụ 2 12 8 5 6 4 15 1 2 3 4 5 6 7 8 1 i j 4 36 Interchange Sort – Ví dụ 2 4 12 8 6 5 15 1 2 3 4 5 6 7 8 1 i j 5 37 Interchange Sort – Ví dụ 2 4 5 6 8 12 15 1 2 3 4 5 6 7 8 1 2. Buble Sort  Xuất phát từ cuối dãy đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đúng đầu dãy hiện hành  void BubleSort(int a[], int n) { int i, j; for (i = 0 ; i<n-1 ; i++) for (j =n-1; j >i ; j --) if(a[j]< a[j-1])// nếu sai vị trí thì đổi chỗ Doicho(a[j],a[j-1]); } 38 39 Bubble Sort – Ví dụ 2 8 5 1 6 4 15 12 2 3 4 5 6 7 8 1 i j 1 40 Bubble Sort – Ví dụ 12 2 8 5 4 6 15 1 2 3 4 5 6 7 8 1 i j 2 41 Bubble Sort – Ví dụ 2 12 4 8 5 6 15 1 2 3 4 5 6 7 8 1 i j 4 42 Bubble Sort – Ví dụ 2 4 12 8 5 6 15 1 2 3 4 5 6 7 8 1 i j 5 43 Bubble Sort – Ví dụ 2 4 5 12 8 6 15 1 2 3 4 5 6 7 8 1 i j 6 44 Bubble Sort – Ví dụ 2 4 5 6 12 8 15 1 2 3 4 5 6 7 8 1 i j 8 45 Bubble Sort – Ví dụ 2 4 5 6 8 12 15 1 2 3 4 5 6 7 8 1 i j 3. Insertion Sort  Giả sử có một dãy a1 , a2 ,... ,an trong đó i phần tử đầu tiên a1 , a2 ,... ,ai-1 đã có thứ tự.  Tìm cách chèn phần tử ai vào vị trí thích hợp của đoạn đã được sắp để có dãy mới a1 , a2 ,... ,ai trở nên có thứ tự. 46 47 Insertion Sort – Ví dụ 2 8 5 1 6 4 15 12 2 3 4 5 6 7 8 1 48 2 8 5 1 6 4 15 12 i x 2 3 4 5 6 7 8 1 pos 2 Insertion Sort – Ví dụ Insert a2 into (1, 2) 49 12 8 5 1 6 4 15 2 i x 2 3 4 5 6 7 8 1 pos Insertion Sort – Ví dụ Insert a3 into (1, 3) 8 50 8 12 5 1 6 4 15 2 i x 2 3 4 5 6 7 8 1 pos Insertion Sort – Ví dụ Insert a4 into (1, 4) 5 51 5 8 12 1 6 4 15 2 i x 2 3 4 5 6 7 8 1 pos Insertion Sort – Ví dụ Insert a5 into (1, 5) 1 52 2 5 8 12 6 4 15 1 i x 2 3 4 5 6 7 8 1 pos Insertion Sort – Ví dụ Insert a6 into (1, 6) 6 53 2 5 6 8 12 4 15 1 i x 2 3 4 5 6 7 8 1 pos Insertion Sort – Ví dụ Insert a7 into (1, 7) 4 54 2 4 5 6 8 12 15 1 i x 2 3 4 5 6 7 8 1 pos Insertion Sort – Ví dụ Insert a8 into (1, 8) 55 2 4 5 6 8 12 15 1 pos 2 3 4 5 6 7 8 1 Insertion Sort – Ví dụ 4. Selection Sort  Chọn phần tử nhỏ nhất trong N phần tử ban đầu  Đưa phần tử này về vị trí đúng là đầu dãy hiện hành  Xem dãy hiện hành chỉ còn N-1 phần tử của dãy ban đầu  Bắt đầu từ vị trí thứ 2;  Lặp lại quá trình trên cho dãy hiện hành... đến khi dãy hiện hành chỉ còn 1 phần tử 56 57 Selection sort – Ví dụ 2 8 5 1 6 4 15 12 i min 2 3 4 5 6 7 8 1 Find MinPos(1, 8) Swap(ai, amin) 58 Selection sort – Ví dụ 2 8 5 12 6 4 15 1 i min 2 3 4 5 6 7 8 1 Find MinPos(2, 8) Swap(ai, amin) 59 Selection sort – Ví dụ 2 8 5 12 6 4 15 1 i min 2 3 4 5 6 7 8 1 Find MinPos(3, 8) Swap(ai, amin) 60 Selection sort – Ví dụ 2 4 5 12 6 8 15 1 i min 2 3 4 5 6 7 8 1 Find MinPos(4, 8) Swap(ai, amin) 61 Selection sort – Ví dụ 2 4 5 12 6 8 15 1 i min 2 3 4 5 6 7 8 1 Find MinPos(5, 8) Swap(ai, amin) 62 Selection sort – Ví dụ 2 4 5 6 12 8 15 1 i min 2 3 4 5 6 7 8 1 Find MinPos(6, 8) Swap(ai, amin) 63 Selection sort – Ví dụ 2 4 5 6 8 12 15 1 i min 2 3 4 5 6 7 8 1 Find MinPos(7, 8) Swap(ai, amin) 5. QuickSort  Sau khi thöïc hieän phaân hoaïch, daõy ban ñaàu ñöôïc phaân thaønh 3 ñoaïn:  a k < x , vôùi k = 0 .. (j-1)  a k = x , vôùi k = (j+1) .. (i-1)  a k > x , vôùi k = i..n  Ñeå saép xeáp caùc ñoaïn 1 vaø 3, ta laàn löôït tieán haønh vieäc phaân hoaïch töøng daõy con theo cuøng phöông phaùp phaân hoaïch daõy ban ñaàu vöøa trình baøy 64 65 Quick sort – Ví duï 2 8 5 1 6 4 15 12 2 3 4 5 6 7 8 1 left right 5 X STOP Not less than X i j STOP Not greater than X Phân hoạch dãy 66 Quick sort – Ví duï 2 8 5 1 6 12 15 4 2 3 4 5 6 7 8 1 left right 5 X STOP Not less than X i j STOP Not greater than X Phân hoạch dãy 67 Quick sort – Ví duï 2 1 5 8 6 12 15 4 2 3 4 5 6 7 8 1 left right i j 68 6 X Quick sort – Ví duï 2 4 5 8 6 12 15 1 2 3 4 5 6 7 8 1 left right i j STOP Not less than X STOP Not greater than X Sắp xếp đoạn 3 Phân hoạch dãy 69 Quick sort – Ví duï 2 4 5 6 8 12 15 1 2 3 4 5 6 7 8 1 left right i j Sắp xếp đoạn 3 III. Đệ quy Chương trình đệ qui gồm hai phần chính:  Phần neo: Điều kiện thoát khỏi đệ qui  Phần đệ quy: Trong phần thân chương trình có lời gọi đến chính bản thân chương trình với giá trị mới của tham số nhỏ hơn giá trị ban đầu 70  Cho hàm sau: int Func( int n ) { if (n == 5) return 5; else return 2 * Func(n + 1); } Cho biết kết quả khi gọi hàm Func(2) ? 71 IV. Danh sách đặc  Danh sách đặc là danh sách mà không gian bộ nhớ lưu trữ các phần tử nằm kề cận nhau trong bộ nhớ.  Sử dụng kiểu mảng để định nghĩa danh sách đặc.  Khai báo: VD: # define MaxLen 1000 //chiều dài tối đa int n; //chiều dài thực int a[MaxLen]; //khai báo danh sách a là 1 mảng với MaxLen phần tử tối đa 2 1 4 7 4 8 3 6 4 7 0 1 2 3 4 5 6 7 8 9 72 Các thao tác trong danh sách đặc  Thêm 1 phần tử vào danh sách tại vị trí pos  Hủy 1 phần tử khỏi danh sách  Tìm kiếm  Sắp xếp  Tách 73 Thêm 1 phần tử x vào ds tại vị trí pos  Kiểm tra chiều dài thực có = chiều dài tối đa?  Thực hiện đi từ cuối danh sách đến vị trí pos, gán giá trị thứ a[i]=a[i-1];  Đến vị trí pos, gán: a[pos]=x; chiều dài thực tăng lên 1. int Themphantu(int M[], int &n, int x, int pos) { if (Len == MaxLen) return (-1); for (int i= n; i >pos; i--) a[i] = a[i-1]; a[pos] = x; n++; return (n); } 74 Hủy 1 phần tử trong ds có vị trí del  Kiểm tra ds có rỗng và del>chiều dài thực?  Thực hiện đi từ vị trí del đến cuối dãy, gán giá trị a[i] cho giá trị đứng sau nó a[i+1];  Chiều dài thực giảm 1. int Xoaphantu(int a[], int &n, int del) { int (n ==0 || del >=Len) return (-1); for (int i =del; i<n-1; i++) a[i] = a[i+1]; n --; return (n); } 75 V. DSLK đơn( Singly Linked List)  DSLK đơn là chuỗi các node, được tổ chức theo thứ tự tuyến tính  Mỗi node gồm 2 phần:  Phần Data, information :lưu trữ các thông tin về bản thân phần tử.  Phần link hay con trỏ : lưu trữ địa chỉ của phần tử kế tiếp; nếu là cuối ds thì =NULL. Data Link Node 76 Khai báo typedef struct Node { int data; NODE * link; }NODE; typedef struct List { NODE* first; NODE* last; }LIST; 77 Các thao tác  Tạo 1 nút  Thêm 1 nút vào danh sách  Xóa 1 nút khỏi danh sách  Duyệt danh sách 78 Tạo 1 nút DSLK đơn NODE *GetNode(int x) { NODE *p; // Cấp phát vùng nhớ cho phần tử p = (NODE*)malloc(sizeof(NODE))//p= new NODE; if (p==NULL) { cout<<“Khong du bo nho!”; exit(1); } p->data = x; // Gán thông tin cho phần tử p p->link = NULL; return p; } 79 Thêm 1 nút vào đầu DSLK đơn new_ele->link = l.first; l.first = new_ele; A B C D E first last X new_ele 80 Thêm 1 nút vào cuối DSLK đơn l.last->link = new_ele; l.last = new_ele ; A B C D E first last X new_ele 81 Chèn 1 nút sau nút q new_ele->link = q->link; q->link = new_ele; A B C D E first last X new_ele q q->link 82 Xóa 1 nút đầu DSLK đơn if (l.first !=NULL) { NODE* p=l.first; l.first=p->link; if(l.first == NULL) l.last=NULL;//Nếu ds rỗng free(p); //delete p; } A B C D E first last p 83 Xóa 1 nút sau nút q trong DSLK đơn if(q !=NULL && q->link !=NULL) { NODE* p = q->link; q->link = p->link; if(p==l.last) l.last=q; free(p); } A B C D E first last q p 84 Duyệt DSLK đơn NODE* p=l.first; while(p!=NULL) { coutdata<<“\t”; p=p ->link; //trỏ đến phần tử kế tiếp } 85 VI. Ngăn xếp (Stack) – Hàng đợi (Queue)  Stack là cấu trúc dữ liệu làm việc theo cơ chế LIFO (Last In First Out)  Việc thêm (push) hoặc lấy (pop) thực hiện theo cơ chế Vào sau Ra trước và thực hiện tại 1đầu của Stack.  Hiện thực Stack có thể có thể dùng kiểu mảng hoặc DSLK Stack 86 Hàng đợi (Queue) 87  Queue là cấu trúc dữ liệu làm việc theo cơ chế LIFO (Fisrt In First Out)  Việc thêm (Enqueue) hoặc lấy (Dequeue) thực hiện theo cơ chế Vào trước Ra trước.  Việc thêm vào luôn diễn ra ở cuối queue và việc lấy ra luôn diễn ra ở đầu queue.  Hiện thực Queue có thể có thể dùng kiểu mảng hoặc DSLK 88 VII. DSLK đôi (Doubly Linked List)  Là danh sách mà mỗi node trong ds kết nối với node đứng trước và node đứng sau trong ds. A B C D 89 VII. DSLK đôi (Doubly Linked List)  Là danh sách mà mỗi node trong ds kết nối với node đứng trước và node đứng sau trong ds. A B C D 90 Khai báo DSLK đôi typedef struct DNODE { Data Info; DNode* pPre; // lưu trữ địa chỉ của node trước DNode* pNext;// ưu trữ địa chỉ của node sau }; typedef struct DLIST { DNODE* first; // con trỏ trỏ đến đầu ds DNODE* last; // con trỏ trỏ cuối ds }; 91 Tạo 1 node DNODE* GetNode(Data x) { DNODE *p; p = new DNODE; if ( p==NULL) return NULL; p->Info = x; p->pPrev = p->pNext = NULL; return p; } 92 Chèn vào đầu và cuối DSLK đôi new_ele->pNext = l.first; // (1) l.first->pPrev = new_ele; // (2 l.first = new_ele; // (3) X first last A B C D (1) (2) (3) X first last A B C D (1) (2) (3) l.last->Next = new_ele; // (1) new_ele->pPrev = l.last; //(2) l.last = new_ele; // (3) 93 Chèn vào sau node q DNODE *p=q->pNext; new_ele->pNext = p;//(1) new_ele->pPrev = q//(2) if(p != NULL) p->pPrev = new_ele; //(3) q->pNext = new_ele; //(4) X first last A B C D (1) (2) (4) (3) q 94 Chèn vào trƣớc node q DNODE *p=q->pPrev; new_ele->pNext = q;//(1) new_ele->pPrev = p;//(2) q->pPrev = new_ele;//(3) if(p != NULL) p->pNext = new_ele;//(4) X first last A B C D (1) (2) (3) (4) q 95 Hủy phần tử đầu và cuối DSLK đôi  Gán node tạm chứa địa chỉ node đầu hoặc cuối.  Cắt bỏ các mối liên kết  Xóa node tạm Code xóa node đầu DSLK đôi: p = l.first; l.first = l.first->pNext; l.first->pPrev = NULL; delete p; Code xóa node cuối DSLK đôi: p = l.last; l.last = l.last->pPrev; l.last->pNext = NULL; delete p; 96 Hủy node trƣớc hoặc sau node q  Cắt bỏ các mối liên kết với node trước hoặc sau q  Xóa node trước hoặc sau q Code xóa node trước q p = q ->pPrev; q->pPrev = p->pPrev; p->pPrev->pNext = q; delete p; Code xóa node sau q: p = q ->pNext ; q->pNext = p->pNext; p->pNext->pPrev = q; delete p; 97 VIII. Cây, cây nhị phân Gốc(root) Nút trong lá cha và con 98 Các khái niệm  Bậc của một nút : là số cây con của nút đó  Bậc của một cây : là bậc lớn nhất của các nút trong cây. Cây có bậc n thì gọi là cây n-phân.  Nút gốc : là nút không có nút cha.  Nút lá : là nút có bậc bằng 0 .  Nút trong : là nút có bậc khác 0 và không phải là gốc .  Mức của một nút:  Mức (gốc (T) ) = 0.  Gọi T1, T2, T3, ... , Tn là các cây con của T0 Mức (T1) = Mức (T2) = ... = Mức (Tn) = Mức (T0) + 1.  Chiều cao (chiều sâu – depth) của cây là mức cao nhất của cây + 1. 99 24/06/2012 100 Owner Jake Manager Chef Brad Carol Waitress Waiter Cook Helper Joyce Chris Max Len A Tree Has Levels LEVEL 0 24/06/2012 101 Owner Jake Manager Chef Brad Carol Waitress Waiter Cook Helper Joyce Chris Max Len Level One LEVEL 1 24/06/2012 102 Owner Jake Manager Chef Brad Carol Waitress Waiter Cook Helper Joyce Chris Max Len Level Two LEVEL 2 24/06/2012 103 Cây nhị phân  Cây nhị phân là cây mỗi