代码实现二叉树的后续遍历。要求:1、不可以用递归;2、不可以用栈;3、自定义树节点的结构;4、给出测试用例;5、语言不限;
注意:你的方法的输入为根节点
参考方法:定义树结构体如下:
struct TreeNode {
int value;
TreeNode* parent;
TreeNode* leftChild;
TreeNode* rightChild;
}
第一行一个正整数n(1<=n<=100),表示二叉树有n个结点。
接下来n行,第i行两个整数li,ri (0<=li,ri<=n) ,分别表示第i个结点的左儿子和右儿子,为0代表空。
保证根为1,保证输入为合法二叉树。
输出一行。输出n个数,代表后序遍历的结点的顺序,相邻两个数之间用一个空格相隔。
5 3 2 0 5 0 4 0 0 0 0
4 3 5 2 1
//我的TreeNode中保存了父节点、左子节点、右子节点的输入序号,默认为0为空节点 //构造一个n+1大小的TreeNode数组,下标0为空节点,其它下标对应节点的输入序号即value //用一个下标指示根节点,按后续遍历顺序找到最先遍历的节点,并将指示下标赋值为该节点 //找到当前树中最先遍历的节点,其左右子节点都为空,输出该节点的下标即value,并将该节点从树中删除 //删除节点通过将其父节点的指向赋值为0,当父节点有左子节点时都会先删除左子节点 #include<iostream> #include<vector> using namespace std; struct TreeNode { //int value = 0;//输入的序号 int parent = 0; int left = 0; int right = 0; }; int main() { int n; cin >> n; vector<TreeNode>arr(n+1); for (int i = 1; i <= n; i++) cin >> arr[i].left >> arr[i].right; for (int i = 1; i <= n; i++) {//节点的输入序号即节点的值 int lef = arr[i].left; int rig = arr[i].right; arr[lef].parent = i; arr[rig].parent = i; } //后续遍历 int index = 1; int count = 0; while (count < n) { int lef = arr[index].left; if (lef) { index = lef; continue; } int rig = arr[index].right; if (rig) { index = rig; continue; } //左右节点为空 cout << index << " "; index = arr[index].parent; if (arr[index].left) arr[index].left = 0; else arr[index].right = 0; count++; } system("pause"); return 0; }
#include <iostream> #include <locale> #include <vector> using namespace std; struct TreeNode { int value; TreeNode* parent; TreeNode* leftChild; TreeNode* rightChild; TreeNode(){ parent =nullptr; leftChild=nullptr; rightChild=nullptr; } }; int main() { int n; cin>>n; vector<TreeNode> vv(n); for(int i =1 ; i<= n ;i++){ vv[i-1].value = i; int l,r; cin>>l>>r; if(l){ vv[i-1].leftChild = &(vv[l-1]); vv[l-1].parent = &(vv[i-1]); } if(r){ vv[i-1].rightChild = &(vv[r-1]); vv[r-1].parent = &(vv[i-1]); } } // 数据读取完毕 TreeNode* root = &(vv[0]);//根节点 TreeNode* cur = root; vector<int> ret; while(cur){ ret.push_back(cur->value); if(cur->rightChild){ cur = cur->rightChild; } else if(cur ->leftChild){ cur = cur->leftChild; } else{ TreeNode* par = cur->parent; while(par){ if(par->rightChild == cur && par->leftChild!=nullptr){ cur = par->leftChild; break; } else{ cur = cur->parent; par = cur->parent; } } if(par == nullptr){ cur = nullptr; } } } for(int i =ret.size()-1; i > 0; i--){ cout<<ret[i]<< " "; } cout<<ret[0]<<endl; } // 64 位输出请用 printf("%lld")