Tree Traversal(二叉树的遍历)
程序员文章站
2022-06-16 12:04:41
...
Binary Tree 二叉树
Full Binary Tree 满二叉树
叶节点都在最底层,其他节点都有左、右子节点。
N = 2^L - 1
Complete Binary Tree 完全二叉树
除了最后一排,其他排都是满的,最后一排的子节点集中在左边。
如果父节点是 i, 他的左子节点是 2*i , 右子节点是 2*i+1;
如果子节点是i, 父节点就是floor(i/2)
Binary Search Tree 有序二叉树
- 左子树上的值小于根节点;
- 右子树上的值大于根节点;
- 没有值相等的节点;
- 任意节点的左、右子树也为有序二叉树
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
上一篇: 将子查询转化成连表查询有关问题
下一篇: 做web 推送 怎么隐藏这个ajax请求