法一:仅使用父指针par
#include<iostream>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
};
int main(){
int n;
cin>>n;
int x;
cin>>x;
TreeNode* root = new TreeNode(x);
cout<<-1<<endl;//插入根节点
for(int i = 1;i < n;i++){
cin>>x;
TreeNode* par = root;
while(1){
//如果x比根节点小
if(x < par->val){
//找到插入点
if(par->left == NULL){
par->left = new TreeNode(x);
cout<<par->val<<endl;
break;
}else{
par = par->left;
}
}else if(x > par->val){
if(par->right == NULL){
par->right = new TreeNode(x);
cout<<par->val<<endl;
break;
}else{
par = par->right;
}
}
}
}
return 0;
}
法二:使用cur和par指针
#include<iostream>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
};
int main(){
int n;
cin>>n;
int x;
cin>>x;
TreeNode* root = new TreeNode(x);
cout<<-1<<endl;//插入根节点
for(int i = 1;i < n;i++){
cin>>x;
TreeNode* node = new TreeNode(x);
TreeNode* par;//父指针
TreeNode* cur = root;//当前该插入的位置
while(1){
//如果x比根节点小,更新指针
if(x < cur->val){
par = cur;
cur = cur->left;
if(cur == NULL){
// cur = node;//错误写法
par->left = node;
cout<<par->val<<endl;
break;
}
}else{
par = cur;
cur = cur->right;
if(cur == NULL){
par->right = node;
cout<<par->val<<endl;
break;
}
}
}
}
return 0;
}