c++实现二叉树遍历
废话不多说，直接发车！
一、层次遍历
假设我们有如下二叉树。
我们进行层次遍历就像是在剥洋葱一样，一层一层往下来。
最终输出：FDJBEGKACIH.
我们用人脑编译能轻松想象出是如何实现的，但是在程序里该如何实现呢？
有人说：像链表那样整个指针不就行了？
我们用current指针指向root节点，下一步会来到D节点，但是我们无法来到右边的J节点。所以这种方法是行不通的！
再整个节点来连接之前的节点？显然会增加开销。
我们的解决方案是：将该节点孩子的引用或者地址放在一个队列之中，这样我们可以在稍后访问。
现在我们将根节点放入了队列，现在队列已经存放了节点，也就是说，只要队列非空，我们就可以从队列前部取出一个节点访问它，然后让它的孩子入队。
现在我们让根节点的孩子入队。现在我们有了一个访问过的节点和两个被发现了的节点。
现在我们可以继续从队首取出节点，访问它的孩子（入队）。
使用队列，我们这里做两件事，首先我们从一个节点开始移动，但是不会丢失对它的孩子的引用，因为我们保存了节点的引用。
然后队列是一个先进先出的结构，所以首先插入的节点会先被访问。因此我们能拿到正确的顺序。
出队时顺便拿到数据，我们让200出队，顺便让他的孩子入队。
这样我们就有2个被访问过的节点，3个发现的节点，6个未被发现的节点。
接着就是一样的操作。一旦队列为空，我们就实现了广度遍历。
总结一下就是通过检索入队，来实现拿到正确的遍历顺序。
cpp实现如下。
#include<iostream>#include<queue>using namespace std;struct Node{ int data; Node *left; Node *right;};void Leverorder(Node *root){ if(root=NULL)return; queue<Node*> Q; Q.push(root);//处理根节点 while(!Q.empty()){ Node* current= Q.front();//放回队首指针 cout<<current->data<<" "; if(current->left!=NULL){ Q.push(current->left); } if(current->right!=NULL){ Q.push(current->right); } Q.pop(); }}最后我们来讨论一下算法复杂度。
我们会访问每一个节点来获取他们的孩子然后入队，所以时间复杂度为O（n）
空间复杂度则要分情况，我们是通过队列来使用内存的。
特殊情况如，每一个节点就一个孩子，像链表那种。
这种队列里面只会存在一个节点。所以内存情况使用不一。
对于满二叉树，我们在最深层有n/2个节点。所以队列里最少为n/2.
所以空间复杂度范围是O(1)-O(n)
二、深度优先实现
假设我们还是有这么一颗二叉树。
在深度优先里，我们会先访问完一个方向的所有子树才会来到另外一个方向。
深度优先被分为前序（根左右），中序（左根右），后序（左右根）。
左子树和右子树将会和原树一样递归访问。
#include<iostream>using namespace std;struct Node{ char data; Node* left; Node* right;};//前序遍历(root->left->right)void preorder(Node* root){ if(root==NULL){//处理空树，亦是退出递归条件（如果一颗树或者子树为空，就退出。 return; } cout<<root->data; preorder(root->left); preorder(root->right);
}简单又明了。空间复杂度为O（h），h为树的高度。
中序遍历和后续遍历也差不多。
void Inorder(Node *root){ if(root==NULL){//处理空树，亦是退出递归条件（如果一颗树或者子树为空，就退出。 return; } Inorder(root->left); cout<<root->data; Inorder(root->right);}void Postorder(Node *root){ if(root==NULL){//处理空树，亦是退出递归条件（如果一颗树或者子树为空，就退出。 return; } Postorder(root->left); Postorder(root->right); cout<<root->data;}这三个算法的时间复杂度都是O（n），空间为O(h）【h是树的高度，也就是最坏为O(n)，最好是O(logn)】
部分信息可能已经过时