TREE

  定義:樹是一個(或以上)的節點所形成的 集合,並且符合下列條

       件:

       (1)含有一個特別的節點,稱為樹根(root)

       (2)其餘節點又分成n個互斥集合(n>=0)T1,T2,……,

          Tn,其中每個集合又是一棵樹。

Binary Trees

 定義:二元樹可以是一棵空的樹(Empty Tree)或者有一個樹根及

       兩棵子樹,分別稱為左子樹與右子樹。左右子樹也都是二

       元樹。我們將以Java Applet的方式,簡單介紹二元樹的

       一些基本操作程式基本操作簡介:

      ★新增(亂數新增):在樹中新增一個節點。

        按新增後的動作如下:

        1.check要新增的節點是否已存在樹中,若否,則往下做。

        2.從樹根開始出發,此時有個指標叫ptr,指向樹根的位子。

        3.新增的節點與ptr指向節點比較,若比ptr指向的節點的值

          小則ptr指向目前所指節點的左子節點;反之,指向右子節點。

        4.重複3的動作,ptr指向的是null時,才把要新增的節點新增上   

          去。

      ★刪除:在樹中刪除一個節點。

        按刪除後的動作如下:

        1.從樹根開始出發,此時有個指標叫ptr,指向樹根的位子。

        2.新增的節點與ptr指向節點比較,若值相等,則將ptr指向的

          節點刪除(1);若比ptr指向的節點的值小則ptr指向目前所

          指節點的左子節點;反之,指向右子節點。

        3.重複2的動作,直到完成刪除動作,或是ptr指向的是null時,

          則表示此節點不存在(刪除失敗)

        註1:若此節點的degree0,表示此節點為樹葉,直接刪除。

            若degree1或是2,則先找出其inorder predecessor

            successor,然後將兩節點的值對調,並將刪除的動作

            從此節點轉換到其inorder predecessorsuccessor上。

 

    秀出範例畫面