概念

二叉树遍历是二叉树的最基本的操作，其实现方式主要有： 1. 递归遍历 2. 非递归遍历 3. Morris遍历（自己度娘去，这里不讲）

递归遍历的实现非常容易，非递归实现需要用到栈。而Morris算法强大之处在于只需要使用O(1)的空间就能实现对二叉树O(n)时间的遍历。

二叉树结点的定义

每个二叉树结点包括一个值以及左孩子和右孩子结点，其定义如下：

//定义树 struct Tree { char data; Tree *LeftChild; Tree *RightChild; };

二叉树的遍历

二叉树的遍历，就是按照某条搜索路径访问树中的每一个结点，使得每个结点均被访问一次，而且仅被访问一次。常见的遍历次序有：

先序遍历：先访问根结点，再访问左子树，最后访问右子树中序遍历：先访问左子树，再访问根结点，最后访问右子树后序遍历：先访问左子树，再访问右子树，最后访问根结点

递归遍历

递归实现非常简单，按照遍历的次序，对当前结点分别调用左子树和右子树即可。

前序遍历

void PreOrderVisit(Tree *T) { if(nullptr == T) { cout << T->data << ends; PreOrderVisit(T->LeftChild); PreOrderVisit(T->RightChild); } }

中序遍历

void InOrderVisit(Tree *T) { if(nullptr == T) { InOrderVisit(T->LeftChild); cout << T->data << ends; InOrderVisit(T->RightChild); } }

后序遍历

void LastOrderVisit(Tree *T) { if(nullptr == T) { LastOrderVisit(T->LeftChild); LastOrderVisit(T->RightChild); cout << T->data << ends; } }

复杂度分析

二叉树遍历的递归实现，每个结点只需遍历一次，故时间复杂度为O(n)。而使用了递归，最差情况下递归调用的深度为O(n)，所以空间复杂度为O(n)。

非递归遍历

二叉树遍历的非递归实现，可以借助栈。

前序遍历

将根结点入栈； 每次从栈顶弹出一个结点，访问该结点； 把当前结点的右孩子入栈； 把当前结点的左孩子入栈。 按照以上顺序入栈，这样出栈顺序就与先序遍历一样：先根结点，再左子树，最后右子树。

void PreOrderVisit2(Tree *T) { stack<Tree *>S; Tree *p; p = T; while(!S.empty() || nullptr != p) { if(nullptr != p) { S.push(p); p = p->LeftChild; } else { p = S.top(); S.pop(); cout << p->data << ends; p = p->RightChild; } } }

中序遍历

初始化一个二叉树结点pNode指向根结点； 若pNode非空，那么就把pNode入栈，并把pNode变为其左孩子；（直到最左边的结点） 若pNode为空，弹出栈顶的结点，并访问该结点，将pNode指向其右孩子（访问最左边的结点，并遍历其右子树）

void InOrderVisit2(Tree *T) { stack<Tree *>S; //用来保存的节点的栈 Tree *p; p = T; while(!S.empty() || nullptr != p) { if(nullptr != p) //p非空 { S.push(p); cout << p->data << ends; p = p->LeftChild; } else { p = S.top(); S.pop(); p = p->RightChild; } } }

后序遍历

需要借助一个指针来标记已遍历过该结点。

void LastOrderVisit2(Tree *T) { stack<Tree *>S; Tree *p; Tree *pre = nullptr; p = T; while(!S.empty() || nullptr != p) { while(nullptr != p) { S.push(p); p = p->LeftChild; } p = S.top(); if(p->RightChild == NULL || p->RightChild == pre) { cout << p->data << ends; pre = p; p = nullptr; S.pop(); } else { p = p->RightChild; } } }

复杂度分析

二叉树遍历的非递归实现，每个结点只需遍历一次，故时间复杂度为O(n)。而使用了栈，空间复杂度为二叉树的高度，故空间复杂度为O(n)。