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

資訊專欄INFORMATION COLUMN

JavaScript數據結構與算法(九)二叉樹和二叉搜索樹

zhaofeihao / 3298人閱讀

摘要:二叉樹和二叉搜索樹二叉樹的節點最多只能有兩個節點,而二叉搜索樹只允許在左側的節點處存儲比父節點小的值,在右側節點存儲比父節點大的值。接收回調函數作為參數先序遍歷先序遍歷是以優先于后代節點的順序訪問沒和節點的。

樹是一種非順序數據結構,對于存儲需要快速查找的數據非常有用。樹是一種分層數據的抽象模型,現實生活中最常見的例子就是家譜,或者是公司的組織架構圖。

樹的相關術語

樹中的每一個元素都是節點,節點分為內部節點和外部節點。其中:
至少有一個子節點的節點稱為內部節點(例如圖中節點7,5,9,15,13,20),沒有子元素的節點為外部節點或葉節點(例如圖中節點3,6,8,10,12,14,18,25)。
位于樹頂部的節點叫做根節點,它沒有父節點。
節點的一個屬性是深度,節點的深度 取決于它的祖先節點的數量。樹的高度取決于深度的最大值。同樣一棵樹也可以分為層級,根節點在第0層,它的子節點在第1層,以此類推。

二叉樹和二叉搜索樹

二叉樹的節點最多只能有兩個節點,而二叉搜索樹只允許在左側的節點處存儲(比父節點)小的值,在右側節點存儲(比父節點)大的值。

創建BinarySearchTree
const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};
function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
};
class Node {
  constructor(key) {
    this.key = key;
    this.left = undefined;
    this.right = undefined;
  };
//下面我們會聲明BinarySearchTree類的基本骨架
class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn;
    this.root = undefined;
  }
向二叉搜索樹插入一個鍵
insert(key) {
    // special case: first key
    if (this.root == null) {
      this.root = new Node(key);
    } else {
      this.insertNode(this.root, key);
    }
  }

  insertNode(node, key) {
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      if (node.left == null) {
        node.left = new Node(key);
      } else {
        this.insertNode(node.left, key);
      }
    } else if (node.right == null) {
      node.right = new Node(key);
    } else {
      this.insertNode(node.right, key);
    }
  }
樹的遍歷 中序遍歷

中序遍歷是一種以上行順序訪問BST所有節點的遍歷方式,也就是從最小到最大的順序訪問所有節點。中序遍歷的一種應用是對樹進行排序操作。

//inOrderTraverse接收回調函數作為參數
inOrderTraverse(callback) {
    this.inOrderTraverseNode(this.root, callback);
  }

  inOrderTraverseNode(node, callback) {
    if (node != null) {
      this.inOrderTraverseNode(node.left, callback);
      callback(node.key);
      this.inOrderTraverseNode(node.right, callback);
    }
  }
先序遍歷

先序遍歷是以優先于后代節點的順序訪問沒和節點的。先序遍歷的一種應用是打印一個結構化的文檔、我們來看代碼實現

preOrderTraverse(callback) {
    this.preOrderTraverseNode(this.root, callback);
  }

  preOrderTraverseNode(node, callback) {
    if (node != null) {
      callback(node.key);
      this.preOrderTraverseNode(node.left, callback);
      this.preOrderTraverseNode(node.right, callback);
    }
  }
后序遍歷

后序遍歷就是縣訪問節點的后代節點,在訪問節點本身。后序遍歷的一種應用是計算一個目錄及其子目錄中所有文件所占空間的大小

postOrderTraverse(callback) {
    this.postOrderTraverseNode(this.root, callback);
  }

  postOrderTraverseNode(node, callback) {
    if (node != null) {
      this.postOrderTraverseNode(node.left, callback);
      this.postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  }
搜索樹中的值 搜索最小值
min() {
    return this.minNode(this.root);
  }

  minNode(node) {
    let current = node;
    while (current != null && current.left != null) {
      current = current.left;
    }
    return current;
  }
搜索最大值
max() {
    return this.maxNode(this.root);
  }

  maxNode(node) {
    let current = node;
    while (current != null && current.right != null) {
      current = current.right;
    }
    return current;
  }
搜索特定的值
search(key) {
    return this.searchNode(this.root, key);
  }

  searchNode(node, key) {
    if (node == null) {
      return false;
    }
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      return this.searchNode(node.left, key);
    } if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      return this.searchNode(node.right, key);
    }
    return true;
  }
移除節點
removeNode(node, key) {
    if (node == null) {
      return undefined;
    }
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      node.left = this.removeNode(node.left, key);
      return node;
    } if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      node.right = this.removeNode(node.right, key);
      return node;
    }
    // key is equal to node.item
    // handle 3 special conditions
    // 1 - a leaf node
    // 2 - a node with only 1 child
    // 3 - a node with 2 children
    // case 1 移除一個葉節點
    if (node.left == null && node.right == null) {
      node = undefined;
      return node;
    }
    // case 2 移除有一個左側或者右側子節點的節點
    if (node.left == null) {
      node = node.right;
      return node;
    } if (node.right == null) {
      node = node.left;
      return node;
    }
    // case 3    移除有兩個子節點的節點
    const aux = this.minNode(node.right);
    node.key = aux.key;
    node.right = this.removeNode(node.right, aux.key);
    return node;
  }
}

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

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

相關文章

  • 一篇文章學會二叉和二叉查找

    摘要:二叉樹和二叉查找樹一個父節點的兩個子節點分別稱為左節點和右節點。下圖展示了一顆二叉樹當考慮某種特殊的二叉樹,比如二叉查找樹時,確定子節點非常重要。實現二叉查找樹定義對象。現在可以創建一個類來表示二叉查找樹。因此二叉查找樹也被叫做二叉排序樹。 樹是計算機科學中經常用到的一種數據結構。樹是一種非線性的數據結構,以分層的方式存儲數據。 樹被用來存儲具有層級關系的數據,比如文件系統中的文件。 ...

    BaronZhang 評論0 收藏0
  • 每周一練 之 數據結構算法(Tree)

    摘要:假設一個二叉搜索樹具有如下特征節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。代碼實現二叉樹節點定義來源驗證二叉搜索樹解析 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第六周的練習題,最近加班比較多,上周主要完成一篇 GraphQL入門教程 ,有興趣的小伙伴可以看下哈。 ...

    zhonghanwen 評論0 收藏0
  • 每周一練 之 數據結構算法(Tree)

    摘要:假設一個二叉搜索樹具有如下特征節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。代碼實現二叉樹節點定義來源驗證二叉搜索樹解析這是第六周的練習題,最近加班比較多,上周主要完成一篇 GraphQL入門教程 ,有興趣的小伙伴可以看下哈。 下面是之前分享的鏈接: 1.每周一練 之 數據結構與算法(Stack) 2.每周一練 之 數據結構與算法(LinkedList) 3...

    fizz 評論0 收藏0
  • 學習javascript數據結構(四)——

    摘要:原文博客地址學習數據結構四樹知乎專欄簡書專題前端進擊者知乎前端進擊者簡書博主博客地址的個人博客人之所能,不能兼備,棄其所短,取其所長。通常子樹被稱作左子樹和右子樹。敬請期待數據結構篇最后一篇文章學習數據結構五圖參考文章樹數據結構二叉樹 前言 總括: 本文講解了數據結構中的[樹]的概念,盡可能通俗易懂的解釋樹這種數據結構的概念,使用javascript實現了樹,如有紕漏,歡迎批評指正。 ...

    Dean 評論0 收藏0

發表評論

0條評論

zhaofeihao

|高級講師

TA的文章

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