国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

數據結構與算法(樹) --javascript語言描述

henry14 / 1157人閱讀

摘要:重建二叉樹輸入某二叉樹的前序遍歷和中序遍歷的結果,請重建出該二叉樹。所以先通過前序遍歷找出根節點,然后將中序遍歷分為左右子樹兩組,最后對于每個子樹依次遞歸調用。

重建二叉樹

輸入某二叉樹的前序遍歷和中序遍歷的結果,請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6},則重建二叉樹并返回。

思路:二叉樹前序遍歷第一個點為根節點,中序遍歷順序為先左子樹然后根節點最后右子樹。所以先通過前序遍歷找出根節點,然后將中序遍歷分為左右子樹兩組,最后對于每個子樹依次遞歸調用。

function TreeNode(x) {
????this.val = x;
????this.left = null;
????this.right = null;
}
//pre為前序遍歷序列數組 vin為中序遍歷序列數組
function reConstructBinaryTree(pre, vin){
  if(pre.length == 0 || vin.length == 0) {
    return null;
  }
  let root = new TreeNode(pre[0]);
  //根節點在中序遍歷中的位置
  let index = vin.indexOf(pre[0]);
  let leftPre = pre.slice(1,index+1);//前序左子樹
  let rightPre = pre.slice(index+1);//前序右子屬
  let leftVin = vin.slice(0,index);//中序左子樹
  let rightVin = vin.slice(index+1);//中序右子樹
  //開始遞歸
  root.left = reConstructBinaryTree(leftPre,leftVin);
  root.right = reConstructBinaryTree(rightPre,rightVin);
  return root;
}

console.log(reConstructBinaryTree([1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]));
二叉樹的下一個節點

給定一個二叉樹和其中的一個結點,請找出中序遍歷順序的下一個結點并且返回。注意,樹中的結點不僅包含左右子結點,同時包含指向父結點的指針。

思路:根據中序遍歷的特點,要找到一個節點的下一個節點無非就是三種情況:1、有右子樹,這時只需要把其右孩子作為下一個遍歷的(并不是要找的)節點,然后沿著該節點的左子樹(如果有的話)出發,直到遇到葉子節點,那么該葉子節點就是其下一個要找的節點;2、沒有右子樹,則判斷該節點是否是其父節點的左孩子,如果是則其下一個要找的節點是其父節點;3、如果不是其父節點的左孩子,則把其父節點作為下一個遍歷的節點,向上回溯,直到找到父節點沒有父節點并且父節點是父節點的父節點的左孩子為止。綜合這三種情況就可以找到二叉樹中任意一個節點的下一個節點。

function TreeNode(x) {
????this.val = x;
????this.left = null;
????this.right = null;
    this.parent = null;
}
function getNext(node) {
  let curNode = null;
  //第一、判斷是否有右孩子
  if(node.right != null) {
    curNode = node.right;
    while(curNode.left !=null) {
      curNode = curNode.left;
    }
    return curNode;
  }
  //第二、判斷是否是其父節點的左孩子
  if(node.parent == null) {
    return null;
  }
  if(node.parent.left == node) {
    return node.parent;
  }
  //第三、向上找其父節點,直到父節點是其父節點的父節點的左孩子
  curNode = node.parent;
  while(curNode.parent != null) {
    if(curNode == curNode.parent.left) {
      return curNode.parent;
    }
    curNode = curNode.parent;
  }
  return null;
}

//構建二叉樹
let parentNode = createTree(
  ["a","b","d","e","h","i","c","f","g"],
  ["d","b","h","e","i","a","f","c","g"]);

let i = parentNode.left.right.right;//i節點
let b = parentNode.left;//b節點
let f = parentNode.right.left;//f節點
console.log(getNext(i).val);//a
console.log(getNext(b).val);//h
console.log(getNext(f).val);//c

//根據前序遍歷和中序遍歷構建一顆二叉樹
function createTree(pre,vin){
  function TreeNode(x) {
  ????this.val = x;
  ????this.left = null;
  ????this.right = null;
      this.parent = null;
  }
  //pre為前序遍歷序列數組 vin為中序遍歷序列數組
  function reConstructBinaryTree(pre, vin,parent){
    if(pre.length == 0 || vin.length == 0) {
      return null;
    }
    let root = new TreeNode(pre[0]);
    //根節點在中序遍歷中的位置
    let index = vin.indexOf(pre[0]);
    let leftPre = pre.slice(1,index+1);//前序左子樹
    let rightPre = pre.slice(index+1);//前序右子屬
    let leftVin = vin.slice(0,index);//中序左子樹
    let rightVin = vin.slice(index+1);//中序右子樹
    //開始遞歸
    root.parent = parent;
    root.left = reConstructBinaryTree(leftPre,leftVin,root);
    root.right = reConstructBinaryTree(rightPre,rightVin,root);
    return root;
  }

  return reConstructBinaryTree(pre,vin,null);
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/107472.html

相關文章

  • 數據結構算法:二叉算法

    摘要:因此,根據題目給出的先序遍歷和中序遍歷,可以畫出二叉樹選參考數據結構與算法描述實現二叉樹算法淺談數據結構二叉樹慕課網實現二叉樹算法前端樹控件騰訊軟件開發面試題 內容銜接上一章 數據結構與算法:常見排序算法 內容提要 什么是樹   - 為什么使用樹 二叉樹 二叉查找樹 紅黑樹 B、B+樹 堆 伸展樹 樹 可以點擊鏈接感受下筆者用d3.js畫的tree https://codepen...

    Little_XM 評論0 收藏0
  • 分類算法之決策(理論篇)

    摘要:后剪枝先創建完整的決策樹,然后再嘗試消除多余的節點,也就是采用減枝的方法。 起步 決策樹(decision tree)是一個樹結構,可以是二叉樹或非二叉樹,也可以把他看作是 if-else 規則的集合,也可以認為是在特征空間上的條件概率分布。 決策樹的結構 以一個簡單的用于是否買電腦預測的決策樹為例子: showImg(https://segmentfault.com/img/remo...

    jzzlee 評論0 收藏0
  • Java數據結構算法——(基本概念,很重要)

    摘要:有網友私信我,期待我的下一篇數據結構。前言數據結構與算法專題會不定時更新,歡迎各位讀者監督。本文介紹數據結構里一些復雜的數據結構樹,相應的會補充一些算法。除根節點外,每個節點又可以分為多個不相交的子樹。 聲明:碼字不易,轉載請注明出處,歡迎文章下方討論交流。有網友私信我,期待我的下一篇數據結構。非常榮幸文章被認可,也非常感謝你們的監督。 前言:Java數據結構與算法專題會不定時更新,歡...

    MangoGoing 評論0 收藏0

發表評論

0條評論

henry14

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<