Java中基於ArrayList的二叉樹實現

Question

我有3種遞歸實現的方法。是的，這是爲了學校，所以請，簡單的答案&，我會很感激描述性的答案，所以我可以學習！我對樹結構很陌生。

3種方法如下...

public class Zombies{ 
    public static int countPeople(Person p){...} 
    // counts all the people in the tree structure 
    // starting with Person p. 

    public static int countZombies(Person p){...} 
    // counts all the people in the tree structure 
    // starting with Person p that are zombies 

    public static void draw(Person p){...} 
    // draws a diagram of the people in tree structure 
    // starting with Person p. 
    // each person will be denoted by a P and 
    // person that is a zombie will be denoted by a Z 
    // 
    // The diagram should illustrate the family tree 
    // structure. Each person will be drawn with 3 minus 
    // signs '-' for each level below p. 

我開始我的Person類和我有幾個問題。

1）我在正確的軌道上我個人類

2）在方法描述中提及二叉樹的樹形結構？

3）我缺少的是能夠實現這些方法（如果有什麼，還是有這種樹形結構需要積木）

下面是我的Person類。類型的樹的

public class Person{ 

    public int  id;  // some identification number unique to the person 
    public boolean zombie; // true if the person is a zombie 
    public char state; // p means human, z means zombie 

    public ArrayList<Person> friends; // list of friends 

    public Person(int id, char state, boolean zombie){ 
     this.id = id; 
     this.state = state; 
     this.zombie = zombie; 
    } 

    public boolean isZombie() { 
     if (state == 'p'){ 
      return zombie=false; 
     } 
     else if (state == 'z'){ 
      return zombie=true; 
     } 
     return zombie; 
    } 
} 

樣本輸出如下..

P   (this is Person q) 
---P  (this is a friend of q, say q1) 
------P (this is a friend of q1) 
------Z (this is another friend of q1, who is a zombie) 
---Z  (this is a friend of q, say q2, who is a zombie) 
------Z (this is a friend of q1, who is also a zombie) 
------P (this is a friend of q1, who is not a zombie) 

預先感謝耐心和幫助/輸入！

Answer 1

希望這會給你一些洞察，以實現基於數組的二叉樹。

從另一篇文章摘自：

當你寫二叉樹，當你建造什麼通常稱爲堆的陣列。堆是相當有據可查，並且這篇文章會給你很多細節，關於他們是如何實現的：

http://en.wikipedia.org/wiki/Binary_heap

鏈接到原：

ArrayList Based Binary Tree - Java

編輯：

它所看起來你正在做的是創建一個「人」類人的二叉樹。每個「父母」人都有「朋友」，這是「人」的孩子。如果「朋友」的數量限制爲2，那麼這是一種二叉樹格式。

樹只是用來存放數據的組織結構......並且在你的情況下是不同的人。與您無關的二進制堆的一部分是堆基於節點值進行組織。你不必擔心這一點。

，以便類殭屍可以採取任何人對象及其所有相關的「朋友」，並確定有多少人或殭屍等

一個人的每個實例都會有朋友一棵樹，排序，您可以從中訪問該人員。

什麼使樹結構是一個鏈接到父母的孩子。所以person1有兩個朋友，friend1和friend2。然後訪問friend1，然後檢查他是否有任何朋友。如果是這樣，你檢查朋友朋友等。這是樹木可以幫助您導航信息的方式的非常通用的解釋。

基本上，如果樹中的任何人擁有2個以上的朋友，則它不再是二叉樹。

看看這個：

http://en.wikibooks.org/wiki/A-level_Computing/AQA/Problem_Solving,_Programming,_Operating_Systems,_Databases_and_Networking/Programming_Concepts/Tree_traversal_algorithms_for_a_binary_tree

這是遍歷樹的一個例​​子。你可以在你遍歷的時候增加值來給你樹中的殭屍或者普通人的數量。

我很抱歉，如果這是解釋似乎分散，但我很難理解你想要做什麼和組織。

EDIT2：

好了，所以你打電話從殭屍類的靜態函數。你需要遞歸檢查這個人和他所有的朋友。

如果你想這是一個二叉樹實現，每個人可以有不超過2個朋友。

如果它不是二叉樹，那麼對每個人的朋友數組的大小沒有限制。

基本上你需要做的是讓殭屍類中的函數遍歷所有的人（朋友，朋友的朋友等）檢查他們是否是殭屍。當你發現它們時，打印以控制結果。然後繼續。

所以看看我上面發佈的有關遍歷樹的鏈接，並將其應用於每個人的朋友的數組列表。有不同的方式遞歸迭代......所以選擇一種樣式（看起來像需要按順序遍歷）並以這種方式實現檢查/打印功能。

這是一個主角，讓我知道如果你再次陷入困境。涉及理解樹木的抽象可能會非常棘手。

Answer 2

1）也許不是你在找什麼，但我會擺脫Person.state。有兩個獨立的領域都用於確定一個人是否是一個殭屍是混淆和容易出錯。 zombie是true和state是p是什麼意思？

2）Miorel的評論有一些很好的見解。從你給了我們什麼樹應該代表什麼，爲什麼它必須是一棵樹，或者它是如何被人居住，這是不明確的。

3）你需要某種世界物體。 Zombies可能是一個不錯的選擇。顯然，你需要一棵所有人的樹。至少，你需要某種人的收集。該集合需要被聲明，實例化和填充。您可能需要它作爲Zombies類的成員。絕對不是作爲Person課程的成員，您將擁有很多課程。

Answer 3

Q1）我是否和我的班級一起走上正軌？

從我的角度來看，我必須說不。

它有什麼問題？

您有冗餘邏輯。字段zombie和state指的是人類潛力的相同狀態。

在這一點上，我們必須做出什麼是殭屍和什麼是人的決定。做這個行爲，行爲是否一樣？從我的觀察，他們有一些共同的特徵，但他們的表達非常鮮明的元素。爲了證明這一點，讓我們想象我們站在人類面前，問他時間。他很可能會給我們一些邏輯的答案。在完成問題之前，另一隻手的殭屍肯定會嘗試吃掉我們的大腦。

這就是爲什麼而不是引入狀態（即btw應該是一個枚舉），我會使用inherit mechanism。

public class Person { 

    private final int id; 

    public Person(int id) { 
    this.id = id; 

    } 

    public int hashCode() { 
    return id; 
    } 

    public boolean equals(Object object) { 

    if(object instance of Person) { 
     return this.id == ((Person) object).id; 
    } 

    return false; 
    } 
} 

public class Zombie : Person { 

    public Zombie(int id) { 
     super(id); 
    } 
) 

---

如何證明一個朋友是人或殭屍？

爲此，您使用了方法isZombie。因爲我們現在有兩個類有這種方法是不合理的。類Zombie代表殭屍和Human。因此，在代碼如if(human.isZombie())，看起來很奇怪。

這裏是OOP踢的力量。我們沒有插入，檢測到一個對象是這種類型或另一個。我們想要的是在控制檯上呈現（對於這種情況），通知用戶該對象是人類或殭屍的有效字符。爲了能夠做到這一點，我們必須添加一個方法到類人類和[覆蓋]類殭屍。這個方法將負責返回有效的char。

public class Person { 

    //... 

    public char howDoOtherSeeMe() { 

    return 'P'; 

    } 
} 

public class Zombie : Person { 

    //... 

    @override 
    public char howDoOtherSeeMe() { 

    return 'Z'; 

    } 
} 

---

Q2）是在方法描述中提及的二進制樹樹結構？

A2。否。定義的二叉樹只能有兩個節點，並且不能有循環。同樣在我們的Person類中耦合結構可能會使課程快速增長並且不受控制。

Answer 4

1. 是的，我認爲你是在正確的軌道上。但是，正如其他人指出的那樣，同時擁有char state和boolean zombie是多餘的。就我個人而言，在這種情況下，我認爲繼承可能是一種重大的矯枉過正 - 可以理解的情況是，如果您以後想要擁有可以成爲「殭屍」，「吸血鬼」甚至是「狼人」的「人」 「但是，我認爲在這種情況下，能夠簡單地說if (p.isZombie()) { ... }就足夠了，但我會放棄它，因爲這是一個古老的設計論點 - 我屬於」構圖 - 繼承「陣營（http://en.wikipedia.org/wiki/Composition_over_inheritance）

2. 這確實是一個樹狀結構，但是，我高度懷疑這是一個二叉樹 - 基於規範，但沒有理由它無法是。對我來說，這似乎是一棵N-Ary樹。如果你之前沒有觸及過這些樹，它們只是一個通用的樹結構，其中每個節點可以有任意數量的子節點。這個鏈接給出了一個更好的解釋：http://www.brpreiss.com/books/opus5/html/page257.html（更多在這一刻）

3. 你不會錯過任何實現這些方法（我可以告訴，這取決於你的教授 - 他們如何去標記這個？運行他們自己的測試代碼？只要看看你的代碼？或者你是否提供演示這是如何工作的客戶端代碼（主要方法）？如果他們正在運行測試代碼，則必須確保您的Person API與他們的規格兼容）。

瞭解這裏最重要的，是如何表示N叉樹已創建的數據結構和。 Person類代表樹中的單個節點（任何節點，可能是根，無關緊要），並且ArrayList<Person>存儲屬於該節點的每個子節點（或朋友）。它本質上是一個「鏈接結構」。試想一下：

class Node { 
    public ArrayList<Node> children = new ArrayList<Node>(); 
} 

這個類有0或更多的孩子（存儲在children），每個孩子都是Node（這反過來有0個或更多的孩子）。

所以，我可以很容易做出一些Node是根Node，再建一個樹的方式：

Node root = new Node(); 
root.children.add(new Node()); 
root.children.add(new Node()); 
root.children.get(0).children.add(new Node()); 
root.children.get(0).children.add(new Node()); 

在本質上，這將創建一個可表示爲這樣的樹：

root 
    /\ 
    /\ 
    0 1 
/\ 
/ \ 
0  1 

現在，也許你會爲什麼我以前說過的通知「沒有理由它無法是[二叉樹]」從技術上講，一個二叉樹是N叉樹，其中N = 2。

另一件重要的事情就是每個節點可以被認爲是它自己的N元樹。所以，舉例來說，就方法而言，當你說draw(Person p)時，p將永遠是一些N-Ary樹的根 - 無論它實際上是整棵樹的根還是僅僅是某棵子樹的根樹。

希望這會有所幫助！我知道你前一段時間發佈了這個問題，所以我希望你成功地完成了這個任務，或者我還沒有太晚。如果沒有，也許它會幫助其他人：/

另外，要解決這些問題（算法和數據結構）時要記住的重要一點是不要被無關的細節阻塞，例如（在這個例子），它們是不是很重要，不管它們是「人們可能是與某些朋友的殭屍」等。這不是我們正在尋找的抽象！我們只是想在樹上代表這種關係！當然，對於現實世界的問題來說，這會變得更加困難，因爲我們並不總是被賦予最好的數據結構，並且通常我們需要利用不同類型的數據結構來創建一些任務。

總是試圖找出問題的根源，然後從那裏出發。通常你會發現許多問題都是增加細節/數據的另一個簡單問題;或者甚至只是另一個問題的輕微變化。

祝你在學業上好運。