使用过java软件开发行业的遍历数据功能的小伙伴，应该对二叉树不会陌生了，那么也是否了解过二叉树的遍历算法有哪些呢?一般都会用到哪些地方呢?
首先呢，我们来引用一下leetcode中有关于二叉树节点的相关定义。
// Definition for binary tree
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};需要注意的是，以下所有的代码遵照都leetcode要求，将遍历结果储存在了vector
首先我们来看看前序遍历。
递归实现如下所示：
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
preorder(root);
return end;
}
void preorder(TreeNode *r){
if(!r)
return;
end.push_back(r->val);//先处理父节点
postorder(r->left);//再处理左子节点
postorder(r->right);//最后处理右子节点
}
vector<int> end;
};非递归实现如下所示：
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
preorder(root);
return end;
}
void preorder(TreeNode *r){
if(!r)
return ;
stack<TreeNode *>t;
t.push(r);
while(!t.empty()){
TreeNode *root=t.top();
t.pop();
end.push_back(root->val);
if(root->right)
t.push(root->right);//要改一起改！
if(root->left)//堆栈是后入先出。如果要先遍历左子数，应该先把右节点压入堆栈！
t.push(root->left);
}
}
vector<int> end;
};其次是后序遍历。
递归实现如下所示：
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
postorder(root);
return end;
}
void postorder(TreeNode *r){
if(!r)
return;
postorder(r->left);
postorder(r->right);
end.push_back(r->val);
}
vector<int> end;
}那么后序遍历比前序遍历实现起来是要稍微复杂一点的。这里就使用到了两个堆栈s,t。堆栈t用于储存正确的节点输出顺序，堆栈s可以帮助我们建立正确的t。后序遍历的输出顺序是先输出左子节点，输出右子节点之后，最后输出父节点。
非递归实现如下所示：
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
postorder(root);
return end;
}
void postorder(TreeNode *r){
if(!r)
return;
stack <TreeNode *>s,t;
TreeNode *root;
s.push(r);
while(!s.empty()){
root=s.top();
s.pop();
t.push(root);
if(root->left)
s.push(root->left);
if(root->right)
s.push(root->right);
}
while(!t.empty()){
end.push_back(t.top()->val);
t.pop();
}
}
vector<int> end;
};那么以上就是有关二叉树遍历算法的所有内容了，还想了解更多java常见问答的话，记得关注本站消息获取更多精彩内容。
推荐阅读：