二叉树遍历的非递归实现-创新互联
二叉树的遍历可以使用递归的方式实现,并且代码非常简单。而递归实际就是函数反复的调用本身,在栈上反复压栈。所以我们可以用栈来模拟实现递归。
创新互联是一家集网站建设,双河企业网站建设,双河品牌网站建设,网站定制,双河网站建设报价,网络营销,网络优化,双河网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。1.前序遍历
(1)栈是后进先出的特点,所以无条件的把栈的根节点入栈,在把栈顶元素输出之后依次把右孩子,左孩子压入栈中。
代码如下:
void _PrevOrder(Node * root) { stacks; if (root == NULL) { return; } s.push(root);//将第一个元素入栈 while (!s.empty())//当栈不为空时 { root = s.top(); cout << root->_data << "->";//打印节点 s.pop(); //栈的特点,后进先出,所以,先压右子树 if (root->_right)//遍历右子树 { s.push(root->_right); } if (root->_left)//遍历左子树 { s.push(root->_left); } } }
2.中序遍历
(1)一直入栈,一直到二叉树的最左边最下边的节点。
(2)按照中序遍历的特点:左子树->根节点->右子树,输出栈顶的元素,并且弹出,必须保留该节点的指针。
(3)此时,该判断此节点的右子树:
a.右子树为NULL,返回到栈顶;
b.右子树不为NULL,把该节点当根节点,重复(1)(2)(3)......
代码如下:
void _InOrder(Node * root) { if (root == NULL) { return; } Node * cur = root; stacks; while (cur || !s.empty()) { while (cur)//当没有左子树时,停止入栈 { s.push(cur); cur = cur->_left; } Node * top = s.top();//保留栈顶指针,判断是否有右子树 cout << top->_data << "->"; s.pop(); if (top->_right == NULL)//没有右子树时,不需要压栈 { cur = NULL; } else//当存在右子树时,把右子树的根节点压入栈中,循环去判断该节点的左子树是否存在 { cur = top->_right; } } }
3.后序遍历
(1)一直入栈,一直到二叉树的最左边最下边的节点。
(2)按照后序遍历的特点:左子树->右子树->根节点,输出栈顶的元素,并且弹出,必须保留该节点的指针。
(3)此时,该判断此节点的右子树,如果存在右子树,把该节点当作根节点,重复(1)(2)(3)
代码如下:
void _PostOrder(Node * root) { if (root == NULL) { return; } Node * cur = root; Node * prev = NULL; stacks; while (cur || !s.empty()) { while (cur)//当没有左子树时,停止入栈 { s.push(cur); cur = cur->_left; } Node * top = s.top();//保留栈顶指针,判断它的右子树是否为空或者已经出栈 if (top->_right == NULL || top->_right == prev) { cout << top->_data << "->"; s.pop(); prev = top;//保留出栈元素的指针 cur = NULL; } else//当存在右子树时,把右子树的根节点压入栈中,循环去判断该节点的左子树是否存在 { cur = top->_right; } } }
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
标题名称:二叉树遍历的非递归实现-创新互联
本文地址:http://myzitong.com/article/dcppie.html