- #include"BinaryTree.h"
- #include<stack>
- using std::stack;
- template<class T>
- void dlrsearch(BinaryTree<T> tree,int r,vector<T> &vectemp)
- {
- if(!tree.isleave(r))
- {
- if(r<=tree.node()) vectemp.push_back(tree.get(r));
- if(tree.leftchild(r)<=tree.node()) dlrsearch(tree,tree.leftchild(r),vectemp);
- if(tree.rightchild(r)<=tree.node()) dlrsearch(tree,tree.rightchild(r),vectemp);
- }
- else
- if (r<=tree.node())vectemp.push_back(tree.get(r));
- }
- template<class T>
- void ldrsearch(BinaryTree<T> tree,int r,vector<T> &vectemp)
- {
- if(!tree.isleave(r))
- {
- if(tree.leftchild(r)<=tree.node()) ldrsearch(tree,tree.leftchild(r),vectemp);
- if(r<=tree.node()) vectemp.push_back(tree.get(r));
- if(tree.rightchild(r)<=tree.node()) ldrsearch(tree,tree.rightchild(r),vectemp);
- }
- else
- if(r<=tree.node()) vectemp.push_back(tree.get(r));
- }
- template<class T>
- void lrdsearch(BinaryTree<T> tree,int r,vector<T> &vectemp)
- {
- if(!tree.isleave(r))
- {
- if(tree.leftbrother(r)<=tree.node()) lrdsearch(tree,tree.leftchild(r),vectemp);
- if(tree.rightchild(r)<=tree.node()) lrdsearch(tree,tree.rightchild(r),vectemp);
- if(r<=tree.node()) vectemp.push_back(tree.get(r));
- }
- else
- if(r<=tree.node()) vectemp.push_back(tree.get(r));
- }
- template<class T>
- vector<T> dlrsearch_norecursion(BinaryTree<T> tree,int r)
- {
- vector<T> vectemp;
- stack<int> sta;
- sta.push(r);
- while(!sta.empty())
- {
- int cur=sta.top();
- sta.pop();
- while(!tree.isleave(cur))
- {
- vectemp.push_back(tree.get(cur));
- sta.push(tree.rightchild(cur));
- cur=tree.leftchild(cur);
- }
- vectemp.push_back(tree.get(cur));
- }
- return vectemp;
- }
- template<class T>
- vector<T> ldrsearch_norecursion(BinaryTree<T> tree,int r)
- {
- vector<T> vectemp;
- stack<int>sta;
- sta.push(r);
- while(!sta.empty())
- {
- int cur=sta.top();
- sta.pop();
- while(!tree.isleave(cur))
- {
- sta.push(cur);
- cur=tree.leftchild(cur);
- }
- vectemp.push_back(tree.get(cur));
- while(!sta.empty())
- {
- int cut=sta.top();
- sta.pop();
- vectemp.push_back(tree.get(cut));
- if(tree.rightchild(cut)<=tree.node())
- {
- sta.push(tree.rightchild(cut));
- break;
- }
- }
- }
- return vectemp;
- }
- template<class T>
- vector<T> lrdsearch_norecursion(BinaryTree<T> tree,int r)
- {
- bool *flg=new bool[tree.node()];
- for(int i=0;i<tree.node();i++)
- flg[i]=true;
- vector<T> vectemp;
- stack<int> sta;
- sta.push(r);
- while(!sta.empty())
- {
- int cur=sta.top();
- sta.pop();
- while(!tree.isleave(cur))
- {
- if(flg[tree.leftchild(cur)-1]&&flg[tree.rightchild(cur)-1])
- {
- sta.push(cur);
- sta.push(tree.rightchild(cur));
- cur=tree.leftchild(cur);
- }
- else
- break;
- }
- vectemp.push_back(tree.get(cur));
- flg[cur-1]=false;
- }
- return vectemp;
- }
- //该片段来自于http://www.codesnippet.cn/detail/170520133431.html
来源: http://www.codesnippet.cn/detail/170520133431.html