欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Tree Traversal(二叉树的遍历)

程序员文章站 2022-06-16 12:04:41
...

Binary Tree 二叉树

Full Binary Tree 满二叉树 

叶节点都在最底层,其他节点都有左、右子节点。

  • N = 2^L - 1 


Tree Traversal(二叉树的遍历)

Complete Binary Tree 完全二叉树

除了最后一排,其他排都是满的,最后一排的子节点集中在左边。

  • 如果父节点是 i, 他的左子节点是 2*i , 右子节点是 2*i+1;

  • 如果子节点是i, 父节点就是floor(i/2) 


Tree Traversal(二叉树的遍历)

Binary Search Tree 有序二叉树

  1. 左子树上的值小于根节点;
  2. 右子树上的值大于根节点;
  3. 没有值相等的节点;
  4. 任意节点的左、右子树也为有序二叉树

Tree Traversal(二叉树的遍历)


Tree Traversals (Inorder, Preorder and PostOrder) 树的遍历(中序,前序,后序遍历)

  • Preorder 前序遍历: Root - Left - Right (NLR)  父节点 - 左子节点 - 右子节点
  • Inorder 中序遍历:Left - Root - Right (LNR) 左子节点 - 父节点 - 右子节点
  • Postorder 后续遍历:Left - Right - Root (LRN) 左子节点 - 右子节点 - 父节点

DFS (深度优先):

preorder(node)
    if (node == null) return;
    visit (node);
    preorder(node.left);
    preorder(node.right);
inorder(node)
    if (node == null) return;
    preorder(node.left);
    visit (node);
    preorder(node.right);
postorder(node)
    if (node == null) return;
    preorder(node.left);
    preorder(node.right);
    visit (node);

BFS (广度优先):

levelorder(root)
    q ← empty queue
    q.enqueue(root)
    while (not q.isEmpty())
      node ← q.dequeue()
      visit(node)
      if (node.left ≠ null)
        q.enqueue(node.left)
      if (node.right ≠ null)
        q.enqueue(node.right)

LeetCode Tree 问题:(缓慢更新)

https://github.com/JoyceHao/Online-Programming-Solution

Ref:

Wikipedia