大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
在二叉树的应用中,很多使用二叉树的操作都是通过遍历来进行节点的修改。
成都创新互联公司专注于南芬网站建设服务及定制,我们拥有丰富的企业做网站经验。 热诚为您提供南芬营销型网站建设,南芬网站制作、南芬网页设计、南芬网站官网定制、微信小程序开发服务,打造南芬网络公司原创品牌,更为您提供南芬网站排名全网营销落地服务。
所以对于遍历而言是学习二叉树的要点,今天就来总结一下。
假设二叉树的结构为:
templatestruct BinaryTreeNode { BinaryTreeNode(const T& x) :_data(x) ,_left(NULL) ,_right(NULL) {} T _data; BinaryTreeNode * _left; BinaryTreeNode * _right; };
前序遍历:
void PrevOrder() { _PrevOrder(_root); cout<* root) { if (root==NULL) return; cout< _data<<" "; _PrevOrder(root->_left); _PrevOrder(root->_right); } void PrevOrder_Non_R() { stack *> s; if (_root) s.push(_root); while(!s.empty()) { BinaryTreeNode * top = s.top(); cout< _data<<" "; s.pop(); if (top->_right) s.push(top->_right); if (top->_left) s.push(top->_left); } cout< 2.中序遍历:
void InOrder() { _InOrder(_root); cout<* root) { if (root == NULL) return; _InOrder(root->_left); cout< _data<<" "; _InOrder(root->_right); } void InOrder_Non_R() { stack *> s; BinaryTreeNode * cur = _root; while (cur || !s.empty()) { // 1.压左节点 while (cur) { s.push(cur); cur = cur->_left; } // 取栈顶节点数据访问 // 前序遍历top节点的右树 if (!s.empty()) { BinaryTreeNode * top = s.top(); s.pop(); cout< _data<<" "; cur = top->_right; } } cout< 3.后序遍历:
void PostOrder() { _PostOrder(_root); cout<* root) { if (root == NULL) return; _PostOrder(root->_left); _PostOrder(root->_right); cout< _data<<" "; } void PostOrder_Non_R() { stack *> s; BinaryTreeNode * cur = _root; BinaryTreeNode * prevVisited = NULL; while (cur || !s.empty()) { // 1.压左节点 while (cur) { s.push(cur); cur = cur->_left; } BinaryTreeNode * top = s.top(); if (top->_right == NULL || top->_right == prevVisited) { cout< _data<<" "; s.pop(); prevVisited = top; } else { cur = top->_right; } } cout< 4.层次遍历
void LevelOrder() { queue* > q; if (_root) q.push(_root); while(!q.empty()) { BinaryTreeNode * front = q.front(); cout< _data<<" "; q.pop(); if (front->_left) q.push(front->_left); if (front->_right) q.push(front->_right); } cout< 以上
网页名称:树:二叉树的前序/中序/后序/层次递归
网页URL:http://dzwzjz.com/article/jjcpho.html