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

Cây nhị phân gồm:
- Thành phần dữ liệu
- Hai địa chỉ trỏ đến hai node con của nó
Cây nhị phân tìm kiếm là cây nhị phân mà khóa của node con trái < khóa của node cha < khóa của node con phải và các khóa trong node không được trùng nhau.

Ta xây dựng cây nhị phân tìm kiếm có dữ liệu là kiểu int.
          1. Định nghĩa node và cây:
struct Node
{
int Info;
Node *pLeft, *pRight;
};

typedef Node* Tree;
          2. Tạo node: 
Node* GetNode(int x)
{
Node *p = new Node;
if(p)
{
p->Info = x;
p->pLeft = p->pRight = NULL;
}
return p;
}
          3. Khởi tạo cây:
void Init(Tree &tree)
{
tree = NULL;
}
          4. Chèn node vào cây:
bool InsertNode(Tree &tree, int x)
{
if(tree)
{
if(x == tree->Info)
return false;
if(x < tree->Info)
return InsertNode(tree->pLeft, x);
else
return InsertNode(tree->pRight, x);
}
tree = GetNode(x);
if(tree)
return true;
else
return false;
}
          5. Duyệt cây:
              Ta thường dùng 3 kiểu duyệt: LNR (Left - Node - Right), NLR (Node - Left - Right), LRN (Left - Right - Node).
void NLR(Tree tree)
{
if(tree)
{
cout<<tree->Info<<" "<<endl;
NLR(tree->pLeft);
NLR(tree->pRight);
}
}
Ví dụ: Cho cây nhị phân tìm kiếm với kiểu dữ liệu là kiểu char

Kết quả sau khi duyệt cây theo LRN, NLR, LNR là gì?
LRN: A C D B H K I T W S P M
NLR: M I B A D C K H P S T W
LNR: A B C D I H K M P T S W

          6. Tìm kiếm:
Node* Search(Tree tree, int x)
{
if(tree == NULL)
return NULL;
if(x == tree->Info)
return tree;
if(x < tree->Info)
return Search(tree->pLeft, x);
else
return Search(tree->pRight, x);
}
          7. Xóa node:
void SearchStandFor(Tree &p, Tree &q) // tìm node trái nhất của nhánh phải để thay thế cho p
{
if(q->pLeft)
SearchStandFor(p, q->pLeft);
else
{
p->Info = q->Info;
p = q;
q = q->pRight;
}
}

bool DelNode(Tree &tree, int x)
{
if(tree == NULL)
return false;
if(x < tree->Info)
return DelNode(tree->pLeft, x);
else if(x > tree->Info)
return DelNode(tree->pRight, x);
else
{
Node *p = tree;
if(tree->pLeft == NULL)           // node không có con trái
tree = tree->pRight;
else if(tree->pRight == NULL) // node không có con phải
tree = tree->pLeft;
else                                            // node lá
SearchStandFor(p, tree->pRight);
                delete p;                                              
return true;
}
}
Ví dụ: Muốn xóa node 4 thì ta sẽ lấy node 6 để thay thế vị trí cho nó sau khi xóa

          8. Tính chiều cao cây:
               Quy ước tại gốc thì chiều cao là 0.
int Max(int a, int b)
{
if(a > b)
return a;
return b;
}

int TinhChieuCao(Tree tree)
{
if(tree == NULL)
return -1;
if(tree->pLeft == NULL && tree->pRight == NULL)
return 0;
return 1 + Max(TinhChieuCao(tree->pLeft), TinhChieuCao(tree->pRight));
}
          9. Đếm số node có đủ cả hai con:
int DemNodeFull(Tree tree)
{
int count = 0;
if(tree == NULL)
return 0;
if(tree->pLeft != NULL && tree->pRight != NULL)
count++;
return count + DemNodeFull(tree->pLeft) + DemNodeFull(tree->pRight);
}
Tương tự như vậy, ta có thể đếm được tất cả các số node trong cây, số node lá, số node chỉ có một con,.. hay node thỏa theo điều kiện nào đó.