360网站开发,网络推广平台有哪些,公司介绍视频,福州网站设计知名乐云seo前言 对于二叉树来说#xff0c;遍历它有多种方式#xff0c;其中递归遍历是比较简单的#xff0c;但是非递归的实现就有一定的难度#xff0c;在这里介绍一种非递归实现二叉树遍历的方式。
1.前序遍历 1.1思路 其实对于二叉树的非递归实现#xff0c;实际上就是用代码来…前言 对于二叉树来说遍历它有多种方式其中递归遍历是比较简单的但是非递归的实现就有一定的难度在这里介绍一种非递归实现二叉树遍历的方式。
1.前序遍历 1.1思路 其实对于二叉树的非递归实现实际上就是用代码来模拟操作系统压栈和弹栈的过程。让我们一起来看看吧首先将一棵树 分为左边节点和左边节点的右子树。如图 然后借助于一个栈先将左边节点入栈入栈时要将节点的值存到数组中。将左边节点全部入栈后再来将左边节点的右子树入栈重复上述过程。直至栈为空并且当前的指针也为空此时完成二叉树的前序遍历。如图 1.2代码实现 vectorint preorderTraversal(TreeNode* root){vectorint v;stackTreeNode* sT;//1.处理左边节点//2.处理左边节点的右子树TreeNode * cur root;while(cur || !sT.empty() ){while(cur){//左边节点入栈sT.push(cur);v.push_back(cur-val);cur cur - left;}TreeNode* p sT.top();sT.pop();cur p - right;//左边节点的右子树入栈}return v;} 2.中序遍历 2.1思路 中序遍历的思路和前序遍历基本相同就是此时左边节点入栈时不会将左边节点的val插到数组中而是在栈中将节点的指针取出时再尾插到数组中。 2.2代码实现 vectorint inorderTraversal(TreeNode* root) {vectorint ret;stack TreeNode* sT;TreeNode* cur root;while(cur || !sT.empty()){//树的左边节点入栈while(cur){sT.push(cur);cur cur - left;}//取出栈顶节点的指针//将栈顶节点指针的val尾插到数组中TreeNode * top sT.top();sT.pop();//左边节点的右子树入栈cur top - right;ret.push_back(top-val);}return ret;}
3.后序遍历 3.1思路 后序遍历沿用了中序遍历的思路唯一不同的是将左边节点依次入栈后出栈时先处理当前节点的左子树然后将右子树入栈等处理完右子树后再来处理当前节点。 3.2代码实现
vectorint postorderTraversal(TreeNode* root) {TreeNode * cur root;TreeNode * back nullptr;//用来记录处理上一个节点vectorint ret;stackTreeNode* sT;while(cur || !sT.empty() ){//左边节点入栈while(cur){sT.push(cur);cur cur-left;}//取出栈顶数据TreeNode* top sT.top();if(top-right nullptr || top-right back){ret.push_back(top-val);back top;//记录处理过的节点sT.pop();}else{//左边节点的右子树入栈cur top - right;}}return ret;} 后续遍历需要注意的是在什么时候来对当前节点进行处理要先处理左右节点之后对当前节点进行处理如果右节点为空很好办直接判断右节点为不为空就可以了但是如果右节点不为空呢怎么确保右节点已经处理过了再来对当前节点进行处理呢这里提供一种较为简单的思路通过一个指针来记录上次处理的节点因为后序遍历总是按照左子树右子树和根的处理顺序来的所以我们只需要处理比较上一个处理的节点是不是当前节点的右子树就可以知道 当前节点的右子树是否已经被处理过了来判断当前节点是否需要处理。 讲的不好希望不要喷我。
