JavaScriptでバイナリツリーを作成してトラバースするにはどうすればよいですか? (コード例)

この記事では、JavaScript を使用してバイナリ ツリーを作成し、走査する方法を紹介します。一定の参考値があるので、困っている友達が参考になれば幸いです。

1. まずバイナリ ツリー トラバーサルについて話しましょう。トラバーサル方法:

事前順序トラバーサル: 最初にルート ノードをトラバースし、次に左側のサブツリーをトラバースします。ツリー

順番トラバーサル: 最初に左のサブツリー、次にルート ノード、次に右のサブツリーをトラバースします。

後続のトラバーサル: 最初に左のサブツリーをトラバースし、次に右のサブツリー、次にルート ノード

上記のコード: 主に再帰を使用します

function TreeCode() {
    let BiTree = function (ele) {
        this.data = ele;
        this.lChild = null;
        this.rChild = null;
    }

    this.createTree = function () {
        let biTree = new BiTree('A');
        biTree.lChild = new BiTree('B');
        biTree.rChild = new BiTree('C');
        biTree.lChild.lChild = new BiTree('D');
        biTree.lChild.lChild.lChild = new BiTree('G');
        biTree.lChild.lChild.rChild = new BiTree('H');
        biTree.rChild.lChild = new BiTree('E');
        biTree.rChild.rChild = new BiTree('F');
        biTree.rChild.lChild.rChild = new BiTree('I');
        return biTree;
    }
}

//前序遍历
function ProOrderTraverse(biTree) {
    if (biTree == null) return;
    console.log(biTree.data);
    ProOrderTraverse(biTree.lChild);
    ProOrderTraverse(biTree.rChild);
}

//中序遍历
function InOrderTraverse(biTree) {
    if (biTree == null) return;
    InOrderTraverse(biTree.lChild);
    console.log(biTree.data);
    InOrderTraverse(biTree.rChild);
}

//后续遍历
function PostOrderTraverse(biTree) {
    if (biTree == null) return;
    PostOrderTraverse(biTree.lChild);
    PostOrderTraverse(biTree.rChild);
    console.log(biTree.data);
}

let myTree = new TreeCode();
console.log(myTree.createTree());
console.log('前序遍历')
ProOrderTraverse(myTree.createTree());
console.log('中序遍历')
InOrderTraverse(myTree.createTree());
console.log('后续遍历')
PostOrderTraverse(myTree.createTree());

の非再帰的走査バイナリ ツリー

• 深さ優先トラバーサル (主にスタックの先入れ後出しを使用)

• 幅優先トラバーサル (主にキューの先入れ先出しを使用します)

//深度优先非递归
function DepthFirstSearch(biTree) {
    let stack = [];
    stack.push(biTree);

    while (stack.length != 0) {
        let node = stack.pop();
        console.log(node.data);
        if (node.rChild) {
            stack.push(node.rChild);
        }
        if (node.lChild) {
            stack.push(node.lChild);
        }

    }

}


//广度优先非递归
function BreadthFirstSearch(biTree) {
    let queue = [];
    queue.push(biTree);
    while (queue.length != 0) {
        let node = queue.shift();
        console.log(node.data);
        if (node.lChild) {
            queue.push(node.lChild);
        }
        if (node.rChild) {
            queue.push(node.rChild);
        }
    }

}

深さの優先順位は主にスタックを使用し、最初に右のサブツリーを押し、次に左のサブツリーを押します

幅優先では主にキューを使用し、最初に左側のサブツリーに入り、次に右側のサブツリーに入ります。

深さ優先のトラバーサル結果は、事前順序トラバーサル ABDGHCEIF と同じです。幅優先のトラバーサル結果は、ABCDEFGHI

## です。

#2. バイナリ ツリーの作成

1 のバイナリ ツリーの作成方法は不器用すぎます。それは誤りです。完全なバイナリ ツリーに基づいて独自のバイナリ ツリーを構築してください空のデータは # で表されます。下図に示すように、これを拡張バイナリ ツリーと呼びます。プレオーダー トラバーサルのシーケンス AB#D##C## を取ります。

上記のコード: 再帰も使用します

//前序遍历得到的字符串
let strArr = 'AB#D##C##'.split('');

function BiTree(ele) {
    this.data = ele;
    this.lChild = null;
    this.rChild = null;
}
var newTree = new BiTree('#');

function createBiTree(biTree) {
    if (strArr.length == 0) return;
    let str = strArr.shift();
    if (str == '#') return;
    biTree.data = str;
    if (strArr[0] != '#') {
        biTree.lChild = new BiTree('#')
    }
    createBiTree(biTree.lChild);
    if (strArr[0] != '#') {
        biTree.rChild = new BiTree('#')
    }
    createBiTree(biTree.rChild);
}
createBiTree(newTree);
console.log(newTree);
ProOrderTraverse(newTree)

インオーダー トラバーサルまたはポストオーダー トラバーサルを使用してバイナリ ツリーを作成することもできます。ノードを生成し、コードの順序を入れ替えるだけで、左右のサブツリーを構築できます。

推奨チュートリアル: 「

JavaScript ビデオ チュートリアル 」

以上がJavaScriptでバイナリツリーを作成してトラバースするにはどうすればよいですか? (コード例)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。