【数据结构】05-二叉树

发表于 | 分类于 | 阅读次数：

介绍
树是一种经常用到的数据结构，用来模拟具有树状结构性质的数据集合。树里的每一个节点有一个根植和一个包含所有子节点的列表。

二叉树 是一种更为典型的树状结构。二叉树是每个节点最多有两个子树的树结构，通常子树被称作 左子树 和 右子树 。

Binary Tree

二叉树

Code

1
2
3
4
5
class Node {
    E e;
    Node left;
    Node right;
}

深度优先遍历

  • 前序遍历（DLR） ：先访问根节点，然后遍历左子树，最后遍历右子树。
  • 中序遍历（LDR） ：先遍历左子树，然后访问根节点，然后遍历右子树。
  • 后序遍历（LRD） ：先遍历左子树，然后遍历右子树，最后访问根节点。

广度优先遍历

  • 层序遍历 ：能够更快的找到问题的解。常用于计算最短路径。

二叉搜索树

二叉搜索树每个节点的值，大于其左子树的所有节点的值，小于其右子树的所有节点的值。即每一棵子树也是二分搜索树。存储的元素必须具有可比较性。

二叉搜索树

遍历结果
前序遍历5 - 3 - 1 - 2 - 4 - 9 - 7 - 6 - 8 - 10
中序遍历1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10
后序遍历2 - 1 - 4 - 3 - 6 - 8 - 7 - 10 - 9 - 5
层序遍历5 - 3 - 9 - 1 - 4 - 7 - 10 - 2 - 6 - 8

参考

LeetCode

0%