非递归实现遍历二叉树-创新互联

非递归实现二叉树主要利用queue和stack的特点,对于层次遍历二叉树主要运用queue队头出,队尾插入,先进先出的特点,先将根插入队尾,然后输出队头的元素,同时将队头的左子树和右子树元素插入队尾,依次输出输出队头的元素,同时将队头的左子树和右子树元素插入队尾,直到队列为空。

创新互联是一家专注于网站设计制作、成都网站建设与策划设计,城固网站建设哪家好?创新互联做网站,专注于网站建设十年,网设计领域的专业建站公司;建站业务涵盖:城固等地区。城固做网站价格咨询:18980820575

void levelorder()

{

queue<BinaryTreeNode<T> *>s;

if (_root == NULL)

return;

s.push(_root);

while (!s.empty())

{

                BinaryTreeNode<T> *front=s.front();

cout << front->_data << " ";

if (front->_left)

s.push(front->_left);

if (front->_right)

s.push(front->_right);

s.pop();

}

}

非递归实现二叉树前序遍历主要运用stack的先进后出的特点,先把根压入栈里,同时先把左子树的左子树元素以此压入栈底,最后左子树的最后一个元素压入栈底之后,再将栈底元素弹出栈,再判断栈底最后一个元素的右子树,利用以上的方法。代码如下:

void prevorder()

{

stack<BinaryTreeNode<T> *>s;

if (_root == NULL)

return;

s.push(_root);

while (!s.empty())

{

BinaryTreeNode<T> *cur = s.top();

cout << cur->_data << " ";

s.pop();

if (cur->_right)

s.push(cur->_right);

if (cur->_left)

s.push(cur->_left);

}

}

非递归实现二叉树中序遍历主要运用stack的先进后出的特点,先把根压入栈里,同时先把左子树的左子树元素以此压入栈底,最后左子树的最后一个元素压入栈底之后,判断栈底最后一个元素的右子树,利用以上的方法。代码如下:

void inorder()

{

stack<BinaryTreeNode<T> *>s;

if (_root == NULL)

return;

BinaryTreeNode<T> *cur = _root;

while (cur||!s.empty())

{

while (cur)

{

s.push(cur);

cur = cur->_left;

}

cout << s.top()->_data << " ";

cur = s.top()->_right;

s.pop();

}

}

非递归实现二叉树后序遍历主要运用stack的先进后出的特点,在利用前序和后序的共同特点

void postorder()

{

stack<BinaryTreeNode<T> *>s;

if (_root == NULL)

return;

BinaryTreeNode<T> *cur = _root;

BinaryTreeNode<T> *prev = NULL;

s.push(cur);

while (cur || !s.empty())

{

while (cur->_left&&cur->_left!=prev)

{

s.push(cur->_left);

cur = cur->_left;

}

if (s.top()->_right&&s.top()->_right != prev)

{

cur = s.top()->_right;

s.push(cur);

}

else

{

cout << s.top()->_data << " ";

prev = s.top();

s.pop();

cur = s.top();

cur->_left =NULL;

}

}

}

创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。

网站名称:非递归实现遍历二叉树-创新互联
文章地址:https://www.cdcxhl.com/article36/jgspg.html

成都网站建设公司_创新互联,为您提供小程序开发营销型网站建设移动网站建设做网站网站设计公司企业建站

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联

成都seo排名网站优化