ĐỊNHNGHĨA

Cấu trúc tài liệu trừu tượng ta vồ cập tới vào mục này là cấu trúc cây. Cây là một cấu trúc dữ liệu bao gồm một tập hữu hạn các nút, giữa các nút bao gồm một quan hệ nam nữ phân cấp điện thoại tư vấn là dục tình "cha - con". Có một nút đặc biệt gọi là cội (root).

Bạn đang xem: Bài tập duyệt cây có lời giải

Có thể quan niệm cây bằng những đệ quy như sau:

Mỗi nút là 1 trong cây, nút đó cũng là gốc của cây ấy

Nếu n là một trong nút với n1, n2, …, nk thứu tự là gốc của các cây T1, T2, …, Tk; những cây này đôi một không tồn tại nút chung. Thì nếu cho nút n trở thành cha của các nút n1, n2, …, nk ta sẽ được một cây new T. Cây này còn có nút n là gốc còn các cây T1, T2, …, Tk trở thành các cây bé (subtree) của gốc.

Để tiện, bạn ta còn chất nhận được tồn trên một cây không có nút nào nhưng ta call là cây trống rỗng (null tree).

Xét cây vào Hình 1:

*
Hình 1:Cây (Tree)

A là cha của B, C, D, còn G, H, I là con của D.

Số những con của một nút được gọi là cấp của nút đó, ví dụ cung cấp của A là 3, cấp của B là 2, cấp của C là 0.

Nút có cấp bằng 0 được hotline là nút lá (leaf) hay nút tận cùng. Ví như ở trên, các nút E, F, C, G, J, K và I là những nút là. Hầu hết nút chưa phải là lá được call là nút nhánh (branch).

Cấp tối đa của một nút trên cây call là cấp của cây đó, cây ngơi nghỉ hình bên trên là cây cấp cho 3.

Gốc của cây tín đồ ta gán mang đến số nấc là 1, giả dụ nút thân phụ có nấc là i thì nút con sẽ sở hữu mức là i +1. Mức của cây vào Hình 1 được đã cho thấy trong Hình 12:


*
Hình 2:Mức của những nút bên trên cây

Chiều cao (height) tuyệt chiều sâu (depth) của một cây là số mức lớn số 1 của nút có trên câyđó. Cây nghỉ ngơi trên có chiều cao là 4.

Một tập hợp những cây tách biệt được hotline là rừng (forest), một cây cũng là một trong những rừng. Nếu quăng quật nút nơi bắt đầu trên cây thì sẽ tạo nên thành một rừng các cây con.

Ví dụ:

Mục lục của một cuốn sách cùng với phần, chương, bài, mục v.v… có cấu tạo của cây

Cấu trúc thư mục trên đĩa cũng có cấu trúc cây, thư mục gốc hoàn toàn có thể coi là gốc của cây

đó với những cây con là những thư mục con và tệp nằm ở thư mục gốc.

Gia phả của một chúng ta tộc cũng có kết cấu cây.

Một biểu thức số học gồm những phép toán cộng, trừ, nhân, phân chia cũng rất có thể lưu trữ vào một cây mà các toán hạng được lưu trữ ở những nút lá, các toán tử được lưu trữ ở các nút nhánh, mỗi nhánh là một biểu thức con.

*

Hình 3:Cây biểu diễn biểu thức

CÂY NHỊ PHÂN (BINARY TREE)

Cây nhị phân là 1 dạng đặc biệt của kết cấu cây. Nó có điểm lưu ý là hầu như nút trên cây chỉ bao gồm tối nhiều hai nhánh con. Với một nút thì tín đồ ta cũng riêng biệt cây con trái cùng cây con cần của nút đó. Cây nhị phân là cây có tính cho thứ tự của những nhánh con.

Cần chăm chú tới một số dạng đặc biệt của cây nhị phân.


Các cây nhị phân vào Hình 4được hotline là cây nhị phân suy vươn lên là (degenerate binary tree), những nút chưa phải là lá chỉ tất cả một nhánh con. Cây a) được gọi là cây lệch phải, cây b) được điện thoại tư vấn là cây lệch trái, cây c) với d) được điện thoại tư vấn là cây zíc-zắc.


*

Hình 4:Các dạng cây nhị phân suy biến

Các cây vào Hình 5 được gọi là cây nhị phân hoàn hảo (complete binary tree): Nếu độ cao của cây là h thì đông đảo nút gồm mức i-1, về tối thiểu là 1 trong những (i ≥1).

Số lượng tối đa các nút bên trên một cây nhị phân có chiều cao h là 2h-1, về tối thiểu là h (h ≥1). Cây nhị phân hoàn chỉnh, không đầy đủ, có n nút thì chiều cao của nó là h = + 1.


Cây nhị phân không thiếu thốn có n nút thì chiều cao của nó là h = log2(n + 1).

BIỂU DIỄN CÂY NHỊ PHÂN


Biểu diễn bởi mảng

Nếu gồm một cây nhị phân đầy đủ, ta hoàn toàn có thể dễ dàng tấn công số cho những nút trên cây kia theo thiết bị tự theo thứ tự từ nấc 1 trở đi, không còn mức này đến hơn cả khác với từ trái sang trọng phải so với các nút ở mỗi mức.

*

Hình 6:Đánh số những nút của cây nhị phân khá đầy đủ để trình diễn bằng mảng

Với biện pháp đánh số này, bé của nút trang bị i đang là những nút lắp thêm 2i với 2i + 1. Thân phụ của nút trang bị j là nút j div 2. Tự đó hoàn toàn có thể lưu trữ cây bởi một mảng T, nút thứ i của cây được lưu trữ bằng bộ phận T.

Với cây nhị phân khá đầy đủ ở Hình 6 thì khi tàng trữ bằng mảng, ta sẽ được mảng như sau:

*

Trong trường vừa lòng cây nhị phân ko đầy đủ, ta hoàn toàn có thể thêm vào một số nút giả và để được cây nhị phân đầy đủ, và gán phần lớn giá trị quan trọng cho những thành phần trong mảng T khớp ứng với phần đa nút này. Hoặc sử dụng thêm một mảng phụ để đánh dấu những nút làm sao là nút trả tự ta thêm vào. Cũng chính vì lý vị này phải với cây nhị phân không đầy đủ, ta sẽ gặp mặt phải sự lãng phí bộ lưu trữ vì rất có thể sẽ nên thêm tương đối nhiều nút trả vào thì mới được cây nhị phân đầy đủ.

Ví dụ cùng với cây lệch trái, ta buộc phải dùng một mảng 31 thành phần để lưu cây nhị phân chỉ có 5 nút.


*

Hình 7:Nhược điểm của phương thức biểu diễn cây bởi mảng


Biểu diễn bằng cấu tạo liên kết

Khi màn trình diễn cây nhị phân bằng cấu tạo liên kết, từng nút của cây là một bạn dạng ghi (record) gồm 3 trường:

Trường Info: cất giá trị lưu lại tại nút đó.

Trường Left: Chứa links (con trỏ) tới nút bé trái, tức là chứa một thông tin đủ để hiểu nút nhỏ trái của nút chính là nút nào, trong trường hợp không tồn tại nút nhỏ trái, trường này được gán một giá trị đặc biệt.

Trường Right: Chứa link (con trỏ) tới nút nhỏ phải, có nghĩa là chứa một tin tức đủ để hiểu nút con đề xuất của nút sẽ là nút nào, trong trường hợp không có nút con phải, trường này được gán một giá trị đặc biệt.

*

Hình 8:Cấu trúc nút của cây nhị phân

Đối với cây ta chỉ việc phải niềm nở giữ lại nút gốc, vị từ nút gốc, đi theo những hướng link Left, Right ta hoàn toàn có thể duyệt mọi nút khác.


*

Hình 9:Biểu diễn cây bằng cấu trúc liên kết


PHÉP DUYỆT CÂY NHỊ PHÂN

Phép xử lý các nút bên trên cây nhưng mà ta gọi bình thường là phép thăm (Visit) những nút một cách khối hệ thống sao cho mỗi nút chỉ được thăm một lần call là phép phê chuẩn cây.

Giả sử rằng giả dụ như một nút không có nút nhỏ trái (hoặc nút bé phải) thì link Left (Right) của nút kia được link thẳng cho tới một nút quan trọng đặc biệt mà ta call là NIL (hay NULL), nếu cây trống rỗng thì nút cội của cây đó cũng rất được gán bằng NIL. Lúc ấy có cha cách trông nom cây hay được sử dụng:

Duyệt theo sản phẩm tự trước (preorder traversal)

Trong phép cẩn thận theo lắp thêm tự trước thì giá trị trong những nút ngẫu nhiên sẽ được liệt kê trước quý hiếm lưu trong nhì nút nhỏ của nó, rất có thể mô tả bằng giấy tờ thủ tục đệ quy sau:


procedure Visit(N); Duyệt nhánh cây dìm N là nút cội của nhánh đó

begin

if N ≠ nil then begin

Visit(Nút con trái của N);

Visit(Nút con cần của N);

end;

end;


Quá trình chuẩn y theo trang bị tự trước bắt đầu bằng lời điện thoại tư vấn Visit(nút gốc).

Như cây làm việc Hình 9, nếu ta săn sóc theo trang bị tự trước thì các giá trị đã lần lượt được liệt kê theo máy tự:

A B D H I E J C F K G L


Duyệt theo lắp thêm tự thân (inorder traversal)


Trong phép duyệt y theo thiết bị tự giữa thì giá trị trong mỗi nút ngẫu nhiên sẽ được liệt kê sau quý hiếm lưu làm việc nút con trái và được liệt kê trước cực hiếm lưu làm việc nút con đề xuất của nút đó, hoàn toàn có thể mô tả bằng giấy tờ thủ tục đệ quy sau:


procedure Visit(N); Duyệt nhánh cây dấn N là nút gốc của nhánh đó

begin

if N ≠ nil then begin

Visit(Nút nhỏ trái của N);

Visit(Nút con nên của N);

end;

end;


Quá trình duyệt y theo sản phẩm công nghệ tự thân cũng bước đầu bằng lời hotline Visit(nút gốc).

Như cây làm việc Hình 9, nếu như ta coi xét theo sản phẩm công nghệ tự thân thì các giá trị đang lần lượt được liệt kê theo máy tự:

H D I B E J A K F C G L

Duyệt theo thiết bị tự sau (postorder traversal)

Trong phép coi xét theo vật dụng tự sau thì giá trị trong những nút ngẫu nhiên sẽ được liệt kê sau cực hiếm lưuở hai nút bé của nút đó, có thể mô tả bằng giấy tờ thủ tục đệ quy sau:


procedure Visit(N); Duyệt nhánh cây nhấn N là nút cội của nhánh đó

begin

if N ≠ nil then begin

Visit(Nút con trái của N);

Visit(Nút con nên của N);

end;

end;


Quá trình chăm nom theo thiết bị tự sau cũng bước đầu bằng lời call Visit(nút gốc).

Cũng cùng với cây ở Hình 9, giả dụ ta để ý theo trang bị tự sau thì những giá trị sẽ lần lượt được liệt kê theo đồ vật tự:


CÂY K_PHÂN

Cây K_phân là 1 trong dạng kết cấu cây mà lại mỗi nút trên cây có tối nhiều K nút bé (có tính đến thứ tự của các nút con).


Biểu diễn cây K_phân bởi mảng

Cũng giống như như việc biểu diễn cây nhị phân, người ta rất có thể thêm vào cây K_phân một vài nút giả để cho mỗi nút nhánh của cây K_phân đều phải có đúng K nút con, những nút bé được xếp thiết bị tự từ nút con trước tiên tới nút con thứ K, tiếp nối đánh số các nút trên cây K_phân ban đầu từ 0 trở đi, ban đầu từ mức 1, hết mức này đến hơn cả khác cùng từ "trái qua phải" sinh hoạt mỗi mức.


Theo bí quyết đánh số này, nút nhỏ thứ j của nút i là: i * K + j. Nút phụ thân của nút x là nút (x - 1) divK. Ta rất có thể dùng một mảng T khắc số từ 0 nhằm lưu những giá trị trên những nút: quý giá tại nút thứiđược tàng trữ ở bộ phận T.


*

Hình 10:Đánh số những nút của cây 3_phân để màn biểu diễn bằng mảng

Biểu diễn cây K_phân bằng kết cấu liên kết


Khi biểu diễn cây K_phân bằng cấu tạo liên kết, từng nút của cây là một phiên bản ghi (record) gồm hai trường:

Trường Info: cất giá trị giữ trong nút đó.

Trường Links: là một mảng có K phần tử, thành phần thứ i chứa links (con trỏ) cho tới nút bé thứ i, vào trường hợp không tồn tại nút con thứ i thì Links được gán một quý giá đặc biệt.

Đối với cây K_ phân, ta cũng chỉ việc giữ lại nút gốc, vày từ nút gốc, đi theo các hướng liên kết hoàn toàn có thể đi tới hồ hết nút khác.

CÂY TỔNG QUÁT

Trong thực tế, có một trong những ứng dụng đòi hỏi một cấu trúc dữ liệu dạng cây nhưng không tồn tại ràng buộc gì về số bé của một nút trên cây, lấy ví dụ như kết cấu thư mục trên đĩa hay hệ thống đề mục của một cuốn sách. Khi đó, ta đề xuất tìm giải pháp mô tả một biện pháp khoa học kết cấu dữ liệu dạng cây tổng quát. Cũng như trường hòa hợp cây nhị phân, người ta thường trình diễn cây tổng quát bởi hai cách: lưu giữ trữ sau đó bằng mảng và lưu trữ bằng cấu trúc liên kết.

Biểu diễn cây tổng quát bởi mảng

Để tàng trữ cây tổng quát bởi mảng, trước hết, ta tiến công số những nút bên trên cây bắt đầu từ 1 theo một máy tự tuỳ ý. Giả sử cây có n nút thì ta sử dụng:

Một mảng Info<1..n>, trong số đó Info là giá trị lưu trong nút sản phẩm i.

Một mảng Children được chia làm n đoạn, đoạn thiết bị i gồm một dãy thường xuyên các bộ phận là chỉ số các nút nhỏ của nút i. Do đó mảng Children đã chứa toàn bộ chỉ số của hồ hết nút bé trêncây (ngoại trừ nút gốc) vì thế nó sẽ gồm n - 1 phần tử, lưu ý rằng khi phân tách mảng Children có tác dụng nđoạn thì sẽ sở hữu những đoạn rỗng (tương ứng cùng với danh sách các nút nhỏ của một nút lá).


Một mảng Head<1..n + 1>, để ghi lại vị trí cắt đoạn vào mảng Children: Head là vị trí đứng tức thì trước đoạn lắp thêm i, xuất xắc nói phương pháp khác: Đoạn con tính trường đoản cú chỉ số Head + 1 đến Head của mảng Children cất chỉ số những nút bé của nút lắp thêm i. Lúc Head = Head tức là đoạn lắp thêm i rỗng. Quy ước: Head = n - 1.

Giữ lại chỉ số của nút gốc. Ví dụ:

*

Hình 11: biểu diễn cây tổng quát bằng mảng

Lưu trữ cây bao quát bằng kết cấu liên kết

Khi lưu trữ cây bao quát bằng kết cấu liên kết, mỗi nút là một bạn dạng ghi (record) gồm bố trường:

Trường Info: đựng giá trị giữ trong nút đó.

Trường FirstChild: Chứa link (con trỏ) cho tới nút con trước tiên của nút kia (con cả), trong trường thích hợp là nút lá (không bao gồm nút con), trường này được gán một quý hiếm đặc biệt.

Trường Sibling: Chứa link (con trỏ) cho tới nút em kề cận bên đề xuất (nút cùng thân phụ với nút đã xét, khi chuẩn bị thứ tự những con thì nút đó đứng ngay tức khắc sau nút đã xét). Vào trường hợp không tồn tại nút em kế cận bên phải, trường này được gán một quý hiếm đặc biệt.


*

Hình 12: cấu trúc nút của cây tổng quát

Dễ thấy được tính đúng đắn của phương pháp biểu diễn, bởi từ 1 nút N bất kỳ, ta có thể đi theo liên kết FirstChild để đến nút bé cả, nút này chính là chốt của một danh sách nối đơn các nút con của nút N: từ bỏ nút con cả, đi theo liên kết Sibling, ta rất có thể duyệt toàn bộ các nút nhỏ của nút N.

Bài tập

Bài 1

Viết chương trình biểu lộ cây nhị phân dùng cấu tạo liên kết, mỗi nút chứa một số trong những nguyên, cùng viết các thủ tục để mắt trước, giữa, sau.

Bài 2

Chứng minh rằng trường hợp cây nhị phân gồm x nút lá cùng y nút cung cấp 2 thì x = y + 1.

Bài 3

Chứng minh rằng giả dụ ta biết dãy những nút được thăm của một cây nhị phân khi duyệt theo lắp thêm tự trước và thứ tự thân thì rất có thể dựng được cây nhị phân đó. Điều này bé đúng nữa không đối với thứ từ trước cùng thứ từ sau? Với sản phẩm tự giữa và thứ tự sau.

Xem thêm: Công Thức Lũy Thừa 12 - Tổng Hợp Đầy Đủ Bộ Công Thức Luỹ Thừa Cần Nhớ

Bài 4

Viết những thủ tục chăm chút trước, giữa, sau ko đệ quy.

« Prev: lời giải và lập trình: §5. Ngăn xếp với hàng ngóng
» Next: giải thuật và lập trình: §7. Ký pháp chi phí tố, trung tố và hậu tố
Copied !!!