Tuesday, August 2, 2011

Trees: A complete Tree

What is a complete tree?

We have read about trees, binary trees, binary search trees - but what are these complete trees, lets figure out that now.

In the tutorial below, I'll go through the basics which will explain the fundamentals about Complete Trees. Keep in mind, complete trees and binary trees are building blocks for a HEAP.

Complete Trees

When a complete binary tree is built, its nodes are generally added one at a time.
As with any tree, the first node must be the root.
The second node of a complete binary tree is always the left child of the root...
... and the third node is always the right child of the root. And so we continue, adding nodes.

But in a complete binary tree, the way that we add nodes is restricted: Nodes must completely fill each level from left-to-right before proceeding to the next level.

A Correct Complete Tree >

                 5

           /           \

         2               8

      /    \              /  

   1        4        7  

An Incorrect Complete Tree >

                 5

             /          

         2            

      /     \            

   1         4      

Nodes must completely fill each level from left-to-right before proceeding to the next level. 5 should be started with children first before assigning children to 2.

Again, an Incorrect Complete Tree >;

                 5

           /           \

         2               8

       /               /  

     1               7


Nodes must completely fill each level from left-to-right before proceeding to the next level. Right Node of 2 must be filled first before starting with children of 8.

Another Correct Complete Tree >;






Hey, but where is the tree???

Empty tree is also a complete tree!



1 comment:

  1. không chống đỡ nổi , ngân long làm sao có thể chịu đựng nổi đây ?
    Ngay khi tử tinh cự kiếm chuẩn bị hạ xuống thì một đạo thân ảnh lặng lẽ xuất hiện trước mặt ngân long Ly Sát .
    “ Chờ một chút , Tử ! “ . Diệp Âm Trúc đứng giữa đồng tâm
    game mu
    cho thuê nhà trọ
    cho thuê phòng trọ
    nhac san cuc manh
    số điện thoại tư vấn pháp luật miễn phí
    văn phòng luật
    tổng đài tư vấn pháp luật
    dịch vụ thành lập công ty
    http://we-cooking.com/
    chém gió
    trung tâm tiếng anhkhông trung , chậm rãi nói với Tử .
    Tử tinh cự kiếm dừng lại giữa không trung , Tử trầm giọng nói : “ Âm Trúc , chuyện của ta không thể kể cho ngươi nghe bởi vì an toàn của bản thân ta và cũng vì an toàn của ngươi , thân phận ta không thể tiết lộ ra ngoài . Ngoiaj trừ ngươi ra , những ngoại nhân ở đây đều không được quyền biết . Nếu bây giờ ta tha cho ngân long này , tương lai ta sẽ trở thành đối tượng bị vây công của long tộc . Ân oán giữa tử tinh cùng long tộc ngươi không thể hiểu nổi được đâu . Huynh đệ , ngươi hãy tránh ra đi ! “ .
    Diệp Âm Trúc lắc đầu , đáp : “ Ta không biết cái gì là Tử tinh bỉ mông , cũng không biết ngươi với long tộc có ân oán gì . Nhưng mà bản tính Ly Sát vốn không xấu , hơn nữa nàng lại có quan hệ linh hồn y phụ với ta , hãy cho nàng thêm một cơ hội đi . Đương nhiên ta tuyệt đối sẽ không tiết lộ bí mật của ngươi ra ngoài , đồng thời ta cũng có biện pháp khiến Ly Sát và Tô Lạp không thể tiết lộ thân phận của ngươi , khiến cho bọn họ quên đi mọi sự việc xảy ra trong ngày hôm nay “ .
    Tử sững sốt một chút , sát khí trong mắt cũng giảm đi vài phần : “ Ngươi có khả năng tiêu trừ trí nhớ ? “ .
    Diệp Âm Trúc gật đầu : “ Trúc tông chúng ta có một bí kỹ , có tên là cửu châm phong thần , khi ta sử

    ReplyDelete