インタビュー準備:二分木実装

今週、私たちは先週のイントロにツリーデータ構造を作ります、そして、我々は実際にJavaで二分木を実装するか、構築します.
あなたが木のデータ構造を聞いたことがないならば、速度を得るために、先週の記事をチェックしてください

我々の問題

以下のようなツリーデータ構造を示します.

このツリーをJavaでコード化するようお願いします.
左右
我々は、ちょうど我々の仕事を成し遂げるために少しの追加用語を必要とします.各親には2人の子供がいることに注意してください.私たちは、1人の子供が親の「左側」側にあると言うことができます、そして、1は「正しい」側にあります.
たとえば、上のツリーのイメージでは、ルートが値“1”を含むノードであることがわかります.左の子は「2」であり、右の子は「3」である.
我々の言語を簡素化するために、子ノードを参照するのではなく、親から子に導くエッジ(行)だけを参照することができます.したがって、ノード1の右端(またはちょうど右)がノード3につながると言うことができます.
その知識でコードを始めましょう
BinaryTreeクラスとメインクラスを宣言することから始めましょう.

public class BinaryTree{

    public static void main(String[] args) {

    }
}

それから私たちのツリーにエントリポイントを保持するためにプライベートフィールドが必要です.そのエントリポイントは“root”と呼ばれます.このフィールドをTreeNode型と宣言します(次にTreeNodeクラスを次に書きます).

public class BinaryTree{

    private TreeNode root;

    public static void main(String[] args) {

    }
}

TroNodeクラス型としてルートノートを宣言したので、TreeNodeクラスをよく書きます.
TreeNodeは、バイナリツリーを構築するために必要なすべてのノードを生成するクラスです.
我々は3つの項目で各トレノードを供給する必要があります:1)左のエッジ(私たちはそれを“左”と呼ばれる);2 )右端(右)と変数を呼び出してノードのデータを格納する変数.私たちのバイナリツリーには、単純にデータとして整数を含めることができます.

public class BinaryTree{

    private TreeNode root;

    private class TreeNode{
        private TreeNode left;  // left edge
        private TreeNode right; // right edge
        private int data;    //  here is where the data goes
    }

    public static void main(String[] args) {

    }
}

TestNodeクラスのフィールド宣言の下にコンストラクターメソッドを追加します.このコンストラクターは、作成したノードに挿入するデータをパラメータとして受け取ります.

public class BinaryTree{

    private TreeNode root;

    private class TreeNode{
        private TreeNode left;  // left edge
        private TreeNode right; // right edge
        private int data;    //  here is where the data goes

        public TreeNode(int data) {
             this.data = data;
        }
    }

    public static void main(String[] args) {

    }
}

我々は現在、我々の木をつくる準備ができています.TreeNodeクラスの下で、まだBinaryTreeクラス内で、CreateBinaryTreeメソッドを作成し、そのメソッド内でいくつかのノードを作成します.TestNodeクラスのインスタンスを作成することで、これらのノードを作成します.

public class BinaryTree{

    private TreeNode root;

    private class TreeNode{
        private TreeNode left;  // left edge
        private TreeNode right; // right edge
        private int data;    //  here is where the data goes

        public TreeNode(int data) {
             this.data = data;
        }
    }

   public void createBinaryTree() {

       TreeNode first = newTreeNode(1);
     //I’m create a TreeNode and calling it “first”
           // then I’m assigning the integer “1” as its value

    // Below: create more TreeNodes:
     TreeNode first = newTreeNode(2);
     TreeNode first = newTreeNode(3);
     TreeNode first = newTreeNode(4);
     TreeNode first = newTreeNode(5);
     TreeNode first = newTreeNode(6);
     TreeNode first = newTreeNode(7);

   }

    public static void main(String[] args) {

    }
}

我々がちょうど作成したこれらのノードを組織し始めましょう.
我々はすでに“root”として宣言したフィールドがあります.ツリーの図を見て(この記事の先頭にスクロールすると)、“1”ノードをルートとして表示します.また、ルートノードの“left”エッジには2つのノードがあることを図からわかります.ルートの右端は3ノードになります.それをコード化しましょう.(簡単にするために、クラス全体ではなくcreateBinaryTreeメソッドを表示します.

public void createBinaryTree() {

       TreeNode first = newTreeNode(1);
     //I’m create a TreeNode and calling it “first”
           // then I’m assigning the integer “1” as its value

    // Below: create more TreeNodes:
     TreeNode first = newTreeNode(2);
     TreeNode first = newTreeNode(3);
     TreeNode first = newTreeNode(4);
     TreeNode first = newTreeNode(5);
     TreeNode first = newTreeNode(6);
     TreeNode first = newTreeNode(7);

     // we want our root to be assigned to “first”
     root = first;

     //we know root’s left edge is the 2 node:
     first.left = second;
   // root’s right edge is the 3 node:
   first.right = third;

   }

それを片付けましょう.私たちの元の図から、2ノードの(別名2番目)左端が4つのノードにポイントしているのがわかります.それは5ノードに右側のポイントです.
3つ目のノード(別名3番目)に似ています:3番目の左側は6です.3番目は右です.

public void createBinaryTree() {

       TreeNode first = newTreeNode(1);
     //I’m create a TreeNode and calling it “first”
           // then I’m assigning the integer “1” as its value

    // Below: create more TreeNodes:
     TreeNode first = newTreeNode(2);
     TreeNode first = newTreeNode(3);
     TreeNode first = newTreeNode(4);
     TreeNode first = newTreeNode(5);
     TreeNode first = newTreeNode(6);
     TreeNode first = newTreeNode(7);


     root = first;


     first.left = second;

   first.right = third;

   //second’s left node is 4
   second.left = fourth;

   //second’s right node is 5
   second.right = fifth;

   //Last two nodes to place:
   third.left = sixth;
   third.right = seventh;

   }

Javaでのバイナリツリーの実装です.確かに、これは簡単な実装であり、これを行うためのfancier方法があります.たとえば、データの配列から開始し、その配列を使用してツリーを実装できます.しかし、私のダンスの先生が私に言ったように
ところで、あなたが私たちの元の図を最後に見た場合、あなたのインタビュアーがあなたに尋ねるならば、「OK、しかし、値4、5、6、7を含むノードは何をするか?」この質問に答えるために、技術的な単語を使用してください.と言う代わりに、“まあ、彼らは”ジッパー';を指して、あなたは言うことができる“彼らはNULLを指す.”
冒険を楽しむ.
そして、あなたの夢をコーディング!
ナマステ!