递归转栈
用栈实现递归.cpp
#include<stack>
#include <iostream>
using namespace std;
int printN(int n)
{
if (n>0)
{
cout << n;
return printN(n - 1);
}
}
void printNS_shunxu(int n)
{
stack<int> mystack;
AAA:
if (n > 0)
{
mystack.push(n);
while (!mystack.empty())
{
cout << mystack.top();
mystack.pop();
}
n -= 1;
goto AAA;
}
}
void printNS_nixu(int n)
{
stack<int> mystack;
AAA:
if (n > 0)
{
mystack.push(n);
n -= 1;
goto AAA;
}
while (!mystack.empty())
{
cout << mystack.top();
mystack.pop();
}
}
int get100(int i)
{
if (!i)
{
return 0;
}
else
{
return get100(i - 1) + i;
}
}
int getN(int i)
{
stack<int> mystack;
int res = 0;
AA: if (i)
{
mystack.push(i);
i--;
goto AA;
}
while (!mystack.empty())
{
res += mystack.top();
mystack.pop();
}
return res;
}
void to2(int num)
{
if (num)
{
cout << num % 2;
to2(num / 2);
}
}
void mainA ()
{
//cout << get100(100) << endl;
printNS_nixu(9);
printNS_shunxu(9);
cout<<"\n"<<getN(100)<<"\n";
to2(10);
cin.get();
}
双层递归转栈.cpp
#include<iostream>
#include <stack>
using namespace std;
int getF(int n)
{
if (n==1 ||n==2)
{
return 1;
}
else
{
return getF(n - 1) + getF(n - 2);
}
}
int GetFF(int n)
{
int *p = new int[n];
p[0] = p[1] = 1;
for (int i = 2; i < n;i++)
{
p[i] = p[i - 1] + p[i - 2];
}
return p[n - 1];
}
int GetFFF(int n)
{
stack<int> mystack;
int f1, f2, f3;
f1 = f2 = 1;
int i = 2;
ABC:if (i<n)
{
mystack.push(f1);
mystack.push(f2);
f3 = 0;
while (!mystack.empty())
{
f3+= mystack.top();
mystack.pop();
}
//f3 = f2 + f1;
f1 = f2;//轮替
f2 = f3;
i++;
goto ABC;
}
return f3;
}
int GetFFFF(int n)
{
int f1, f2, f3;
f1 = f2 = 1;
for (int i = 2; i < n; i++)
{
f3 = f2 + f1;
f1 = f2;//轮替
f2 = f3;
}
return f3;
}
void mainFG()
{
cout << getF(10) << endl;
cout << GetFF(10) << endl;
cout << GetFFF(10) << endl;
cin.get();
}
栈模拟递归函数调用.cpp
#include<iostream>
#include <stack>
//递归，有顺序，逆序，栈吃一个吐一个，顺序，一次吃完再吐，逆序
//递归，数据保留中间结果，函数指针保留操作
//汉诺塔，斐波那契数列 递归计算表达式 ，栈，（熊飞，3人做一题）
//谭胜，汉诺塔，李桂龙，斐波那契 ，柳益民
using namespace std;
struct datas
{
int n;
void(*p)(int);
};
void printN(int n)
{
if (n > 0)
{
cout << n;
return printN(n - 1);
}
}
void print(int n)
{
cout << n;
}
//1+100
void printall(int n)
{
stack<datas> mystack;
AAA:
if (n > 0)
{
datas s1;
s1.n = n;
s1.p = print;
mystack.push(s1);
while (!mystack.empty())
{
datas stemp = mystack.top();
stemp.p(stemp.n);
mystack.pop();
}
n -= 1;
goto AAA;
}
}
void main()
{
printall(10);
cin.get();
}
二叉树实现
#include<iostream>
#include <string>
#include <stack>
using namespace std;
struct MyStruct
{
int Nodedata=0;
MyStruct *pLeft=nullptr;
MyStruct *pRight = nullptr;
}BTree,*pBTree;
//中序，前序，后序，递归遍历，非递归遍历
//查找，修改， 删除，插入，排序
MyStruct * insertnode(MyStruct *proot,int num)
{
if (proot==nullptr)
{
MyStruct *pnew = new MyStruct;
pnew->Nodedata = num;
proot = pnew;
}
else if ( num <= proot->Nodedata)
{
proot->pLeft = insertnode(proot->pLeft, num);
}
else
{
proot->pRight = insertnode(proot->pRight, num);
}
return proot;
}
int findmax(MyStruct *proot)
{
int max = -99999;
MyStruct * pcurr = proot;//记录根节点
MyStruct * mystack[100];//指针数据
int top = 0;
while (top != 0 || pcurr != nullptr)
{
while (pcurr != nullptr)
{
mystack[top++] = pcurr;
pcurr = pcurr->pLeft;
}
if (top > 0)
{
top--;
pcurr = mystack[top];
///cout << " " << pcurr->Nodedata << endl;
if (max< pcurr->Nodedata)
{
max = pcurr->Nodedata;
}
pcurr = pcurr->pRight;
}
}
return max;
}
void zhong(MyStruct *proot)
{
if (proot!=nullptr)
{
if (proot->pLeft!=nullptr)
{
zhong(proot->pLeft);
}
cout << " " << proot->Nodedata << endl;
if (proot->pRight!= nullptr)
{
zhong(proot->pRight);
}
}
}
void stackzhong(MyStruct *proot)
{
//stack<MyStruct> mystack;
MyStruct * pcurr = proot;//记录根节点
MyStruct * mystack[100];//指针数据
int top = 0;
while ( top!=0 || pcurr !=nullptr)
{
while (pcurr != nullptr)
{
mystack[top++] = pcurr;
pcurr = pcurr->pLeft;
}
if (top>0)
{
top--;
pcurr = mystack[top];
cout << " " << pcurr->Nodedata << endl;
pcurr = pcurr->pRight;
}
}
}
void stackzhongA(MyStruct *proot)
{
//stack<MyStruct> mystack;
MyStruct * pcurr = proot;//记录根节点
stack<MyStruct *> mystack;
while (!mystack.empty() || pcurr != nullptr)
{
while (pcurr != nullptr)
{
mystack.push(pcurr);
pcurr = pcurr->pLeft;
}
if (!mystack.empty())
{
pcurr = mystack.top();
cout << " " << pcurr->Nodedata << endl;
mystack.pop();
pcurr = pcurr->pRight;
}
}
}
void show(MyStruct *proot ,int n)
{
if (proot==nullptr)
{
return;
}
else
{
show(proot->pLeft, n + 1);
for (int i = 0; i < n;i++)
{
cout << " ";
}
cout << proot->Nodedata << endl;
show(proot->pRight, n + 1);
}
}
int getyenum(MyStruct *proot)//叶子节点
{
int left = 0;
int right = 0;
if (proot==nullptr)
{
return 0;
}
if (proot->pLeft==nullptr && proot->pRight==nullptr)
{
return 1;
}
left = getyenum(proot->pLeft);
right = getyenum(proot->pRight);
return left + right;
}
int getheight(MyStruct *proot)
{
int height = 0;
int left = 0;
int right = 0;
if (proot == nullptr)
{
return 0;
}
left = getheight(proot->pLeft);
right = getheight(proot->pRight);
height = left > right ? left : right;
return height + 1;
}
void ceng(MyStruct *proot)
{
if (proot ==nullptr)
{
return;
}
MyStruct * myq[100];
int tou = 0;
int wei = 0;
MyStruct * pcurr = nullptr;
myq[wei++] = proot;//存入队列第一个节点，入队
while (tou !=wei)
{
pcurr = myq[tou];
tou++;//出队
cout << pcurr->Nodedata << endl;
if (pcurr->pLeft!=nullptr)
{
myq[wei++] = pcurr->pLeft;//入队
}
if (pcurr->pRight != nullptr)
{
myq[wei++] = pcurr->pRight;//入队
}
}
}
void mainA()
{
MyStruct *pRoot;//根
MyStruct sarray[100];
pRoot = sarray;
//0 1 2 3 4 --99
//
for (int i = 1; i <= 100;i++)
{
sarray[i].Nodedata = i;
}
//2 * i + 2<<99
for (int i = 0; i <= 50;i++)
{
if (i<=(99-1)/2)
{
sarray[i].pLeft = &sarray[2 * i + 1];
}
if (i<=(99-2)/2)
{
sarray[i].pRight = &sarray[2 * i + 2];
}
}
show(pRoot, 1);
cin.get();
}
int getba(MyStruct *pRoot,int num)
{
if (pRoot==nullptr)
{
return 0;
}
if (pRoot->pLeft!=nullptr && pRoot->pLeft->Nodedata==num)
{
return pRoot->Nodedata;
}
if (pRoot->pRight != nullptr && pRoot->pRight->Nodedata == num)
{
return pRoot->Nodedata;
}
getba(pRoot->pLeft, num);
getba(pRoot->pRight, num);
}
int getleft(MyStruct *pRoot, int num)
{
if (pRoot == nullptr)
{
return 0;
}
if (pRoot->pRight && pRoot->pRight->Nodedata == num)
{
if (pRoot->pLeft)
{
return pRoot->pLeft->Nodedata;
}
}
getleft(pRoot->pLeft, num);
getleft(pRoot->pRight, num);
}
void main213213()
{
MyStruct *pRoot;//根
MyStruct s1;
MyStruct s2;
MyStruct s3;
MyStruct s4;
MyStruct s5;
MyStruct s6;
MyStruct s7;
MyStruct s8;
pRoot = &s1;
s1.Nodedata = 1;
s2.Nodedata = 2;
s3.Nodedata = 3;
s4.Nodedata = 4;
s5.Nodedata = 5;
s6.Nodedata = 16;
s7.Nodedata = 7;
s8.Nodedata = 8;
s1.pLeft = &s2;
s1.pRight = &s3;
s2.pLeft = &s4;
s2.pRight = &s5;
s3.pLeft = &s6;
s3.pRight = &s7;
cout << findmax(pRoot) << endl;
cin.get();
}
void mainasds()
{
MyStruct *pRoot;//根
MyStruct s1;
MyStruct s2;
MyStruct s3;
MyStruct s4;
MyStruct s5;
MyStruct s6;
MyStruct s7;
MyStruct s8;
pRoot = &s1;
s1.Nodedata = 1;
s2.Nodedata = 2;
s3.Nodedata = 3;
s4.Nodedata = 4;
s5.Nodedata = 5;
s6.Nodedata = 6;
s7.Nodedata = 7;
s8.Nodedata = 8;
s1.pLeft = &s2;
s1.pRight = &s3;
s2.pLeft = &s4;
s2.pRight = &s5;
s3.pLeft = &s6;
s3.pRight = &s7;
//s4.pLeft = &s8;
ceng(pRoot);
cout << "\n\n\n\n\n\n\n";
cout << getyenum(pRoot)<<"\n\n\n";
cout << getheight(pRoot) << "\n\n\n";
//show(pRoot, 1);
zhong(pRoot);
cout << "\n\n\n\n";
stackzhong(pRoot);
cout << "\n\n\n\n";
stackzhongA(pRoot);
cin.get();
}
void main()
{
MyStruct *pRoot=nullptr;//根
for (int i = 6; i < 10; i++)
{
pRoot = insertnode(pRoot, i);
}
for (int i = 5; i >=0; i--)
{
pRoot = insertnode(pRoot, i);
}
show(pRoot, 1);
cin.get();
}
