javascriptは二叉の木を再帰的に遍歴することと再帰的でないことを実現します.

まず、二叉樹の構造を実現します.

(function () {

  /**
   *         Node     
   */
  function Node(data) {
    this.left = null;
    this.right = null;
    this.data = data;
  }

  /**
   *       
   *        0      
   */
  function createTree (data) {
    let dat = data.shift();
    let p = null;

    if (dat != 0) {
      p = new Node(dat);
      p.left = createTree(data);
      p.right = createTree(data);
    }

    return p;
  }

//        
let arr = [1,2,4,0,0,5,0,0,3,6,0,0,7,0,0],
    root = createTree(arr);

})();

再帰遍歴する

//     
function prevTraverse (node) {
  if (node === null) return;

  prevTraverse(node.left);
  console.log(node.data);
  prevTraverse(node.right);
}

//     
function middleTraverse (node) {
  if (node === null) return;

  console.log(node.data);
  middleTraverse(node.left);
  middleTraverse(node.right);
}

//     
function lastTraverse (node) {
  if (node === null) return;

  lastTraverse(node.left);
  lastTraverse(node.right);
  console.log(node.data);
}

再帰遍歴しない
再帰順ではない

、巡回中のノード

をスタックarrで保存します.

は、まずルートノードをスタックに保存し、スタックが空の

であるまで巡回巡回する.

は、プリアンブルであるので、第1のステップはルートノード

を印刷する.

印刷が完了したら、現在のノードに右の子供がいるかどうかを調べ、右の子供は先にスタック

に入れます.

は、現在のノードに左の子供がいるかどうかを調べ、左の子供は後でスタック

に入る.

右の子供が左の子供より先にスタックに入る理由は、次の循環の中で左の子供が先にスタックを出て、右の子供が後でスタックを出ます.

右の子供がスタックを出た後、ルートノードに相当します.まずルートノードを印刷してから、下の方に引き続き上記のようなルックアップステップ

を実行します.

function prevTraverseUnRecursion (root) {
  let arr = [],
      node = null;

  arr.unshift(root);

  while (arr.length !== 0) {
    node = arr.shift();
    console.log(node.data);

    if (node.right !== null) {
      arr.unshift(node.right);
    }

    if (node.left !== null) {
      arr.unshift(node.left);
    }
  }
}

再帰的でない順番に巡回します.

非再帰中に、まず左の子供を訪問し、ルートノードを訪問し、最後に右の子供

を訪問します.

したがって、実行中に、ドメインのルートノードをまたぐプロセスが必要となり、スタックはすでに空きました.この時は右の子供を訪問する必要がある

です.

したがって、スタックが空であり、ノードが空である場合、全体のアクセスプロセスが終了することを示す

.

そうでなければ、現在のノードが空であれば、最下部に到達したことを示す.現在のノードが空でない場合は、下へ

を検索し続けます.

function middleTraverseUnRecursion (root) {
  let arr = [],
      node = root;

  while (arr.length !== 0 || node !== null) {
    if (node === null) {
      node = arr.shift();
      console.log(node.data);
      node = node.right;
    } else {
      arr.unshift(node);
      node = node.left;
    }
  }

}

再帰的でない場合は、順番に巡回します.

私たちはスタックを使用して前に通過したノードを保存し、まずルートノードをスタックに保存し、スタックトップのノード

をパルトノードで記録する.

私達はparent Nodeを使って、parent Nodeの左の子供と右の子供が空です.

サイクルを使用して、ARrが空の

であるまでスタックarrを巡回する必要があります.

の第一の状況は下を向いて検索する過程です.最近印刷されたノードtrverseNodeはparent Nodeの左の子供でもないし、parent Nodeの右の子供でもない

です.

第二のケースも絶えず探しています.ただし、この時には印刷し終わったばかりの左の子供がtrverseNodeになり、parent Nodeの右の子供

になりました.

の第3のケースは、parent Nodeの左の子供と右の子供が存在しないということであり、この時はすでに最下部に達しています.ポップアップスタックの一番上の要素からプリントしなければならないということです.また、最近印刷されたノードtrverseNode

を更新します.

function lastTraverseUnRecursion (root) {
  let arr = [],
      parentNode = null,
      traverseNode = null;

  if (root !== null) {
    arr.unshift(root);

    while (arr.length !==0) {
      parentNode = arr[0];
      if (parentNode.left !== null && traverseNode !== parentNode.left &&traverseNode !== parentNode.right) {
        arr.unshift(parentNode.left);
      } else if (parentNode.right !== null && traverseNode !== parentNode.right) {
        arr.unshift(parentNode.right);
      } else {
        traverseNode = arr.shift();
        console.log(traverseNode.data);
      }
    }
  }
}