Cây

Trở về Mục lục cuốn sách

Cũng giống như danh sách liên kết, cây được tạo thành từ các nút. Một loại cây thông dụng là cây nhị phân, trong đó mỗi nút có chứa một tham chiếu đến hai nút khác (vốn có thể là nút rỗng). Những tham chiếu này gọi là các cây con trái và phải. Cũng như nút của danh sách, mỗi nút trên cây cũng chứa một khoang. Sơ đồ trạng thái cho một cái cây như sau:

Để tránh làm rối hình vẽ, chúng ta thường bỏ qua các cây rỗng (None).

Ở phía trên cùng (nơi mà nút tree chỉ đến) là gốc cây. Theo đúng tin thần ví von với hình ảnh của cây cối, những nút khác có tên là cành, và những nút chĩa ra ngoài cùng với tham chiếu rỗng thì được gọi là . Có vẻ kì quặc khi ta vẽ hình với gốc cây chổng ngược lên trên và lá cây ở dưới cùng, nhưng đó chưa phải là điều lạ nhất.

Mọi việc càng tệ hơn khi các nhà khoa học máy tính đã pha trộn với một phép ví von khác     cây gia đình. Nút ở trên đôi khi còn đợc gọi là cha mẹ và những nút mà nó chỉ đến được gọi là con. Những nút có cùng cha mẹ thì được gọi là anh em.

Cuối cùng là một thuật ngữ về đặc điểm hình học khi nói về cây. Ta đã đề cập đến phía phải và trái, nhưng cũng có cả hướng “lên” (về cha mẹ/gốc) và “xuống” (về phía con/lá). Ngoài ra, tất cả những nút cách đều gốc thì tạo nên một tầng cây.

Có lẽ ta không cần đến ba phép ví von khi nói về cây, song thực tế chúng là như vậy.

Cũng như danh sách liên kết, cây là cấu trúc dữ liệu đệ quy vì chúng được định nghĩa theo lối đệ quy.

Cây hoặc là:

  • một cây rỗng, được biểu diễn bởi None, hay
  • một nút có chứa một tham chiếu đến đối tượng và hai tham chiếu đến cây.

Thiết lập nên cây

Quá trình dựng nên một cây cũng tương tự như quá trình lập danh sách liên kết. Mỗi lượt kích hoạt constructor thì tạo nên một nút.

class Tree: 
  def __init__(self, cargo, left=None, right=None): 
    self.cargo = cargo 
    self.left  = left 
    self.right = right 

  def __str__(self): 
    return str(self.cargo) 

Khoang cargo có thể theo kiểu bất kì, như các đối số cho left và right cần phải là các nút trên cây. left và right đều tùy chọn; giá trị mặc định là None.

Để in thông tin của một nút, ta chỉ việc in khoang này.

Một cách dựng cây là từ chân lên đỉnh. Trước hết, cần phải huy động các nút con:

left = Tree(2) 
right = Tree(3) 

Tiếp theo là tạo ra nút cha mẹ và nối nó với các nút con:

tree = Tree(1, left, right); 

Ta có thể viết đoạn mã lệnh trên gọn hơn bằng cách lồng ghép các lời gọi constructor:

>>> tree = Tree(1, Tree(2), Tree(3)) 

Bằng cách nào đi nữa, kết quả cũng là cây mà ta đã xét ở đầu chương.

Duyệt theo cây

Bất cứ lúc nào bạn thấy một cấu trúc dữ liệu mới, câu hỏi đầu tiên đặt ra sẽ là, “Làm thế nào để duyệt thông tin trên đó?” Cách tự nhiên nhất để duyệt cây là bằng đệ quy. Chẳng hạn, nếu cây có chứa các khoang là số nguyên, thì hàm dưới đây sẽ trả lại tổng của những số nguyên đó:

def total(tree): 
  if tree == None: return 0 
  return total(tree.left) + total(tree.right) + tree.cargo 

Trường hợp cơ sở là cây rỗng, nghĩa là không có khoang nào, và do vậy tổng bằng 0. Bước đệ quy sẽ thực hiện hai lần gọi quy nạp để tìm tổng của các cây con. Khi hoàn thành những lời gọi quy nạp này, ta cộng vào với giá trị ở khoang nút cha mẹ rồi trả lại giá trị của tổng.

Cây biểu thức

Cây là một hình thức tự nhiên để biểu diễn cấu trúc của một biểu thức. Khác với những kiểu kí pháp khác, nó có thể biểu diễn được phép tính mà không có sự mơ hồ. Chẳng hạn, biểu thức trung tố 1 + 2 * 3 có sự mô hồ trừ khi ta đã biết rằng phép nhân phải được thực hiện trước phép cộng.

Cây biểu thức này cũng thực hiện phép tính giống như vậy:

Các nút của một cây biểu thức có thể là những toán hạng như 1 và 2 hoặc các toán tử như + và *. Các toán hạng là nút lá; các nút  toán tử thì chứa những tham chiếu đến các toán hạng của chúng. (Tất cả những toán tử đều thuộc loại toán tử nhị phân, theo nghĩa là chúng có đúng hai toán hạng.)

Ta có thể dựng nên cây như sau:

>>> tree = Tree('+', Tree(1), Tree('*', Tree(2), Tree(3)))

Nhìn vào hình vẽ, không còn nghi ngờ gì về thứ tự phép tính; phép nhân sẽ được thực hiện trước thì từ đó mới tìm ra toán hạng thứ hai cho phép cộng.

Cây biểu thức có nhiều ứng dụng. Ví dụ trong chương này đã dùng cây để chuyển đổi biểu thức thành các dạng hậu tố, tiền tố, và trung tố. Những cây tương tự thế này được dùng trong các trình biên dịch để phân tách, tối ưu hóa, và dịch chương trình.

Duyệt trên cây

Ta có thể duyệt một cây biểu thức rồi in ra nội dung như sau:

def printTree(tree):
  if tree == None: return
  print tree.cargo,
  printTree(tree.left)
  printTree(tree.right)

Nói cách khác, để in một cây, trước hết ta hãy in nội dung của nút gốc, rồi in toàn bộ cây con trái, tiếp theo in toàn bộ cây con phải. Cách duyệt thế này được gọi là thứ tự trước, vì nội dung của gốc xuất hiện trước các nội dung của những nút con. Đối với ví dụ trước, kết quả là:

>>> tree = Tree('+', Tree(1), Tree('*', Tree(2), Tree(3)))
>>> printTree(tree)
 + 1 * 2 3

Định dạng này khác cả hình thức hậu tố lẫn trung tố; nó là một hình thức khác có tên gọi tiền tố, trong đó toán tử xuất hiện trước hai toán hạng.

Bạn có thể nghi hoặc rằng liệu khi duyệt cây theo thứ tự khác đi thì có thu được biểu thức theo kiểu kí pháp khác hay không. Chẳng hạn, nếu in ra những cây con trước rồi mới đến nút gốc, thì bạn sẽ thu được:

def printTreePostorder(tree):
  if tree == None: return
  printTreePostorder(tree.left)
  printTreePostorder(tree.right)
  print tree.cargo,

Kết quả, 1 2 3 * +, có hình thức hậu tố! Như vậy thứ tự duyệt này được gọi là thứ tự sau.

Cuối cùng, để duyệt cây theo thứ tự giữa, bạn cần in ra cây trái, rồi đến gốc, sau đó là cây phải:

def printTreeInorder(tree):
  if tree == None: return
  printTreeInorder(tree.left)
  print tree.cargo,
  printTreeInorder(tree.right)

Kết quả là 1 + 2 * 3, chính là biểu thức dưới hình thức trung tố.

Để công bằng, cần chỉ ra rằng ta đã bỏ qua một điểm phức tạp quan trọng. Đôi khi ta viết một biểu thức theo dạng trung tố, ta phải dùng đến cặp ngoặc tròn để bảo toàn thứ tự phép tính. Như vậy cách duyệt thứ tự giữa vẫn chưa đủ để tạo nên một biểu thức trung tố.

Dù sao, sau khi được cải thiện chút ít, cây biểu thức và các phép duyệt cây đệ quy cho ta một cách tổng quát để chuyển một biểu thức từ dạng này sang dạng khác.

Bài tập: hãy sửa chữa printTreeInorder để nó đặt cặp ngoặc tròn quanh từng cụm toán tử và hai toán hạng liền kề. Liệu kết quả có chính xác và hết mập mờ chưa? Liệu rằng lúc nào cũng cần phải có cặp ngoặc tròn hay không?

Nếu ta thực hiện một phép duyệt theo thứ tự giữa rồi theo dõi xem hiện mình đang ở tầng nào trên cây, thì ta có thể tạo thành một dạng biểu diễn hình học cho cây:

def printTreeIndented(tree, level=0):
  if tree == None: return
  printTreeIndented(tree.right, level+1)
  print '  '*level + str(tree.cargo)
  printTreeIndented(tree.left, level+1)

Tham số level theo dõi vị trí hiện thời của ta trên cây. Ban đầu mặc định nó bằng 0. Mỗi khi gọi đệ quy, ta truyền cho giá trị bằng level+1 vì tầng của nút con thì luôn lớn hơn một so với tầng của nút cha mẹ. Từng phần tử được in ra theo cách sau: cứ xuống một tầng thì sẽ được in lùi dầu dòng một khoảng bằng hai kí tự. Kết quả thu được đối với cây trên là:

>>> printTreeIndented(tree)
    3
  *
    2
+
  1

Nếu nhìn vào kết quả này khi quay ngang trang giấy ra, thì bạn sẽ thấy một sơ đồ đơn giản của hình vẽ ban đầu.

Lập một cây biểu thức

Trong mục này, ta phân tách những biểu thức trung tố và tạo lập nên các cây tương ứng. Chẳng hạn, biểu thức (3+7)*9 cho ra cây sau:

Lưu ý rằng ta đã làm đơn giản biểu đồ bằng việc lược đi tên của các thuộc tính.

Mã lệnh để phân tách mà ta sẽ viết sau đây có nhiệm vụ xử lý những biểu thức chứa con số, ngoặc tròn cùng các toán tử + và *. Ta giả thiết rằng chuỗi được nhập đã được chia thành nguyên tố vào một danh sách Python. Đối với biểu thức (3+7)*9 thì danh sách nguyên tố là:

['(', 3, '+', 7, ')''*', 9, 'end']

Nguyên tố end là cần thiết vì nó ngăn không cho đọc quá điểm cuối của danh sách.

Bài tập: Hãy viết một hàm nhận một chuỗi biểu thức rồi trả lại một danh sách các nguyên tố.

Hàm đầu tiên mà ta sẽ viết là getToken; hàm này nhận đối số gồm một danh sách nguyên tố và một  nguyên tố dự định, rồi so sánh nguyên tố dự định này với nguyên tố đầu tiên trong danh sách. Nếu giống nhau thì nguyên tố sẽ được rút khỏi danh sách rồi trả lại giá trị true cho hàm. Còn nếu không, trả lại giá trị false:

def getToken(tokenList, expected):
  if tokenList[0] == expected:
    del tokenList[0]
    return True
  else:
    return False

Vì tokenList tham chiếu đến một đối tượng khả chuyển, nên những thay đổi thực hiện ở đây cũng thấy được từ bất kì biến nào khác tham chiếu đến cùng đối tượng này.

Hàm tiếp theo, getNumber, có nhiệm vụ xử lý toán hạng. Nếu nguyên tố tiếp theo trong tokenList là một con số, thì getNumber sẽ rút nó khỏi danh sách đồng thời trả lại một nút lá có chứa con số này. Còn nếu không, hàm sẽ trả lại None.

def getNumber(tokenList):
  x = tokenList[0]
  if not isinstance(x, int): return None
  del tokenList[0]
  return Tree (x, None, None)

Trước khi tiếp tục, ta cần phải kiểm tra riêng getNumber. Ta hãy gán một danh sách số vào cho tokenList, xuất ra số đầu tiên, in kết quả, rồi in những thứ còn lại trong danh sách nguyên tố:

>>> tokenList = [9, 11, 'end']
>>> x = getNumber(tokenList)
>>> printTreePostorder(x)
 9
>>> print tokenList
 [11, 'end']

Phương thức tiếp theo ta cần là getProduct, nhằm lập nên cây biểu thức từ những phép nhân. Một phép nhân đơn giản thì có hai toán hạng, như 3 * 7.

Sau đây là một phiên bản getProduct để xử lý phép nhân đơn giản.

def getProduct(tokenList):
  a = getNumber(tokenList)
  if getToken(tokenList, '*'):
    b = getNumber(tokenList)
    return Tree ('*', a, b)
  else:
    return a

Coi rằng getNumber hoạt động được và trả lại một cây đơn độc, ta sẽ gán toán hạng thứ nhất cho a. Nếu kí tự tiếp theo là *, ta lấy con số thứ hai rồi lập nên một cây biểu thức với ab, và toán tử nhân đó.

Nếu kí tự tiếp theo là bất kì thứ gì khác thì ta chỉ việc trả lại nút lá chứa a. Sau đây là hai ví dụ:

>>> tokenList = [9, '*', 11, 'end']
>>> tree = getProduct(tokenList)
>>> printTreePostorder(tree)
 9 11 *
>>> tokenList = [9, '+', 11, 'end']
>>> tree = getProduct(tokenList)
>>> printTreePostorder(tree)
 9

Ví dụ thứ hai ngụ ý rằng ta coi một toán hạng như một dạng của một tích. Định nghĩa “tích” kiểu này có vẻ trái với trực quan, nhưng hóa ra lại có ích.

Bây giờ ta đi xử lí các tích phức hợp, như 3 * 5 *
13
. Ta coi biểu thức này như một tích của hai tích, cụ thể là 3
* (5 * 13)
. Từ đó ta có cây sau:

Thay đổi getProduct một chút, ta có thể xử lý được một tích dài tùy ý:

def getProduct(tokenList):
  a = getNumber(tokenList)
  if getToken(tokenList, '*'):
    b = getProduct(tokenList)       # sửa đổi dòng này 
    return Tree ('*', a, b)
  else:
    return a

Nói cách khác, một tích có thể là một cây đơn độc hoặc một cây có * ở gốc, một con số ở nhánh trái, và một tích ở nhánh phải. Cách định nghĩa theo lối đệ quy này, bạn nên bắt đầu làm quen.

Ta hãy kiểm tra đoạn mã lệnh mới bằng một tích phức hợp:

>>> tokenList = [2, '*', 3, '*', 5 , '*', 7, 'end']
>>> tree = getProduct(tokenList)
>>> printTreePostorder(tree)
2 3 5 7 * * *

Tiếp theo ta sẽ thêm khả năng để phân tách các tổng. Một lần nữa, ta dùng một định nghĩa hơi phản trực quan về “tổng.” Đối với chúng ta, một tổng có thể là một cây với + ở gốc, một tích ở nhánh trái, và một tổng ở nhánh phải. Hoặc, một tổng có thể đơn giản chỉ là một tích.

Nếu bạn sẵn lòng đón nhận định nghĩa này, thì ở đó có một thuộc tính hay: ta có thể biểu diễn bất kì biểu thức nào (không chứa ngoặc tròn) dưới dạng một tổng của các tích. Thuộc tính này là cơ sở của thuật toán phân tách mà ta thiết lập.

getSum cố gắng lập nên một cây với một tích ở nhánh trái và một tổng ở nhánh phải. Nhưng nếu nó không tìm thấy dấu +, nó sẽ chỉ lập nên một tích mà thôi.

def getSum(tokenList):
  a = getProduct(tokenList)
  if getToken(tokenList, '+'):
    b = getSum(tokenList)
    return Tree ('+', a, b)
  else:
    return a

Ta hãy kiểm tra nó bằng biểu thức 9 * 11 + 5 * 7:

>>> tokenList = [9, '*', 11, '+', 5, '*', 7, 'end']
>>> tree = getSum(tokenList)
>>> printTreePostorder(tree)
 9 11 * 5 7 * +

Ta đã gần đạt được mục đích, song vẫn còn phải xử lý những dấu ngoặc tròn. Bất cứ đâu trong biểu thức cũng có thể chứa một con số, thì ở đó cũng có thể là một tổng đặt giữa cặp ngoặc tròn. Ta chỉ cần sửa chữa getNumber để xử lý được biểu thức con:

def getNumber(tokenList):
  if getToken(tokenList, '('):
    x = getSum(tokenList)         # nhận biểu thức con
    getToken(tokenList, ')')      # bỏ đi dấu đóng ngoặc tròn 
    return x
  else:
    x = tokenList[0]
    if not isinstance(x, int): return None
    tokenList[0:1] = []
    return Tree (x, None, None)

Ta hãy thử mã lệnh này bằng biểu thức 9 * (11 + 5) * 7:

>>> tokenList = [9, '*''(', 11, '+', 5, ')''*', 7, 'end']
>>> tree = getSum(tokenList)
>>> printTreePostorder(tree)
 9 11 5 + 7 * *

Mã lệnh phân tách đã xử lý chính xác trường hợp có ngoặc tròn; phép cộng được thực hiện trước phép nhân.

Trong phiên bản cuối cùng của chương trình, một ý kiến hay là đặt cho getNumber một cái tên gợi tả hơn để phù hợp với nhiệm vụ mới của nó.

Xử lý lỗi

Trong suốt mã lệnh phân tách nói trên, ta đã giả sử rằng các biểu thức đều định hình hoàn chỉnh. Chẳng hạn, khi đến cuối một biểu thức con, ta giả sử rằng kí tụ tiếp theo là một dấu đóng ngoặc tròn. Nếu có một lỗi xảy ra bởi kí tự tiếp theo không phải, thì ta cần xử lý nó.

def getNumber(tokenList):
  if getToken(tokenList, '('):
  x = getSum(tokenList)
if not getToken(tokenList, ')'):
raise ValueError, 'thiếu dấu ngoặc'
return x
else: # bỏ qua phần còn lại của hàm

Câu lệnh raise tạo nên một biệt lệ; trong trường hợp này là ValueError. Nếu hàm gọi đến getNumber, hoặc gọi một trong những hàm khác trong vết dò ngược (traceback) mà xử lý được biệt lệ, thì chương trình có thể tiếp tục. Còn nếu không, Python sẽ in ra một thông báo lỗi và dừng.

Bài tập: Hãy tìm những chỗ khác trong các hàm trên nơi có thể xảy ra lỗi, rồi thêm vào các câu lệnh raise phù hợp. Hãy kiểm tra mã lệnh bằng các biểu thức thiết lập sai.

Cây loài vật

Trong mục này, ta phát triển một chương trình nhỏ có dùng cây để biểu diễn một cơ sở tri thức.

Chương trình này tương tác với người dùng để tạo nên một cây câu hỏi cùng tên các loài vật. Sau đây là một lần chạy thử:

Bạn đang nghĩ về một loài vật à? c
Có phải một loài chim không? k
Nó là loài gì? chó
Câu hỏi nào sẽ phân biệt được loài chó với chim? Nó bay được không
Nếu loài vật bạn đang nghĩ là chó thì trả lời câu hỏi trên thế nào? k

Bạn đang nghĩ về một loài vật à? c
Nó bay được không? k
Nó có phải là chó không? k
Nó là loài gì? mèo
Câu hỏi nào sẽ phân biệt được loài mèo với chó? Nó sủa được không
Nếu loài vật bạn đang nghĩ là mèo thì trả lời câu hỏi trên thế nào? k
Bạn đang nghĩ về một loài vật à? c
Nó bay được không? k
Nó sủa được không? c
Nó có phải là chó không? c
Tôi thắng rồi!
Bạn đang nghĩ về một loài vật à? k

Và sau đây là cây dựng được từ đoạn hội thoại trên:

Vào đầu mỗi lượt chơi, chương trình sẽ đi từ đỉnh của cây và đặt câu hỏi đầu tiên. Tùy theo câu trả lời, nó sẽ đi sang cây con trái hoặc phải, và tiếp tục đến khi đạt được nút lá. Ở điểm đó, chương trình sẽ đưa ra dự đoán. Nếu dự đoán không đúng, nó hỏi người chơi cho biết tên loài vật mới và hỏi thêm một câu làm cách nào để phân biệt loài vật này với loài mà vừa đoán sai. Sau đó, chương trình sẽ thêm vào cây một nút chứa câu hỏi và loài mới này.

Sau đây là mã lệnh:

def animal():
  # bắt đầu với một cây đơn độc 
  root = Tree("chim")
# lặp vòng cho đến khi người chơi chấm dứt
while True:
  print
  if not yes("Bạn đang nghĩ về một loài vật à? "): break
# đi trên cây
tree = root
while tree.getLeft() != None:
prompt = tree.getCargo() + "? "
if yes(prompt):
  tree = tree.getRight()
else:
  tree = tree.getLeft()
# phỏng đoán
guess = tree.getCargo()
prompt = "Nó có phải là " + guess + " không ? "
if yes(prompt):
  print "Tôi thắng rồi!"
  continue
# lấy thông tin mới
prompt  = "Nó là loài gì? "
animal  = raw_input(prompt)
prompt  = "Câu hỏi nào sẽ phân biệt được loài %s với %s? "
question = raw_input(prompt % (animal,guess))
# bổ sung thông tin mới này vào cây
tree.setCargo(question)
prompt = "Nếu loài vật bạn đang nghĩ là %s thì trả lời câu hỏi trên thế nào? "
if yes(prompt % animal):
  tree.setLeft(Tree(guess))
  tree.setRight(Tree(animal))
else:
  tree.setLeft(Tree(animal))
  tree.setRight(Tree(guess))

Hàm yes là một hàm phụ trợ; nó in ra một dấu nhắc rồi nhận câu trả lời của người dùng. Nếu câu trả lời bắt đầu bằng  c hoặc C, hàm sẽ trả lại true:

def yes(ques):
  from string import lower
  ans = lower(raw_input(ques))
  return (ans[0] == 'c')

Điều kiện của vòng lặp ngoài là True, điều này nghĩa là nó vẫn sẽ tiếp tục cho đến khi lệnh break được thực thi, nếu người chơi không nghĩ về một loài vật.

Vòng lặp while bên trong có nhiệm vụ đi trên cây từ đỉnh xuống đáy, được dẫn dắt qua những câu trả lời của người chơi.

Khi một nút mới được thêm vào cây, thì câu hỏi mới này sẽ thay thế khoang chứa thông tin, và hai cây con sẽ là loài vật mới và khoang ban đầu.

Một nhược điểm của chương trình là khi kết thúc, nó sẽ quên hết những gì bạn đã tận tình chỉ dạy!

Bài tập: Hãy hình dung những cách khác nhau để bạn có thể lưu lại kiến thức trên cây vào một tập tin. Hãy thực hiện phương án mà bạn cho là dễ nhất.

Phụ lục

cây nhị phân
Một cây mà mỗi nút chỉ đến không, một, hoặc hai nút phụ thuộc.
gốc
Nút ở đỉnh trên cùng của cây, không có nút cha mẹ nào.
Nút ở dưới cùng của cây, không có nút con nào.
nút cha mẹ
Nút tham chiếu đến nút cho trước.
nút con
Một trong các nút được nút khác tham chiếu đến.
nút anh em
Những nút có chung cha mẹ.
tầng
Tập hợp các nút cánh đều đến gốc.
toán tử nhị phân
Toán tử có nhận hai toán hạng.
biểu thức con
Một biểu thức đặt trong cặp ngoặc đơn để đóng vai trò của một toán hạng đơn lẻ trong biểu thức lớn.
thứ tự trước
Một cách duyệt cây, thăm từng nút trước khi thăm các nút con của nó.
kí pháp tiền tố
Một cách viết biểu thức toán học mà từng toán tử đứng trước các toán hạng.
thứ tự sau
Một cách duyệt cây, thăm từng nút con trước khi thăm bản thân mỗi nút.
thứ tự giữa
Một cách duyệt cây, thăm cây con trái, rồi đến gốc, sau đó đến cây con phải.

1 Phản hồi

Filed under Think Python

One response to “Cây

  1. Pingback: Cách nghĩ như nhà khoa học máy tính | Blog của Chiến

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s