二叉树前中后/层次遍历的递归与非递归形式(c++)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了二叉树前中后/层次遍历的递归与非递归形式(c++),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3310字,纯文字阅读大概需要5分钟。
内容图文
/* 二叉树前中后/层次遍历的递归与非递归形式 */ //*************** void preOrder1(BinaryTreeNode* pRoot) { if(pRoot==NULL) return; cout<<pRoot->value; if(pRoot->left!=NULL) preOrder1(pRoot->left); if(pRoot->right!=NULL) preOrder1(pRoot->right); } void preOrder2(BinaryTreeNode* pRoot) { stack<BinaryTreeNode*> s; BinaryTreeNode *p=pRoot; if(pRoot==NULL) return; while(p!=NULL||!s.empty()) { while(p!=NULL) { cout<<p->value<<" "; s.push(p); p=p->left; } if(!s.empty()) { p=s.top(); s.pop(); p=p->right; } } } void preOrder2(BinaryTreeNode* pRoot){ if(pRoot==NULL) return; stack<BinaryTreeNode*> s; s.push(root); BinaryTreeNode* p; while(!s.empty()){ p = s.top(); cout<<p->data;//遍历根结点 s.pop(); if(p>right){ s.push(p->right); //先将右子树压栈 } if(p->left){ s.push(p->left); //再将左子树压栈 } } } //***************** //中序遍历 void inOrder1(BinaryTreeNode* pRoot) { if(pRoot==NULL) return; if(pRoot->left!=NULL) inOrder1(pRoot->left); cout<<pRoot->value; if(pRoot->right!=NULL) inOrder1(pRoot->right); } void inOrder2(BinaryTreeNode* pRoot) { stack<BinaryTreeNode*> s; BinaryTreeNode *p=pRoot; if(pRoot==NULL) return; while(p!=NULL||!s.empty()) { while(p!=NULL) { s.push(p); p=p->left; } if(!s.empty()) { p=s.top(); cout<<p->value<<" "; s.pop(); p=p->right; } } } //***************** //后序遍历 void postOrder1(BinaryTreeNode* pRoot) { if(pRoot==NULL) return; postOrder1(pRoot->left); postOrder1(pRoot->right); cout<<pRoot->value<<" "; } void postOrder2(BinaryTreeNode* pRoot) { stack<BinaryTreeNode*> s; BinaryTreeNode *cur; BinaryTreeNode *pre=NULL;//记录上一个输出的节点 s.push(pRoot);//根结点入栈 while(!s.empty()) { cur=s.top(); if((cur->left==NULL&&cur->right==NULL)||(pre!=NULL&&(pre==cur->left||pre==cur->right))) { //左孩子和右孩子同时为空,或者当前结点的左孩子或右孩子已经遍历过了 cout<<cur->value<<" "; s.pop(); pre=cur; } else { if(cur->right!=NULL) s.push(cur->right); if(cur->left!=NULL) s.push(cur->left); } } } //***************** //层次遍历,使用队列 void PrintFromTopToBottom(BinaryTreeNode* pRoot) { if(pRoot == NULL) return; deque<BinaryTreeNode *> dequeTreeNode; dequeTreeNode.push_back(pRoot); while(dequeTreeNode.size()) { BinaryTreeNode *pNode = dequeTreeNode.front(); dequeTreeNode.pop_front(); cout<<pNode->m_nValue<<" "; if(pNode->m_pLeft) dequeTreeNode.push_back(pNode->m_pLeft); if(pNode->m_pRight) dequeTreeNode.push_back(pNode->m_pRight); } } //深度优先遍历~先序遍历 void dfs(BinaryTreeNode* root){ stack<BinaryTreeNode* *> nodeStack; nodeStack.push(root); Node *node; while(!nodeStack.empty()){ node = nodeStack.top(); cout<<node->data;//遍历根结点 nodeStack.pop(); if(node->rchild){ nodeStack.push(node->rchild); //先将右子树压栈 } if(node->lchild){ nodeStack.push(node->lchild); //再将左子树压栈 } } } //广度优先遍历~层次遍历 void bfs(BinaryTreeNode* root){ queue<BinaryTreeNode* *> nodeQueue; nodeQueue.push(root); Node *node; while(!nodeQueue.empty()){ node = nodeQueue.front(); nodeQueue.pop(); cout<<node->data;//遍历根结点 if(node->lchild){ nodeQueue.push(node->lchild); //先将左子树入队 } if(node->rchild){ nodeQueue.push(node->rchild); //再将右子树入队 } } }
原文:https://www.cnblogs.com/zhang-qc/p/9344824.html
内容总结
以上是互联网集市为您收集整理的二叉树前中后/层次遍历的递归与非递归形式(c++)全部内容,希望文章能够帮你解决二叉树前中后/层次遍历的递归与非递归形式(c++)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。