遍历二叉树

img1

创建二叉树数据结构：

function TreeCode() {
    let BiTree = function(ele){
        this.data = ele;
        this.left = null;
        this.right = null;
    }
    
    this.createTree = function(){
        let biTree = new BiTree('A');
        biTree.left = new BiTree('B');
        biTree.right = new BiTree('C');
        biTree.left.left = new BiTree('D');
        biTree.left.left.left = new BiTree('G');
        biTree.left.left.right = new BiTree('H');
        biTree.right.left = new BiTree('E');
        biTree.right.right = new BiTree('F');
        biTree.right.left.right = new BiTree('I');
        return biTree;
    }
}

深度优先遍历和广度优先遍历

/**
 * 深度优先遍历
 * 栈-后进先出
 * push pop right left
 * @param {Object} biTree
 */
function DepthFirstSearch(biTree){
    let stack = [];
    stack.push(biTree);
    
    while(stack.length != 0){
        let node = stack.pop();
        console.log(node.data);
        if(node.right){
            stack.push(node.right);
        }
        if(node.left){
            stack.push(node.left);
        }
    }
}
//DepthFirstSearch(new TreeCode().createTree());

/**
 * 广度优先遍历
 * 队列-先进先出
 * push shift left right
 * @param {Object} biTree
 */
function BreadthFirstSearch(biTree){
    let queue = [];
    queue.push(biTree);
    while(queue.length != 0){
        let node = queue.shift();
        console.log(node.data);
        if(node.left){
            queue.push(node.left);
        }
        if(node.right){
            queue.push(node.right);
        }
    }
}
// BreadthFirstSearch(new TreeCode().createTree());

前序遍历：先遍历根结点，然后左子树，再右子树
中序遍历：先遍历左子树，然后根结点，再右子树
后续遍历：先遍历左子树，然后右子树，再根结点

/**
 * 前序遍历
 * 先遍历根结点，然后左子树，再右子树
 * @param {Object} biTree
 */
function ProOrderTraverse(biTree) {
    if(biTree == null) return;
    console.log(biTree.data);
    ProOrderTraverse(biTree.left);
    ProOrderTraverse(biTree.right);
}
//ProOrderTraverse(new TreeCode().createTree());

/**
 * 中序遍历
 * 先遍历左子树，然后根结点，再右子树
 * @param {Object} biTree
 */
function InOrderTraverse(biTree) {
    if(biTree == null) return;
    InOrderTraverse(biTree.left);
    console.log(biTree.data);
    InOrderTraverse(biTree.right);
}
//InOrderTraverse(new TreeCode().createTree());

/**
 * 后序遍历
 * 先遍历左子树，然后右子树，再根结点
 * @param {Object} biTree
 */
function PostOrderTraverse(biTree) {
    if(biTree == null) return;
    PostOrderTraverse(biTree.left);
    PostOrderTraverse(biTree.right);
    console.log(biTree.data);
}
//PostOrderTraverse(new TreeCode().createTree());