数据结构与算法(16)-二叉树

1. 树

  • 父节点
    • 上层的节点
  • 兄弟节点
    • 父节点是同一个节点
  • 叶节点
    • 没有子节点的节点
  • 高度
    • 节点到叶子节点的最长路径
  • 深度
    • 根节点到这个节点所经历的边的个数
    • 节点的深度 + 1

2. 二叉树

每个节点最多有两个分叉的树,即最多有两个子节点

fig1.jpg
2 显示的是满二叉树,特点是叶子节点都在最底层,出了叶子节点之外,每个节点都有左右两个子节点

3 叶子节点都在最底下两层,并且出了最后一层,其他的层的节点数量都要达到最大,并且最后一层的节点都是靠左排列的,这种二叉树叫做完全二叉树。

2.1 如何表示/ 存储一棵二叉树?

2.1.1 基于指针或者引用的二叉链式存储法

fig2.jpg

每个节点都有三个字段,其中一个存储数据,另外两个指向左右子节点的指针。因此通过根节点,我们就可以通过左右子节点的指针将整棵树都串起来了。

2.1.2 基于数组的顺序存储法

fig3.jpg
如果节点X存储在数组中下标为i的位置,下标为2i的位置存储的是左子节点,下标为2i + 1的位置存储的就是右子节点。下标为i/2的位置存储的就是它的父节点了。通过这种方式,我们只要知道根节点存储的位置,就可以通过下标计算,把整棵树都串起来。 不过对于一棵非完全二叉树而言,会浪费比较多的数组存储空间的。

2.2 二叉树的遍历

2.2.0 递归公式

fig4.jpg

二叉树的遍历整体就是一个递归的过程

写递归代码的关键,就是看能不能写出一个递推公式。而递推公式的关键,就是如果要解决问题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节点
}

2.2.1 前序遍历

对于树中的任意节点来说,先打印这个节点,然后再打印它的左子树,最后打印它的右子树。

2.2.2 中序遍历

对于树中的任意节点来说,先打印它的左子树,然后再打印它本身,最后打印它的右子树

2.2.3 后序遍历

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

3. 二叉查找树

支持动态数据集合的快速插入、删除、查找操作。


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 stone2paul@gmail.com

文章标题:数据结构与算法(16)-二叉树

文章字数:876

本文作者:Leilei Chen

发布时间:2020-02-10, 02:31:37

最后更新:2020-02-10, 02:32:28

原始链接:https://www.llchen60.com/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95-16-%E4%BA%8C%E5%8F%89%E6%A0%91/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏