博客

一、二叉树

1.首先介绍一下树，树是非顺序数据结构，一个树包含一系列存在父子节点，每个节点都有一个父节点以及零个或多个子节点，也就是一对多的关系

2.二叉树中的节点最多只能有两个子节点，二叉树要么为空，要么由根节点、左子树和右子树组成，左右子树本身也是二叉树

二、二叉树的遍历

1.先序遍历：先遍历根节点，再访问左子树，再访问右子树

2.中序遍历：先遍历左子树，再访问根节点，再访问右子树

3.后序遍历：先遍历左子树，在遍历右子树，再访问根节点

二叉树的遍历又分为递归和非递归两个版本，下面详细介绍

三、先序遍历

1.递归版本

const preOrder = function (node) {
  if (node) {
    console.log(node.value);
    preOrder(node.left);
    preOrder(node.right);
  }
};

2.非递归版本

function preOrder(node) {
  let stack = [];
  let root = node;
  stack.push(root);
  while (stack.length) {
    root = stack.pop();
    console.log(root.value);
    if (root.right) {
      stack.push(root.right);
    }
    if (root.left) {
      stack.push(root.left);
    }
  }
}

四、中序遍历

1.递归版本

const inOrder = function (node) {
  if (node) {
    inOrder(node.left);
    console.log(node.value);
    inOrder(node.right);
  }
};

2.非递归版本

function inOrder(node) {
  let stack = [];
  let root = node;
  stack.push(root);
  while (stack.length) {
    if (root.left) {
      stack.push(root.left);
      root = root.left;
    } else {
      root = stack.pop();
      console.log(root.value);
      if (root.right) {
        stack.push(root.right);
        root = root.right;
      }
    }
  }
}

五、后序遍历

1.递归版本

const postOrder = function (node) {
  if (node) {
    postOrder(node.left);
    postOrder(node.right);
    console.log(node.value);
  }
};

2.非递归版本

function postOrder(node) {
  let stack = [];
  let res = [];
  let root = node;
  stack.push(root);
  while (stack.length) {
    root = stack.pop();
    res.unshift(root.value);
    if (root.left) {
      stack.push(root.left);
    }
    if (root.right) {
      stack.push(root.right);
    }
  }
  res.forEach((item) => console.log(item));
}