【C/C++學院】0906-遞歸轉棧/二叉樹實現
遞歸轉棧
用棧實現遞歸.cpp
#include
#include
using namespace std;
int printN(int n)
{
if (n>0)
{
cout << n;
return printN(n - 1);
}
}
void printNS_shunxu(int n)
{
stack 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 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 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"<雙層遞歸轉棧.cpp
#include
#include
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 mystack;
int f1, f2, f3;
f1 = f2 = 1;
int i = 2;
ABC:if (i棧模擬遞歸函數調用.cpp
#include
#include
//遞歸，有順序，逆序，棧吃一個吐一個，順序，一次吃完再吐，逆序
//遞歸，數據保留中間結果，函數指針保留操作
//漢諾塔，斐波那契數列 遞歸計算表達式 ，棧，（熊飛，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 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();
}</mystruct></mystruct></mystruct></stack></string></iostream>
