JS数据结构学习(三)

树是一种分层数据的抽象模型。一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点)以及零个或多个子节点。位于树顶部的节点叫作根节点。它没有父节点。树中的每个元素都叫作节点,节点分为内部节点和外部节点。至少有一个子节点的节点称为内部节点。没有子元素的节点称为外部节点。

二叉树和二叉搜索树

二叉树中的节点最多只能有两个子节点:一个是左侧子节点,另一个是右侧子节点。
二叉搜索树是二叉树的一种,但是它只允许你在左侧节点存储(比父节点)小的值,在右侧节点存储(比父节点)大(或者等于)的值。

实现二叉搜索树

对于树,存在两个指针,一个指向左侧子节点,另一个指向右侧子节点。

  1. insert(key):向树中插入一个新的键。
  2. search(key):在树中查找一个键,如果节点存在,则返回true;如果不存在,则返回false。
  3. inOrderTraverse:通过中序遍历方式遍历所有节点。
  4. preOrderTraverse:通过先序遍历方式遍历所有节点。
  5. postOrderTraverse:通过后序遍历方式遍历所有节点。
  6. min:返回树中最小的值/键。
  7. max:返回树中最大的值/键。
  8. remove(key):从树中移除某个键。

    未完待续。。。