数据结构-树–二叉树-一一网

对于树形结构的数据来说，存在多叉树，二叉树。二叉树是指树的节点中最多只能有两个子节点：一个左侧子节点，另一个右侧子节点。这个定义有助于我们写出更高效地在树中插入、查找和删除节点的算法。二叉树在计算机科学的应用非常广泛。

对于二叉树，我们通常有以下几种遍历方式。

先序遍历

先序遍历是以后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。

有以下二叉树:


const bt = {
    val: '1',
    left: {
        val: '2',
        left: {
            val: '3',
            left: null,
            right: null
        },
        right: {
            val:'4',
            left: {
                val: '5',
                left:null,
                right: null
            }
        }
    },
    right: {
        val: "6",
        left: null,
        right: {
            val: "7",
            left: null,
            right: null
        }
    }
}
复制代码

二叉树结构如下图:

代码思路：

先读取根节点的值
读取左子树的值
读取右子树的值

那么，通过先序遍历遍历该二叉树方式如下：

function readBt(root) {
    if (!root) {return}
    console.log(root.val);
    readBt(root.left);
    readBt(root.right);
}

复制代码

中序遍历

代码思路:

先读取左子树
读取根节点
读取右子树

代码实现:

function readBt(root) {
    if (!root) {return}
    readBt(root.left);
    console.log(root.val);
    readBt(root.right);
    
}

复制代码

后序遍历

代码思路

后序遍历左子树
后序遍历右子树
读取根节点

代码实现:

function readBt(root) {
    if (!root) { return }
    readBt(root.left);
    readBt(root.right);
    console.log(root.val);
}

复制代码

非递归版本

对于二叉树的先中后序遍历，我们使用了递归去完成这些操作。我们知道，递归，其实就是程序堆栈去依次的执行。我们也可以自己使用栈这个数据结构去完成二叉树的先中后序遍历。

先序遍历非递归版本

代码思路:

根节点入栈
右子树入栈
左子树入栈
出栈并读取栈节点
重复1234

代码实现:

function readBt(root) {
  if (!root) {
    return;
  }
  const stack = [root];
  while (stack.length) {
    const item = stack.pop();
    console.log(item.val);
    if (item.right) {
      stack.push(item.right);
    }
    if (item.left) {
      stack.push(item.left);
    }
  }
}

复制代码

中序遍历非递归版本

代码思路:

参看中序遍历的递归版本。我们能得到一些启示。

function readBt(root) {
    if (!root) {return}
    readBt(root.left);
    console.log(root.val);
    readBt(root.right);
    
}

复制代码

将所有的左子树入栈。
左子树出栈，并读取栈值。
右子树入栈，右子树出栈，读取栈值，重复1，2，3

对于第一步来讲，我们需要将所有的左子树入栈，那么我们知道，二叉树的左子树其实类似于链表的数据结构。我们需要将所有的左子树入栈，相当于遍历链表操作。

function readBt(root) {
  if (!root) {
    return;
  }
  const stack = [];
  let p = root;
  while (stack.length || p) {
    while (p) { // 利用指针遍历链表
      stack.push(p);
      p = p.left; // 变更指针指向
    }
    // 所有左子树已经入栈
    const item = stack.pop();
    console.log(item.val);
    p = item.right; // 变更指针为右指针 进行下一步重复
  }
}

复制代码

后序遍历非递归版本

代码思路:

对于后序遍历，我们可以换一种思路去写。我们知道，后序遍历的顺序是左 => 右 => 根，先序遍历的顺序是根 => 左 => 右。非常类似。那么，我们完全可以利用两个栈结构。先进行”先序遍历”再将”先序遍历”的栈结构倒转过来。实现后序遍历即可。

代码实现:

function readBt(root) {
  if (!root) {
    return;
  }
  const stack = [root];
  const outputStack = [];
  while (stack.length) {
    const item = stack.pop();
    outputStack.push(item); // 此处不再打印，而是将节点入栈
    if (item.left) {
      stack.push(item.left);
    }
    if (item.right) {
      stack.push(item.right);
    }
  }
  while (outputStack.length) {
    const n = outputStack.pop();
    console.log(n.val);
  }
}


复制代码