14

#include<iostream> #include <string> #include <stack> using namespace std; struct MyStruct { int Nodedata; MyStruct *pLeft; MyStruct *pRight; }BTree,*pBTree; //中序，前序，后序，递归遍历，非递归遍历（栈） //查找，修改，插入，排序,删除(太难) /*递归：在输出doc界面上，输出二叉树的形状*/ void show(MyStruct *proot ,int n) { if (proot==nullptr) { return; } else { show(proot->pRight, n + 1); for (int i = 0; i < n;i++) { cout << " "; } cout << proot->Nodedata << endl; show(proot->pLeft, n + 1); } } /*递归：实现二叉树中序遍历*/ void zhong(MyStruct *proot) { if (proot!=nullptr) { if (proot->pLeft!=nullptr) { zhong(proot->pLeft); } cout << " " << proot->Nodedata ; if (proot->pRight!= nullptr) { zhong(proot->pRight); } } } /*递归：实现二叉树先序遍历*/ void xian(MyStruct *proot) { if (proot!=nullptr) { cout << " " << proot->Nodedata ; if (proot->pLeft!=nullptr) { xian(proot->pLeft); } if (proot->pRight!= nullptr) { xian(proot->pRight); } } } /*递归：实现二叉树后序遍历*/ void hou(MyStruct *proot) { if (proot!=nullptr) { if (proot->pLeft!=nullptr) { hou(proot->pLeft); } if (proot->pRight!= nullptr) { hou(proot->pRight); } cout << " " << proot->Nodedata ; } } /*利用数组实现二叉树的中序遍历*/ void stackzhong(MyStruct *proot) { 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) { 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; } } } /*递归：获取叶子节点数*/ 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;//入队 } } } /*递归：输入某个数，获取到他的父节点*/ 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); } /*利用数组模拟栈，查找二叉树中的最大值*/ 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]; if (max< pcurr->Nodedata) { max = pcurr->Nodedata; } pcurr = pcurr->pRight; } } return max; } /*递归：插入数据*/ MyStruct * insertnode(MyStruct *proot,int num) { if (proot==nullptr) { MyStruct *pnew = new MyStruct; pnew->Nodedata = num; pnew->pLeft = nullptr ; pnew->pRight = nullptr ; proot = pnew; } else if ( num <= proot->Nodedata) { proot->pLeft = insertnode(proot->pLeft, num); } else { proot->pRight = insertnode(proot->pRight, num); } return proot; } void main01() { MyStruct *pRoot;//根 MyStruct s1 = { 0 , nullptr , nullptr} ; MyStruct s2 = { 0 , nullptr , nullptr} ; MyStruct s3 = { 0 , nullptr , nullptr} ; MyStruct s4 = { 0 , nullptr , nullptr} ; MyStruct s5 = { 0 , nullptr , nullptr} ; MyStruct s6 = { 0 , nullptr , nullptr} ; MyStruct s7 = { 0 , nullptr , nullptr} ; MyStruct s8 = { 0 , nullptr , nullptr} ; MyStruct s9 = { 0 , nullptr , nullptr} ; 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; s9.Nodedata = 9; s1.pLeft = &s2; s1.pRight = &s3; s2.pLeft = &s4; s2.pRight = &s5; s3.pLeft = &s6; s3.pRight = &s7; s4.pLeft = &s8 ; s4.pRight = nullptr ; s8.pRight = &s9 ; s8.pLeft = nullptr ; show( pRoot , 1) ; cout<<endl ; zhong(pRoot) ; cout<<endl ; xian(pRoot) ; cout<<endl ; hou(pRoot) ; cout<< endl << getyenum( pRoot ); cout<< endl << getheight( pRoot ) ; ceng( pRoot ) ; cin.get(); } void mainA() { MyStruct *pRoot;//根 MyStruct sarray[100]; /*数组的每个元素都是二叉树上的一个节点*/ pRoot = sarray; for (int i = 1; i <= 100;i++) { sarray[i].Nodedata = i; } /*给数组的每个元素的前驱和后继赋值， 也就是让数组形成逻辑上的二叉树。 究竟有多少个节点需要赋值呢？ 实际上只有最下面的一层不需要赋值， 倒数第二层需要赋值（有些不要） 所以在循环的内部还要加限定条件。 所以这里的大循环应该是倒数第二层到 第一层之间的节点总个数（设为x）， 则最后一层的节点个数为（x+1）， 条件为：x+x+1<=100。这里取相近的50. 反正在循环的内部还会限制条件*/ for (int i = 0; i <= 50;i++) { /*正如上面所说的，由于设置的总节点个数 不一定能设整个二叉树成为满二叉树，所以 在倒数第二层这里最右边有些节点是不会挂上 前驱和后继的。 还有可能只是挂上了前驱没后继， 所以需要加限制条件来赋值。 条件要求：假设要挂前驱和后继的节点为x， 则其挂载的前驱为：2x+1（这里根据i从0开始推倒出来的）； 后继为：2x+2； 可得： 只要满足2x+1<=99 即可挂上前驱; 只要满足2x+2<=99 即可挂上后继*/ 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(); } void main() { MyStruct *pRoot=nullptr;//根 for (int i = 0; i < 10; i+=2) { pRoot = insertnode(pRoot, i); } for (int i = 5; i >=0; i-=2) { pRoot = insertnode(pRoot, i); } show(pRoot, 1); cin.get(); }