《重学数据结构》之什么是二叉树?(下)

基于数组的顺序存储法

《重学数据结构》之什么是二叉树?(下)

若节点X存储在数组中下标为i的位置

2 * i 存储左子节点

2 * i + 1存储右子节点

i/2存储其父节点

由于这是个完全二叉树,所以仅“浪费”了一个下标0的存储位置。若是非完全二叉树,就会浪费较多存储空间:

《重学数据结构》之什么是二叉树?(下)

所以完全二叉树用数组存储最省内存,就不像链式存储法,还要存储左、右子节点的指针。所以完全二叉树要求最后一层的子节点都靠左。

堆也是一种完全二叉树,所以其最常用的存储方式就是数组。

二叉树的遍历

经典遍历

  • 前序遍历
    对于树中的任意节点来说,先打印这个节点,然后再打印它的左子树,最后打印它的右子树。
  • 中序遍历
    对于树中的任意节点来说,先打印它的左子树,然后再打印它本身,最后打印它的右子树。
  • 后序遍历
    对于树中的任意节点来说,先打印它的左子树,然后再打印它的右子树,最后打印这个节点本身。

《重学数据结构》之什么是二叉树?(下)

  • 这些都是递归过程。

递归代码的关键就是递推公式,递推公式的关键就是,如果要解决问题A,就假设子问题B、C已经解决,然后再来看如何利用B、C来解决A。

所以可以写出前、中、后序遍历的

递推公式

前序遍历

preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)

中序遍历

inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)

后序遍历

postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
void preOrder(Node* root) {
  if (root == null) return;
  print root // 此处为伪代码,表示打印root节点
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  print root // 此处为伪代码,表示打印root节点
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  print root // 此处为伪代码,表示打印root节点
}

时间复杂度

每个节点最多会被访问两次,所以遍历操作的时间复杂度,跟节点的个数n成正比,也就是说二叉树遍历的时间复杂度是O(n)。

参考

上一篇:JAVA输入输出(IO)之常用流


下一篇:《算法技术手册》一2.4.9 渐进增长小结