二叉树是另一种树型结构,它的特点是每一个节点至多只有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。
二、先序遍历、中序遍历、后序遍历、层序遍历操作定义 1、先序遍历操作定义若二叉树为空,则空操作;否则
访问根节点先序遍历左子树先序遍历右子树 2、中序遍历操作定义若二叉树为空,则空操作;否则
中序遍历左子树访问根节点中序遍历右子树 3、后序遍历操作定义若二叉树为空,则空操作;否则
后序遍历左子树后序遍历右子树访问根节点 4、层序遍历操作定义若二叉树为空,则空操作;否则
遍历位于同一层的相关数据进入二叉树的下一层再次遍历处于同一层的数据直到将二叉树遍历完成 三、算法描述前序遍历:
function getListFrontDLR(obj) {console.log(obj.val);if(obj.left) {getListFrontDLR(obj.left);}if(obj.right) {getListFrontDLR(obj.right);}}中序遍历
function getListMiddleDLR(obj) {if(obj.left) {getListMiddleDLR(obj);}console.log(obj.val);if(obj.right) {getListMiddleDLR(obj);}}后序遍历
function getListBehindDLR(obj) {if(obj.left) {getListBehindDLR(obj);}if(obj.right) {getListBehindDLR(obj);}console.log(obj.val);}层序遍历
// 注意:arr为其相关的数组对象(该函数的存储过程类似于队列)function getListLevelDLR(arr) {// 存放层序遍历的结果let res = [];// 依次存放数组对象中统一层次的数据let tempArr = [];tempArr = arr.slice(0);// 通过该层次的相关的数据长度进行遍历while(tempArr.length) {// 依次相关层次进行遍历for(let i=0; i<tempArr.length;i++) {// 去除其同一层次上的同一个数据,同时删除掉该同一层次上的相关数据let temp = tempArr.shift();// 获取到该层次上所去除的数据的相关值res.push(temp.name);if(temp.children) {for(let j=0; j<temp.children.length; j++) {tempArr.push(temp.children[j]);}}}}return res;}注意:前序、中序和后序遍历算法与层序遍历所存放二叉树的数据结构不同,前序、中序和后序遍历算法是使用对象进行存放二叉树的数据的,而层序遍历是使用数组对象存放二叉树的数据的。