二叉树的遍历
2017-08-02 本文已影响30人
熊白白
前中后序的递归实现
void ff(TreeNode* p,vector<int> &v){
if(p==nullptr)
return;
v.push_back(p->val);
ff(p->left,v);
ff(p->right,v);
}
void mf(TreeNode* p,vector<int> &v){
if(p==nullptr)
return;
mf(p->left,v);
v.push_back(p->val);
mf(p->right,v);
}
void bf(TreeNode* p,vector<int> &v){
if(p==nullptr)
return;
bf(p->left,v);
bf(p->right,v);
v.push_back(p->val);
}
前中后序的非递归标准实现
void ff(TreeNode* root,vector<int>& v){
TreeNode* p=root;
stack<TreeNode*> s;
while(!s.empty() || p){
while(p){
v.push_back(p->val);//Visit
s.push(p);
p=p->left;
}
p=s.top();
s.pop();
p=p->right;
}
}
void mf(TreeNode* root,vector<int>& v){
TreeNode* p=root;
stack<TreeNode*> s;
while(!s.empty() || p){
while(p){
s.push(p);
p=p->left;
}
p=s.top();
v.push_back(p->val);//Visit
s.pop();
p=p->right;
}
}
void bf(TreeNode* root,vector<int>& v){
TreeNode* p=root,*plast=nullptr;
stack<TreeNode*> s;
while(!s.empty() || p){
while(p){
s.push(p);
p=p->left;
}
p=s.top();
if(!p->right || plast==p->right){
v.push_back(p->val);//Visit
s.pop();
plast=p;
p=nullptr;//既然没有右子树或者右子树已经被访问，那么p就没有用了，应该让它失效，这样才会从栈顶，弹出根节点
}else
p=p->right;
}
}
总结
整体的思路是这样的：
- 指针p指向root，创建栈
- 当栈不为空或p有效时，循环：
- 沿着根节点的左分支一路压入根节点（如果是前序遍历此时就可以访问p）
- 循环结束时p为空，此时p失效。
- 当p失效时，从栈顶弹出结点（如果是中序遍历此时就可以访问p）。此时弹出的一定是底层的结点。
- 对该结点进行访问，并尝试访问其右分支。
- 右分支的结点视作根节点，重复以上过程。
当后序遍历时，预先设置plast为空，以记录上一次访问的结点。
取栈顶元素作p，
- 当p无右分支或p的右分支已被访问时
- 访问p
- 弹出栈顶
- 更新plast
- 设置p失效（p失效之后才会从栈顶弹元素）
- 否则（当p有右分支且右分支没有被访问）
p=p->right 右分支作根节点进入循环进行访问
简单来说，p相当于当前操作的子树；当p失效时，弹出栈顶元素，即使当前操作的子树的根。左边处理完了，就索引根，通过根来索引右子树。
层遍历与前序遍历的非标准实现
前序遍历的非标准实现
流程：
- 判断root是否为空
- 指针p指向root
- 创建栈并压入p
- 当栈不为空时：循环
- 弹出栈顶元素进行访问
- 如果该元素有右分支，压入右孩子
- 如果该元素有左分支，压入左孩子
void ff2(TreeNode* root,vector<int>& v){
if(!root)
return;
TreeNode* p=root;
stack<TreeNode*> s;
s.push(p);
while(!s.empty()){
p=s.top();
s.pop();
v.push_back(p->val);
if(p->right)
s.push(p->right);
if(p->left)
s.push(p->left);
}
}
层遍历
流程：
- 判断root是否为空
- 指针p指向root
- 创建队列并压入p
- 当队列不为空时：循环
- 弹出队首元素进行访问
- 如果该元素有左分支，压入左孩子
- 如果该元素有右分支，压入右孩子
void layer(TreeNode* root,vector<int> &v){
if(!root)
return;
TreeNode* p=root;
queue<TreeNode*> q;
q.push(p);
while(!q.empty()){
p=q.front();
v.push_back(p->val);
q.pop();
if(p->left)
q.push(p->left);
if(p->right)
q.push(p->right);
}
}
扩展：层打印
按层打印到一个二维数组中。
该问题的难点在于如何判断当前访问的结点是不是某一行的行末。所以我们使用nlast指针，来记录当前行的行末；用last指针来记录最近压入队列的结点。
- 初始时last和nlast都为root
- 循环时，last记录最近压入的结点
- 当前访问的结点等于nlast时，表示已经访问到了某一行的行末。这个时候做行末相关的处理，并将nlast更新为last。因为当某一行访问完成后，新压入的结点，一定是下一行的行尾。
void layer(TreeNode* root,vector<vector<int> > &v){
if(!root)
return;
TreeNode* p=root;
queue<TreeNode*> q;
q.push(p);
TreeNode* last=root,*nlast=root; //last和nlast初始化为root
vector<int> temp;
while(!q.empty()){
p=q.front();
q.pop();
temp.push_back(p->val);
if(p->left){
q.push(p->left);
last=p->left; //记录last
}
if(p->right){
q.push(p->right);
last=p->right;//记录last
}
if(p==nlast){//如果p指针已经到达了一行的行末，那么最新压入栈的last一定是下一行的行末
v.push_back(temp);
temp.clear();
nlast=last;
}
}
}
扩展：判满、完全二叉树
判断完全二叉树
思路：按层遍历二叉树，直到发现第一个非满结点（单左或叶子结点，不可以是单右）。在这个结点之后，所有的结点都是叶子结点。那么该树就是完全二叉树。
bool chk(TreeNode* root) {
//按层遍历，找到第一个不满结点，其后所有结点必须是叶子
if(!root)
return false;
TreeNode *p=root;
queue<TreeNode*> que;
que.push(p);
int find=0;
while(!que.empty()){
p=que.front();
que.pop();
if(p->left){
que.push(p->left);
}
if(p->right){
que.push(p->right);
}
if(!p->right){//没有右树，就涵盖了叶子和单左 两种情况
find=1;
continue;
}else{//如果有右树，看看是叶子，还是单右。单右直接返回false
if(!p->left)
return false;
}
if(find==1 && (p->left || p->right)){//注意优先级，&&高于||
return false;
}
}
return true;
}
判断满二叉树
思路：按层遍历二叉树，直至发现第一个非满结点（且必须是叶子结点）。在该结点之后的所有结点都是叶子结点，且该结点前一个节点是某行的行末。
实现：用一个plast指针来记录上次访问的结点。其他按照判完全二叉树的方法来进行即可。代码未经过验证就不写了。另外，nlast更新时可以按照nlast=nlast->right来更新，这样就不用last指针了。
扩展：二叉树的规则化构建
根节点的值是1，其左右孩子分别是1和2，每个孩子的左右孩子依然是1和2。以此来构建N层的二叉树。
思路：首先需要保证N大于0.建立总根节点root，然后初始化p和nlast为root。然后共遍历n-2层，每一层遍历时都把结点添加左右孩子。比如n==3时，应该遍历中间的一层就好。
TreeNode* buildBt(int n){
if(!n)
return nullptr;
TreeNode* root=new TreeNode(1);
TreeNode *p=root,*nlast=root;
queue<TreeNode*> que;
que.push(p);
----n;
while(n){
p=que.front();
que.pop();
p->left=new TreeNode(1);
p->right=new TreeNode(2);
que.push(p->left);
que.push(p->right);
if(p==nlast->right){//如果发现遍历至某一行尾，则更新n和nlast
--n;
nlast=p;
if(n<=0)
break;
}
}
return root;
}
