数据结构之-二叉树

[Aaaaash]

树

树是一种分层数据的抽象模型,一个树结构包含一系列存在父子关系的节点,每个节点都有一个父节点(除了根节点)以及多个子节点.

• 树顶部的节点叫做根节点.
• 由一个子节点以及其后代组成子树.
• 节点有个深度属性,表示当前节点在树的层级.
• 所有节点深度的最大值被称为树的高度.

二叉树和二叉搜索树

二叉树中一个节点最多只能有两个子节点,分别为左侧节点以及右侧节点

二叉搜索树(BST)是另一种二叉树,但是它只允许左侧子节点存储比父节点小的值,而右侧子节点存储比父元素大的值

二叉树的节点Node类有一个指向左侧子节点的属性left以及一个指向右侧子节点的属性right,以及表示自身的属性key

class Node {
  constructor(public key: Node, public left?: Node, public right?: Node){}
}

class BinarySearchTree {
  root: Node;
  constructor() {
    this.root = null;
  }
}

向树中插入一个键

public insert(key: any) {
  const node = new Node(key);
  if (this.root === null) {
    this.root = node;
  } else {
    insertNode(this.root, node);
  }
}

向树中插入一个键分为三部

• 实例化一个新的node
• 如果不存在根节点,则新插入的节点赋值给根节点
• 如果已存在根节点,则调用insertNode函数递归插入

function insertNode(node: Node, newNode: Node) {
  // 当新节点的key小于当前节点时,从当前节点左侧递归查找空位
  if (newNode.key < node.key) {
    if (node.left === null) {
      node.left = newNode;
    } else {
      insertNode(node.left, newNode);
    }
  } else {
    // 新节点的key大于当前节点时,从当前节点右侧递归查找空位
    if (node.right === null) {
      node.right = newNode;
    } else {
      insertNode(node.right, newNode);
    }
  }
}

树的遍历

树的遍历分为先序,中序以及后序

中序遍历

中序遍历是一种以上行顺序访问BST所有节点的遍历方式,也就是以从小到大的方式顺序访问所有节点,可以使用递归的方式依次遍历左侧节点和右侧节点,以节点为null作为递归终止条件

public inOrderTraverse(callback: Function) {
  inOrderTraverse(this.root, callback);
}

function inOrderTraverse(node: Node, callback: Function) {
  if (node !== null) {
    inOrderTraverse(node.left, callback);
    callback(node.key);
    inOrderTraverse(node.right, callback);
  }
}

先序遍历

先序遍历是以优先于后代节点的顺序访问树

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

function preOrderTraverseNode(node: Node, callback: Function) {
  if (node !== null) {
    callback(node.key);
    preOrderTraverseNode(node.left, callback);
    preOrderTraverseNode(node.right, callback);
  }
}

后序遍历

后序遍历是指先访问节点的后代节点,再访问节点本身

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

function postOrderTraverseNode(node: Node, callback: Function) {
  if (node !== null) {
    postOrderTraverseNode(node.left, callback);
    postOrderTraverseNode(node.right, callback);
    callback(node.key);
  }
}

[blly5]

a