二叉树的遍历与创建

二叉树的遍历

分为:前序，中序，后序，层序。

前/中/后序,是根据跟节点遍历的前后顺序来定义的。

前序遍历

image.png

从根节点开始，先遍历当前节点值，再遍历左节点值，后遍历右节点值。
如上图得到: ABDGHCEIF

中序遍历

image.png

从根节点开始，先遍历左节点值，再遍历当前节点值，后遍历右节点值。
如上图得到: GDHBAEICF

后序遍历

image.png

从根节点开始，先遍历左节点值，再遍历右节点值，后遍历当前节点值。

实现代码

var three = {
  value: 5,
  left:{
    value: 3,
    left:{
      value: 2
    },
    right:{
      value:4
    }
  },
  right:{
    value:7,
    left:{
      value: 6
    },
    right:{
      value:8
    }
  }
}

以上为树的定义：

// 前序遍历
var arr = [];
function preOrder(three){
  arr.push(three.value) //1.取节点值(取值顺序在前面)
  if(three.left != null){
    preOrder(three.left) //2. 遍历左树
  }
  if(three.right != null){ //3.遍历右数
    preOrder(three.right)
  }
}
preOrder(three)
console.log("preOder",arr);
// 中序遍历
function midOrder(three){
  if(three.left != null){//1.遍历左树
    midOrder(three.left)
  }
  arr.push(three.value)//2.取节点值(取值顺序在中间)
  if(three.right != null){ //3. 遍历右树
    midOrder(three.right)
  }
}
arr = []
midOrder(three)
console.log("midOrder",arr)
// 后序遍历
function afterOrder(three){
  if(three.left != null){// 遍历左树
    afterOrder(three.left)
  }
  if(three.right != null){//遍历右树
    afterOrder(three.right)
  }
  arr.push(three.value)// 取节点值(取值顺序在后面)
}
arr = []
afterOrder(three)
console.log("afterOrder",arr)

二叉树的创建

如果按照遍历的思路，可分为四种创建模式
如果以#标记为空节点，以下图的前序创建的

image.png

var threeStr = "532##4##76##8##"
// 前序创建
function preCreateThree(arr){
  var result = {}
  var value = arr.shift()
  if(value && value !=="#"){  //先处理当前节点值
    result.value = value;
  }else{
    return null;
  }
  var left = preCreateThree(arr) // 再计算左树
  if(left){
    result.left = left;
  }
  var right = preCreateThree(arr) // 再计算右树
  if(right){
    result.right = right;
  }
  return result;
}

var result = preCreateThree(threeStr.split(""))
console.log(result)

ok，剩下两个写法基本类似。

层序遍历

image.png