二叉树的遍历

前序遍历中序遍历后序遍历深度优先搜索广度优先搜索Morris前序遍历Morris中序遍历Morris后序遍历

为了便于理解各种遍历顺序，以下面二叉树为例进行遍历

C/C++二叉树：

struct node { int val; node *left; node *right; node(int x):val(x),left(NULL),right(NULL){} };

Python二叉树：

class node: def __init__(slef, x): self.val = x self.left = None self.rigth = None

前序遍历

先访问根结点然后遍历左子树，最后遍历右子树。 结果：$1—>2—>4—>5—>3—>6—>7$

C/C++实现：

void PreTraversal(node *root) { if root == NULL return; printf("%d",&root.val); PreTraversal(root.left); PreTraversal(root.right); }

Python实现：

def PreTraversal(root): if root is None: return print(root.val) PreTraversal(root.left) PreTraversal(root.right)

中序遍历

首先遍历左子树，然后访问根结点，最后遍历右子树。 结果：$4—>2—>5—>1—>6—>3—>7$

C/C++实现：

void InTraversal(node *root) { if root == NULL return; InTraversal(root.left); printf("%d",&root.val); InTraversal(root.right); }

Python实现：

def InTraversal(node root) { if root is None: return InTraversal(node.left) print(root.val) InTraversal(node.right) }

后序遍历

首先遍历左子树，然后遍历右子树，最后访问根结点 结果$4—>5—>2—>6—>7—>3—>1$

C/C++实现：

void PostTraversal(node *root) { if root == NULL return; PostTraversal(root.left); PostTraversal(root.right); printf("%d",&root.val); }

Python实现：

def PostTraversal(root) if root is None: return PostTraversal(root.left) PostTraversal(root.right) print(root.val)

深度优先搜索

同先序遍历

广度优先搜索

按照二叉树，一层一层的遍历 结果：$1—>2—>3—>4—>5—>6—>7$

C/C++实现：

#include<iostream> #include<algorithm> #include<queue> void bfs(node *root) { if root == NULL return queue<node> q; q.push(root); while(!q.empty()) { node x = q.front();q.pop(); printf("%d",x.val); if x.left != NULL q.push(x.left); if x.right != NULL q.push(x.right); } }

Python实现：

from collections import deque def bfs(root) if root is None return q = deque() q.append(root) while q: node x = q.popleft() print(x.val) if x.left: q.append(x.left) if x.right: q.append(x.right)

本质就是线索二叉树，遇到了填坑。。。话说还有好多树没补完。。。权值线段树，主席树，红黑树。。。

Morris前序遍历

Morris中序遍历

Morris后序遍历