(没有写好代码)二叉树遍历 前序 中序 遍历 层次 深度优先遍历(DFS)广度优先遍历(BFS)

节点的度(degree):子书的个数

树的度:max(节点的度)

叶子节点(leaf):度为0 的节点

节点的深度(depth):从根节点到当前节点的唯一路径上的节点总数

节点的高度(height):从根节点到最远叶子节点的路径上的节点总数

树的深度:max(节点的深度)

树的高度:max(节点的高度)

二叉树

二叉树的特点

  • 每个节点的度最大为2
  • 左子树和右子树是有序的

前序

前序遍历:根结点 —> 左子树 —> 右子树

中序

中序遍历:左子树—> 根结点 —> 右子树

后序

后序遍历:左子树 —> 右子树 —> 根结点

层次

层次遍历:只需按层次遍历即可

深度优先遍历(DFS)

深度优先遍历:从根节点出发,沿着左子树方向进行纵向遍历,直到找到叶子节点为止。然后回溯到前一个节点,进行右子树节点的遍历,直到遍历完所有可达节点为止。

利用栈实现

广度优先遍历(BFS)

广度优先遍历:从根节点出发,在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。

利用队列实现

发表评论