#include <iostream> using namespace std; struct Bitree { Bitree* left; Bitree* right; int val;//节点的值 }; Bitree* creatnode(int data) { //创建二叉树节点 Bitree* node = (Bitree*)malloc(sizeof(Bitree)); node->val = data; node->left = NULL; node->right = NULL; return node; } Bitree* paixuCreat(Bitree* root, int value,int* parent) //用parent记录父亲节点的值 { if (root == NULL) { //当前节点为空 return creatnode(value); } if (value < root->val) { *parent = root->val; root->left = paixuCreat(root->left, value, parent); } else { *parent = root->val; root->right = paixuCreat(root->right, value, parent); } return root; } int main() { Bitree* root = NULL; int N, value; cin >> N; int* parentNodes = (int*)malloc(N * sizeof(int));//创建数组以保存父亲节点的值 parentNodes[0] = -1;//第一个值默认为-1 for (int i = 0; i < N; i++) { cin >> value; int parent = -1; root = paixuCreat(root, value, &parent); parentNodes[i] = parent;//记录父亲节点 } for (int i = 0; i < N; i++) { cout << parentNodes[i] << endl; //输出父亲节点 } } // 64 位输出请用 printf("%lld")
创建排序二叉树的同时用parent变量记录其父节点然后保存在数组里,最后再输出