企业做网站维护,空调安装工做网站,河源盛世网站建设,不会百度吗网页生成二叉树的前序、中序、后序 遍历属于深度优先搜索方式#xff0c;本文使用递归法实现前序、中序、后序的遍历方法#xff0c;代码如下#xff1a;
#include iostream
#include vectorstruct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode(int …二叉树的前序、中序、后序 遍历属于深度优先搜索方式本文使用递归法实现前序、中序、后序的遍历方法代码如下
#include iostream
#include vectorstruct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x),left(nullptr),right(nullptr){};
};//前序遍历
void preorderTraversal(TreeNode* root,std::vectorint vec)
{if(root nullptr){return;}vec.emplace_back(root-val);preorderTraversal(root-left,vec);preorderTraversal(root-right,vec);
}//中序遍历
void inorderTraversal(TreeNode* root,std::vectorint vec)
{if(root nullptr){return;}preorderTraversal(root-left,vec);vec.emplace_back(root-val);preorderTraversal(root-right,vec);
}//后序遍历
void postOrderTraversal(TreeNode* root,std::vectorint vec)
{if(root nullptr){return;}preorderTraversal(root-left,vec);preorderTraversal(root-right,vec);vec.emplace_back(root-val);
}void deleteTree(TreeNode* root)
{if(root nullptr){return;}deleteTree(root-left);deleteTree(root-right);delete root;root nullptr;
}int main()
{//创建二叉树// 1// / \// 2 3// / \ / \// 4 5 6 7// / \// 8 9//前序遍历中左右: 1 2 4 8 9 5 3 6 7//中序遍历左中右: 2 4 8 9 5 1 3 6 7//后序遍历左右中: 2 4 8 9 5 3 6 7 1TreeNode* root new TreeNode(1);root-left new TreeNode(2);root-right new TreeNode(3);root-left-left new TreeNode(4);root-left-right new TreeNode(5);root-right-left new TreeNode(6);root-right-right new TreeNode(7);root-left-left-left new TreeNode(8);root-left-left-right new TreeNode(9);std::vectorint vec;preorderTraversal(root,vec);printf(****************\n);for(int i 0; i vec.size();i){printf(%d\t,vec.at(i));}printf(\n);std::vectorint().swap(vec);inorderTraversal(root,vec);printf(****************\n);for(int i 0; i vec.size();i){printf(%d\t,vec.at(i));}printf(\n);std::vectorint().swap(vec);postOrderTraversal(root,vec);printf(****************\n);for(int i 0; i vec.size();i){printf(%d\t,vec.at(i));}printf(\n);// delete root-left-left-left;
// delete root-left-left-right;deleteTree(root);std::vectorint().swap(vec);return 0;
}程序运行结果如下 附加知识
二叉树遍历的递归实现详解先序、中序、后序和层次遍历 - violet-evergarden - 博客园 (cnblogs.com)
C实现二叉树 前、中、后序遍历递归与非递归非递归实现过程最简洁版本_后序遍历的非递归算法-CSDN博客 深度优先搜索DFS和广度优先搜索BFS-CSDN博客
