二叉树的前序遍历、中序遍历和后序遍历

1、概念

树是一种非顺序数据结构（节点，根节点，内部节点，外部节点，子树，深度）

节点包括（key left right）

二叉搜索树是二叉树的一种，左节点key值<父节点key值，右节点key值>=父节点key值

（1）前序遍历
a、访问根节点；b、前序遍历左子树；c、前序遍历右子树。

（2）中序遍历
a、中序遍历左子树；b、访问根节点；c、中序遍历右子树。

（3）后序遍历
a、后序遍历左子树；b、后续遍历右子树；c、访问根节点。

2、前序遍历和中序遍历还原二叉树

思想如下：
a、根据前序遍历结果，第一个元素为二叉树的根结点；
b、观察中序遍历结果，根结点左侧的为左子树，若左子树根结点前（后）再无任何元素，则左（右）子树的左分支为空；根结点右侧的为右子树，若右子树根结点前（后）再无任何元素，则左（右）子树的左分支为空；
c、上面的过程是递归的。先找到当前树的根结点，然后划分为左右子树，再进入左子树重复上面的过程，最后进入右子树重复上面的过程，最终还原一棵树。

例：已知
前序遍历：ABDHIEJKCFLMGNO
中序遍历：HDIBJEKALFMCNGO

按照上述步骤先画出二叉树，然后在进行求解后序遍历结果。结果为：HIDJKEBLMFNOGCA

练习：

1、前序遍历：GDAFEMHZ

  中序遍历：ADEFGHMZ

求得后序遍历结果为：AEFDHZMG

2序遍历：ADCEFGHB

  中序遍历：CDFEGHAB

求得后序遍历结果为：CFHGEDBA

3、中序遍历和后序遍历还原二叉树

思想如下：
a、根据后序遍历结果，最后一个元素为二叉树的根结点；
b、观察中序遍历结果，其中根结点左侧为左子树，若左子树根结点前（后）再无任何元素，则左（右）子树的左分支为空；其中根结点右侧为右子树，若右子树根结点前（后）再无任何元素，则左（右）子树的左分支为空；
c、上面的过程是递归的。先根据后序遍历结果找根结点，根结点左侧为左子树，右侧为右子树，再进入左子树重复上面的过程，最后进入右子树重复上面的过程，最终还原一棵树。

例：已知
中序遍历：HDIBJEKALFMCNGO
后序遍历：HIDJKEBLMFNOGCA

按照上述步骤先画出二叉树，然后在进行求解前序遍历结果。结果为：ABDHIEJKCFLMGNO

4、前序遍历和后序遍历还原二叉树

已知前序和中序，后序和中序遍历序列之后，可以唯一确定一棵二叉树。但是，只知道前序和后序遍历序列，是无法知道哪个结点是左子树还算右子树。

5.js实现二叉树的先序、中序、后序遍历方法

四种遍历的主要思想：
前序遍历：根左右;
中序遍历：左根右;
后序遍历：左右根;
广度遍历：按照层次一层层遍历;

// 创建一个树节点
function Node(key){
    this.key = key;
    this.left = null;
    this.right = null;
}
// 创建树的类
function treeList(){
    this.root = new Node('root'); // 根节点
    this.insertNode = insertNode; // 插入节点
    this.findNode = findNode; // 查找节点
    this.removeNode = removeNode; // 删除节点
    this.findMaxNode = findMaxNode; // 这棵树中的最小值在最后一层最左侧的节点
    this.findMinNode = findMinNode; // 最大值在最右端的节点。

    //先序遍历 主左右 先序遍历的一种应用是打印一个结构化的文档。
    this.preOrderTraverseNode = preOrderTraverseNode;
    // 中序遍历 左主右 是一种上行访问BST所有节点的遍历方式，也就是从最小到最大的顺序访问所有节点。中序遍历的一种应用就是对树进行排序操作。
    this.inOrderTraverseNode = inOrderTraverseNode;
    // 后序遍历 左右主 后序遍历的一种应用是计算一个目录和它的子目录中所有文件所占用空间的大小。
    this.postOrderTraverseNode = postOrderTraverseNode;
}

function insertNode(node, root){
    if (root === null){
        root = node;
    }else{
        if (node.key < root.key){
            if (root.left == null){
                root.left = node
            }else {
                insertNode(node, root.left)
            }
        }else {
            if (root.right == null){
                root.right = node
            }else {
                insertNode(node, root.right)
            }
        }
    }
}

function findNode(node, key){
    if (node == null){
        return false
    }else {
        if (key < node.key){
            return findNode(node.left, key)
        }else if(key > node.key) {
            return findNode(node.right, key)
        }else{
            return true
        }

    }
}

function findMaxNode(node){
    if (node){
        while(node && node.right !== null){
            node = node.right
        }
        return node.key
    }else{
        return null
    }
}

function findMinNode(node){
    if (node){
        while(node && node.left !== null){
            node = node.left
        }
        return node
    }else{
        return null
    }
}

// 三种情况：删除节点没有子节点，删除节点有一个子节点，删除节点有两个子节点，从node来删除
function removeNode(node, key){
    if (node === null){
        return null;
    }
    if (key < node.key){
        node.left = removeNode(node.left, key)
        return node
    }else if (key > node.key){
        node.right = removeNode(node.right, key)
        return node
    } else {
        // 找到删除的节点，删除，分三种情况
        // case1 删除节点没有子节点
        if (node.left === null && node.right === null){
            node = null;
            return node;
        }
        //case 2 删除节点有一个子节点
        if (node.left === null){
            node = node.right;
            return node;
        } else if (node.right === null){
            node = node.left;
            return node;
        }
        //case 3 删除节点有两个子节点，最复杂，用该右子树的最小节点aux的值代替删除节点值de，并删除aux
        var aux = findMinNode(node.right);// findMinNode返回的是节点
        node.key = aux.key;
        node.right = removeNode(node.right, aux.key);
        return node;
    }
}

// 回调函数用来定义我们对遍历到的每个节点进行操作
// 先序中左右
function preOrderTraverseNode(node, callback){
    if (node !== null) {
        callback(node.key)
        preOrderTraverseNode(node.left, callback)
        preOrderTraverseNode(node.right, callback)
    }
}
// 中序遍历左中右
function inOrderTraverseNode(node, callback){
    if (node !== null) {
        inOrderTraverseNode(node.left, callback);
        callback(node.key)
        inOrderTraverseNode(node.right, callback)
    }
}
// 后序遍历左右中
function postOrderTraverseNode(node, callback){
    if (node !== null) {
        postOrderTraverseNode(node.left, callback);
        postOrderTraverseNode(node.right, callback)
        callback(node.key)
    }
}

用例测试，树用object来表示

// 普通二叉树
let obj = {
    key: 10,
    left: {
        key: 11, 
        left: {
            key: 21, 
            left: {
                key: 31, 
                left: null,
                right: null
            },
            right: {
                key: 32,
                left: null,
                right: null
            }
        }, 
        right: {
            key: 22,
            left: null,
            right: null
        }
    },
    right: {
        key: 12,
        left: {
            key: 23,
            left: null,
            right: null
        },
        right: {
            key: 24,
            left: null,
            right: null
        }
    }
}
// 搜索二叉树
let treeObj = {
    key: 14,
    left: {
        key: 12, 
        left: {
            key: 9, 
            left: {
                key: 6, 
                left: null,
                right: null
            },
            right: null
        }, 
        right: {
            key: 13,
            left: null,
            right: null
        }
    },
    right: {
        key: 16,
        left: {
            key: 10,
            left: null,
            right: null
        },
        right: {
            key: 20,
            left: {key: 18, left: null, right: null},
            right: {key: 21, left: null, right: null}
        }
    }
}
var tree = new treeList();
// tree.preOrderTraverseNode(obj, console.log)
// tree.inOrderTraverseNode(obj, console.log)
// tree.postOrderTraverseNode(obj, console.log)


// console.log(tree.findMinNode(treeObj)) // 6
// console.log(tree.findNode(treeObj, 6)) // true
var node = new Node(30)
// tree.insertNode(node, treeObj)
// tree.inOrderTraverseNode(treeObj, console.log)
tree.removeNode(treeObj, 20)
tree.inOrderTraverseNode(treeObj, console.log)
// console.log(treeObj)

详情参考：
https://www.jianshu.com/p/3f3fed4b1b69
https://www.jb51.net/article/126850.htm