🎯 Mục tiêu

• Hiểu cấu trúc cây và cách duyệt (inorder, preorder, postorder).
• Áp dụng nguyên lý BST để tìm kiếm nhanh.

📘 Lý thuyết

Cây nhị phân gồm các nút, mỗi nút có tối đa 2 con. BST thỏa: giá trị bên trái < nút gốc < giá trị bên phải.

💻 Ví dụ

C++

#include <bits/stdc++.h>
using namespace std;
struct Node{int val;Node* left;Node* right;Node(int v):val(v),left(NULL),right(NULL){}};
Node* insert(Node* r,int v){
  if(!r) return new Node(v);
  if(v<r->val) r->left=insert(r->left,v);
  else r->right=insert(r->right,v);
  return r;
}
void inorder(Node* r){if(!r)return;inorder(r->left);cout<<r->val<<" ";inorder(r->right);}
int main(){Node* root=NULL;for(int x:{5,3,7,2,4,6,8}) root=insert(root,x);inorder(root);}

Python

class Node:
    def __init__(self,val): self.val=val;self.left=self.right=None
def insert(r,v):
    if not r: return Node(v)
    if v<r.val: r.left=insert(r.left,v)
    else: r.right=insert(r.right,v)
    return r
def inorder(r):
    if not r: return
    inorder(r.left);print(r.val,end=' ');inorder(r.right)
root=None
for x in [5,3,7,2,4,6,8]: root=insert(root,x)
inorder(root)

🧩 Bài tập

1. Viết hàm tìm kiếm trong BST.
2. Đếm số lá trong cây.
3. In cây theo thứ tự giảm dần.

def search(root,x):
    if not root: return False
    if root.val==x: return True
    return search(root.left,x) if x<root.val else search(root.right,x)