Cây nhị phân: tiền thứ tự, trung thứ tự, hậu thứ tự và code

Gốc, lá và cây con

Nút gốc là điểm bắt đầu khi duyệt cây. Mỗi con lại có thể là gốc của một cây con, nên cấu trúc cây tự nhiên phù hợp với đệ quy. Nút không có con nào gọi là lá. Một con trỏ rỗng biểu diễn việc không có nút ở nhánh đó; nó không phải nút mang giá trị 0.

Điều kiện “tối đa hai con” cho phép nút có 0, 1 hoặc 2 con. Con trái và con phải có vai trò riêng: cây chỉ có con trái khác cây chỉ có con phải, dù cùng một giá trị. Không nên bỏ thông tin vị trí trái/phải khi lưu dữ liệu hoặc so sánh hai cây.

Ba phép duyệt khác nhau ở thời điểm xử lý gốc

Giữ thứ tự duyệt cây con trái trước, cây con phải sau. Nếu xử lý nút hiện tại trước cả hai cây con, đó là tiền thứ tự, tiếng Anh preorder. Nếu xử lý sau cây trái nhưng trước cây phải, đó là trung thứ tự, inorder. Nếu xử lý sau cả hai cây con, đó là hậu thứ tự, postorder.

Hãy chạy tay ở cây con gốc 2 trước. Preorder của nó là 2, 4, 5; inorder là 4, 2, 5; postorder là 4, 5, 2. Khi trở về gốc 1, chèn phần xử lý gốc đúng thời điểm và thêm cây con chỉ có nút 3. Bạn sẽ thấy ba dãy dùng đúng cùng các nút nhưng thứ tự khác nhau.

Thiết kế hàm đệ quy không bị rối

Điều kiện dừng là nút rỗng: không xử lý gì và trả về. Với nút thật, gọi hàm trên con trái, con phải và đặt thao tác ghi giá trị tại thời điểm tương ứng. Trong code, tham số kieu nhận 0, 1, 2 cho ba lựa chọn. Đây là cách gộp ví dụ để dễ so sánh; khi giải bài, bạn có thể viết riêng từng hàm cho rõ.

Mỗi lời gọi giải một cây con có cùng dạng với bài gốc. Để tự kiểm, thử cây rỗng rồi cây một nút trước khi dùng cây nhiều tầng. Nếu một lời gọi nhận nullptr mà vẫn đọc p->left, chương trình C++ có hành vi không xác định; nhánh dừng phải xuất hiện trước việc truy cập thành viên.

#include <iostream>
#include <vector>
using namespace std;
struct Node{int val;Node*left=nullptr;Node*right=nullptr;explicit Node(int x):val(x){}};
// Chỉ phần dựng ví dụ dùng thứ tự tầng của cây đầy đủ về bên trái.
Node* tao(const vector<int>& a,size_t i=0){
    if(i>=a.size())return nullptr;
    Node*p=new Node(a[i]);p->left=tao(a,2*i+1);p->right=tao(a,2*i+2);return p;
}
void duyet(Node*p,int kieu,vector<int>&out){
    if(!p)return;
    if(kieu==0)out.push_back(p->val);
    duyet(p->left,kieu,out);
    if(kieu==1)out.push_back(p->val);
    duyet(p->right,kieu,out);
    if(kieu==2)out.push_back(p->val);
}
void huy(Node*p){if(p){huy(p->left);huy(p->right);delete p;}}
int main(){
    int n;vector<int>a={1,2,3,4,5};
    if(cin>>n){a.resize(n);for(int&x:a)cin>>x;}
    Node*root=tao(a);
    for(int k=0;k<3;++k){vector<int>out;duyet(root,k,out);for(int x:out)cout<<x<<' ';cout<<'\n';}
    huy(root);
}

class Node:
    def __init__(self,val,left=None,right=None):
        self.val,self.left,self.right=val,left,right

def tao(a,i=0):
    if i>=len(a):
        return None
    return Node(a[i],tao(a,2*i+1),tao(a,2*i+2))

def duyet(root,kieu):
    out=[]
    def visit(p):
        if p is None:
            return
        if kieu==0:
            out.append(p.val)
        visit(p.left)
        if kieu==1:
            out.append(p.val)
        visit(p.right)
        if kieu==2:
            out.append(p.val)
    visit(root)
    return out

if __name__=='__main__':
    import sys
    d=list(map(int,sys.stdin.read().split()))
    a=d[1:1+d[0]] if d else [1,2,3,4,5]
    root=tao(a)
    for k in range(3):
        print(*duyet(root,k))

Không nhập gì, chương trình dựng cây năm nút trong hình và in ba dòng đúng bảng. Với dữ liệu riêng, nhập n không âm, sau đó n số theo thứ tự từng tầng của một cây điền đầy từ trái sang phải. Hàm dựng ví dụ nối chỉ số i tới 2*i+1 và 2*i+2 khi chỉ số còn trong mảng. Đây là quy ước dựng một loại cây thuận tiện để thử, không phải cách biểu diễn mọi cây nhị phân bất kỳ.

Các hàm duyệt làm việc trên Node có left/right và dùng được cho cây có các nhánh rỗng khác nhau. Muốn nhập cây thưa, cần thêm ký hiệu cho vị trí rỗng hoặc nhập các cạnh; không thể bỏ hết ô rỗng rồi áp công thức chỉ số trên. Trong C++, phần hủy đi hậu thứ tự để xóa các con trước khi delete nút cha.

Duyệt theo tầng và ứng dụng của từng thứ tự

Duyệt theo tầng, hay level-order, thường dùng queue. Đưa gốc vào hàng, mỗi lượt lấy một nút và thêm các con tồn tại. Trên ví dụ, thứ tự là 1, 2, 3, 4, 5. Nó khác preorder vì hoàn thành cả tầng hiện tại trước khi xuống tầng sau.

Preorder có ích khi muốn xử lý cha trước con. Postorder thích hợp khi kết quả của nút phụ thuộc hai cây con, chẳng hạn đếm số nút hoặc tính chiều cao. Inorder cho dãy tăng dần chỉ khi cây có thêm tính chất BST; cây ví dụ không phải BST nên dãy 4, 2, 5, 1, 3 không tăng.

Đừng học thuộc thứ tự chỉ để in một dãy. Hãy hỏi lúc xử lý nút, bạn đã cần kết quả của cây con chưa. Nếu cần cả hai, đặt xử lý sau hai lần gọi; nếu đang truyền trạng thái từ cha xuống, xử lý trước hoặc truyền tham số phù hợp.

Thời gian, bộ nhớ và cây lệch

Mỗi phép duyệt thăm n nút một lần nên tốn O(n) thời gian. Ngăn xếp đệ quy có độ sâu O(h), với h là chiều cao cây. Cây cân đối có h = O(log n), nhưng một cây chỉ có một chuỗi con có h = O(n). Danh sách đầu ra trong ví dụ còn cần O(n) bộ nhớ, được tính riêng với bộ nhớ lời gọi.

Python có giới hạn độ sâu đệ quy và C++ cũng có giới hạn stack thực tế. Không nên giải quyết cây cực lệch chỉ bằng tăng giới hạn tùy ý. Bạn có thể chuyển sang duyệt lặp dùng stack hoặc queue, tùy thứ tự cần giữ. Riêng hàm dựng từ mảng của ví dụ tạo cây cân đối về hình dạng, nên không kiểm được toàn bộ rủi ro của cây lệch sâu.

Quy ước chiều cao và các lỗi thường gặp

Cây ví dụ có đường dài nhất từ gốc tới lá gồm ba nút và hai cạnh. Nếu đề tính chiều cao theo số nút thì trả 3, theo số cạnh thì trả 2. Với cây rỗng và một nút, quy ước cũng phải nhất quán. Khi so lời giải, khác quy ước không có nghĩa thuật toán bị sai.

Luyện ngay trên Big-O Coding

Độ sâu và đảo cây luyện hai lời gọi trên hai con. Bài trải phẳng miễn phí luyện biến đổi cấu trúc cây theo thứ tự duyệt, cần giữ liên kết trước khi ghi đè.

Câu hỏi thường gặp

Nguồn tham khảo

• Open Data Structures: Binary Trees
• Open Data Structures: BinaryTree
• Python: Recursion limit