ツリーの配列実装のためのJava Link戦略？

Question

私の質問：
私はバイナリツリーで最も低い共通祖先を検索するJavaプログラムを持っています。その部分はでなければなりませんが、私の主な方法は私の質問ですので、正しくテストしていません。私は私の配列に格納されている文字からバイナリツリーを作成する必要があります。

私が見つけたもの
簡単に言えば、それほど多くはありません。私は主題に触れるいくつかのページを見つけましたが、その実装は他のコードと大きく異なるようです。誰かがガイドへのリンクを提供することもできますが、できればコード例があれば、おそらく私の質問に答えることができます。

マイコード

public class TreeMain 
{ 
    static TreeNode root; 

    public static void main(String args[]) 
    { 
     String[] myStringsChars = new String[26]; 

     for(int i = 0; i < 26; i++) 
     { 
      myStringChars[i] = new String(Character.toChars(i+65)); 
      System.out.println(myStringChars[i]); 
     } 

     // array to binary tree 

     TreeNode commonAncestor = findLowestCommonAncestor(firstNode, secondNode); 

     if(commonAncestor != null) { 
      System.out.println(commonAncestor.getContents()); } 
    } 

    public static TreeNode findLowestCommonAncestor(TreeNode node1, TreeNode node2) 
    {   
     return findLCA(root, node1, node2); 
    } 

    public static TreeNode findLCA(TreeNode node, TreeNode node1, TreeNode node2) 
    { 
     if (node == null) { 
      return null; } 

     if (node.getContents() == node1 || node.getContents() == node2) { 
      return node; } 

     TreeNode leftLCA = findLCA(node.getLeftChild(), node1, node2); 
     TreeNode rightLCA = findLCA(node.getRightChild(), node1, node2); 

     if (leftLCA!=null && rightLCA!=null) 
      return node; 

     // Otherwise check if left subtree or right subtree is LCA 
     return (leftLCA != null) ? leftLCA : rightLCA; 
    } 
} 

public class TreeNode<T extends Comparable>{ 
    private T contents; 
    private TreeNode<T> parent; 
    private TreeNode<T> leftChild; 
    private TreeNode<T> rightChild; 
    private int level; 

    public TreeNode(T data, TreeNode parent) 
    { 
     contents = data; 
     this.parent = parent; 
    }   

    public void setLeftChild(TreeNode node) 
    { 
     this.leftChild = node; 
    }   

    public void setRightChild(TreeNode node) 
    { 
     this.rightChild = node; 
    }   

    public boolean isContentEquals(T data) 
    { 
     return 0 == getContents().compareTo(data); 
    } 

    public T getContents() { 
     return contents; 
    } 

    public void setContents(T contents) { 
     this.contents = contents; 
    } 

    public TreeNode getParent() { 
     return parent; 
    } 

    public void setParent(TreeNode parent) { 
     this.parent = parent; 
    } 

    public TreeNode getLeftChild() { 
     return leftChild; 
    } 

    public TreeNode getRightChild() { 
     return rightChild; 
    } 

    public TreeNode findNodeOnTree(T contentToSearch) 
    { 
     List<TreeNode> nodes = new LinkedList(); 
     nodes.clear(); 
     nodes.add(this); 

     while(!nodes.isEmpty()) 
     { 
      TreeNode current = nodes.remove(0); 
      if(current.isContentEquals(contentToSearch)) 
      { 
       return current; 
      } 

      if(current.leftChild != null) 
      { 
       nodes.add(current.leftChild); 
      } 

      if(current.rightChild != null) 
      { 
       nodes.add(current.rightChild); 
      }  
     } 

     return null; 
    }   

    public int getLevel() { 
     return level; 
    } 

    public void setLevel(int level) { 
     this.level = level; 
    } 
} 

Answer 1

私はまだあなたのアルゴリズムを試していないが、しかし、あなたが探している部分が非常に簡単でなければなりません。これを達成するための簡単な方法は、あなたが念頭に置いているバイナリツリーの絵を描き、その絵をコードに変換するためのいくつかのメソッドを書くことです。ここで私はで始まるたいものです：

public TreeNode<T> addLeft(T key) {            
     TreeNode<T> tmp = new Node<>(key);           
     this.left = tmp;              
     tmp.parent = this; // if you are using parent pointers              
     return tmp; // for chaining purpose, so returned node can be subject to addition                
    }                   
    public TreeNode<T> addRight(T key) {           
     TreeNode<T> tmp = new TreeNode<>(key);           
     this.right = tmp;              
     tmp.parent = this;              
     return tmp;                
    } 

はツリーを構築するには、ルート・ノードを作成し、あなたのバイナリツリーの写真で見ると、その後addLeft()とaddRight()メソッドを呼び出すことができます。

TreeNode<Character> root = ...; // say root's key is 'A' 
    TreeNode<Character> left1 = root.addLeft('B'); 
    TreeNode<Character> right1 = root.addRight('C'); 
    //TreeNode<Character> left2 = left1.addLeft(); 
    // and so on for your character array. 

あなたが念頭に置いているツリーのinorder traversalとpreorder traversalを考え、という2つのトラバーサルを2つの別々の配列として表現し、2つのツリーを構築するこれら2つの配列を受け入れる別の手順を書いてくださいこれからこれは練習問題として残されています。