Định nghĩa cho chiều cao của cây là gì?

Question

tôi dường như không thể tìm thấy một câu trả lời dứt khoát cho điều này, tôi đang cố gắng để làm một số bằng chứng tiểu học trên đống nhưng đây là những gì đang ném tôi ra một chút:

là một cây trống hợp lệ? Nếu vậy, chiều cao của nó là bao nhiêu?
Tôi nghĩ điều này sẽ là 0.

Chiều cao của cây bằng một nút là gì?
Tôi nghĩ đây sẽ là 1 nhưng tôi đã thấy định nghĩa ở đó 0 (và nếu đây là trường hợp thì tôi không biết cách giải thích cho cây trống).

Answer 1

Tôi nghĩ bạn nên xem Dictionary of Algorithms and Data Structures tại trang web NIST. Có definition for height cho biết một nút là chiều cao 0.

definition of a valid tree không bao gồm cấu trúc trống. Trang web không đề cập đến chiều cao của cây như vậy, nhưng dựa trên định nghĩa về chiều cao, nó cũng phải là 0.

Answer 2

Chiều cao của cây là chiều dài của đường dẫn từ gốc của cây đó đến nút xa nhất của nó (tức là nút lá xa nhất từ ​​gốc).

Một cây chỉ có nút gốc có chiều cao 0 và một cây có các nút bằng 0 sẽ được coi là rỗng. Một cây trống có chiều cao -1. Vui lòng kiểm tra this.

Tôi hy vọng điều này sẽ hữu ích.

Answer 3

Tôi đã thấy nó được sử dụng theo cả hai cách (đếm một nút là 0 hoặc 1), nhưng phần lớn các nguồn sẽ xác định một cây chỉ gốc là cây có chiều cao 0, và sẽ không xem xét một nút 0 cây hợp lệ.

Answer 4

Theo Wikipedia, chiều cao của cây (phụ) với một nút duy nhất là 0. Chiều cao của cây không có nút nào là -1. Nhưng tôi nghĩ điều đó tùy thuộc vào bạn, cách bạn xác định chiều cao và bằng chứng của bạn sẽ hoạt động với một trong hai định nghĩa.

Answer 5

Nếu cây của bạn là cấu trúc dữ liệu được xác định đệ quy có thể rỗng hoặc nút một cây con trái và phải (ví dụ cây tìm kiếm, hoặc đống của bạn), thì định nghĩa tự nhiên là gán 0 cho cây trống và 1 + chiều cao của cây con cao nhất cho cây không phải cây gai dầu.

Nếu cây của bạn là biểu đồ thì định nghĩa tự nhiên là đường dài nhất từ ​​gốc tới lá, do đó cây chỉ có chiều sâu 0. Bạn thường không xem xét cây trống trong trường hợp này.

Answer 6

Chiều cao của cây là chiều dài của con đường dài nhất đến nút đầu cuối ở một trong hai nút con của nó.

Wikipedia nói the height of an empty tree is -1. Tôi không đồng ý. Một cây trống theo nghĩa đen chỉ là một cây có chứa một nút đầu cuối (một giá trị null hoặc đặc biệt đại diện cho một cây trống). Vì nút không có con, chiều dài đường đi dài nhất của nó phải là empty sum = 0, không phải là -1.

Tương tự như vậy, một cây không trống có hai con, do đó theo định nghĩa, có ít nhất đường dẫn> = 1 đến nút đầu cuối.

Chúng ta có thể xác định cây của chúng tôi như sau:

type 'a tree = 
    | Node of 'a tree * 'a * 'a tree 
    | Nil 

let rec height = function 
    | Node(left, x, right) -> 1 + max (height left) (height right) 
    | Nil -> 0 

Answer 7

actully một defn hoàn hảo cho chiều cao của cây là mức d của lá của d con đường dài nhất từ ​​gốc cộng 1..accordin 2 defn fa cây này s có sản phẩm nào , nó sẽ không havin bất kỳ mức nv không thể xem xét nó có số không, mức coz của một gốc s zero .. như vậy mức độ cây rỗng là -1, hơn accordin 2 defn của nó -1 + 1 = 0..so ZERO sd chiều cao của sản phẩm nào cây ... bt n nhiều cuốn sách họ hav đưa ra -1 bt không có lời giải thích cho