二叉樹的遍歷方式主要有：先序遍歷、中序遍歷、后序遍歷、層次遍歷。先序、中序、后序其實(shí)指的是父節(jié)點(diǎn)被訪問的次序。若在遍歷過程中，父節(jié)點(diǎn)先于它的子節(jié)點(diǎn)被訪問，就是先序遍歷；父節(jié)點(diǎn)被訪問的次序位于左右孩子節(jié)點(diǎn)之間，就是中序遍歷；訪問完左右孩子節(jié)點(diǎn)之后再訪問父節(jié)點(diǎn)，就是后序遍歷。不論是先序遍歷、中序遍歷還是后序遍歷，左右孩子節(jié)點(diǎn)的相對(duì)訪問次序是不變的，總是先訪問左孩子節(jié)點(diǎn)，再訪問右孩子節(jié)點(diǎn)。而層次遍歷，就是按照從上到下、從左向右的順序訪問二叉樹的每個(gè)節(jié)點(diǎn)。
1、遞歸遍歷（前、中、后）
//節(jié)點(diǎn)結(jié)構(gòu)
/* function TreeNode(x) {
? ? this.val = x;
? ? this.left = null;
? ? this.right = null;
} */
//1、前序遍歷
function DLR(root){
? ? console.log(root.val);
? ? if(root.left){
? ? ? ? DLR(root.left);
? ? }
? ? if(root.right){
? ? ? ? DLR(root.right);
? ? }
}
//2、中序遍歷
function LDR(root){
? ? if(root.left){
? ? ? ? LDR(root.left);
? ? }
? ? console.log(root.val);
? ? if(root.right){
? ? ? ? LDR(root.right);
? ? }
}
//3、后序遍歷
function LRD(root){
? ? if(root.left){
? ? ? ? LRD(root.left);
? ? }
? ? if(root.right){
? ? ? ? LRD(root.right);
? ? }
? ? console.log(root.val);
}
2、層序遍歷
/* function TreeNode(x) {
? ? this.val = x;
? ? this.left = null;
? ? this.right = null;
} */
function levelTraversal(root){
if ( !root ) return false;//如果頭結(jié)點(diǎn)為空、返回假
? ? var result = []; //創(chuàng)建一個(gè)數(shù)組存放結(jié)果
? ? var tree = []; //創(chuàng)建一個(gè)數(shù)組存放二叉樹
? ? tree.push(root); //先傳入頭結(jié)點(diǎn)
? // 當(dāng)tree數(shù)組長度不為空
? ? while( tree.length ){
? ? ? ? var node = tree.shift();? ? // 將數(shù)組第一個(gè)結(jié)點(diǎn)放到node中? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? result.push(node.val); //將node結(jié)點(diǎn)的值壓入result數(shù)組中
? ? ? ? //如果node結(jié)點(diǎn)左子樹不為空
? ? ? ? if( node.left ){
? ? ? ? ? ? tree.push(node.left); // 將node結(jié)點(diǎn)的左子樹結(jié)點(diǎn)的值壓入tree數(shù)組中
? ? ? ? }
? ? ? ? //如果node結(jié)點(diǎn)又子樹不為空
? ? ? ? if( node.right ) {
? ? ? ? ? tree.push(node.right); //將node結(jié)點(diǎn)的右子樹結(jié)點(diǎn)的值壓入tree數(shù)組中
? ? ? ? }
? ? }
? ? return result; //返回result數(shù)組
}
3、重建二叉樹
根據(jù)二叉樹的前序遍歷和中序遍歷的結(jié)果，重建出該二叉樹。
function reConstructBinaryTree(pre, vin)
{
? ? var res = null;
? ? if(pre.length===1){
? ? ? ? res = {
? ? ? ? ? ? val: pre[0],
? ? ? ? ? ? left: null,
? ? ? ? ? ? right: null,
? ? ? ? }
? ? }else if(pre.length >1){
? ? ? ? var root = pre[0];
? ? ? ? var rootIndex = vin.indexOf(root);? //記錄根節(jié)點(diǎn)在中序遍歷中的位置
? ? ? ? var vinLeft = vin.slice(0,rootIndex);? //分割中序遍歷得到左子樹
? ? ? ? var vinRight = vin.slice(rootIndex+1,vin.length);? //分割中序遍歷得到右子樹
? ? ? ? pre.shift();? ? //去掉pre第一個(gè)元素并返回該元素。
? ? ? ? var preLeft = pre.slice(0,vinLeft.length);
? ? ? ? var preRight = pre.slice(vinLeft.length,pre.length);
? ? ? ? res = {
? ? ? ? ? ? val: root,
? ? ? ? ? ? left: reConstructBinaryTree(preLeft,vinLeft),
? ? ? ? ? ? right: reConstructBinaryTree(preRight,vinRight),
? ? ? ? }
? ? }
? ? return res;?
}
