#include<iostream>
#include<algorithm>

using namespace std;
struct TreeNode {
	int data;
	TreeNode *parent,*left,*right;
};
TreeNode *pTree;
int arr[1010];
void pre_order(TreeNode *pTree){
	if(pTree!=NULL){
		cout<< pTree -> data  <<" ";
		pre_order(pTree->left);
		pre_order(pTree->right);
	}
	cout<<endl;
} 
int main() {
	/*通过插入构造一棵二叉查找树*/
	int n,p;
	cin>>n;
	for(int i=0; i<n; i++) {
		cin>>p;
		arr[i]=p;
		if(pTree == NULL) {
			pTree=new TreeNode;
			pTree->data=p;
			pTree->left=pTree->right=NULL;
		} else {
			TreeNode *point = pTree;
			while(true) {
				if(point->data >  p) {
					if(point->left==NULL) {
						point->left = new TreeNode;
						point->left->data=p;
						point->left->left=point->left->right=NULL;
						break;
					} else {
						point=point->left;
						continue;
					}
				}
				if(point->data <= p) {
					if(point->right==NULL) {
						point->right = new TreeNode;
						point->right->data=p;
						point->right->left=point->right->right=NULL;
						break;
					} else {
						point=point->right;
						continue;
					}
				}
			}
		}
	}
	pre_order(pTree);
	/*从这里开始 树就造完了，接下来尝试删除某些节点*/
	int del;
	cin>>del;
	TreeNode *point = pTree,*tmp=NULL;//tmp为父节点指针
	int lr= -1;/* 0 left  1 right */
	while(true) {
		if(point == NULL) {
			break;
		}
		if(point->data >  del) {
			tmp=point;
			lr=0;
			point=point->left;
			continue;
		}
		if(point->data < del) {
			tmp=point;
			lr=1;
			   point=point->right;
			continue;
		}
		if(point->data == del) {
			TreeNode *l=point->left,*r=point->right,*op=point;
			if(point->left==NULL&&point->right!=NULL) {
				op=point->right;
				if(lr==1)tmp->right=op;
				if(lr==0)tmp->left=op;
			}
			if(point->left!=NULL&&point->right==NULL) {
				op=point->left;
				if(lr==1)tmp->right=op;
				if(lr==0)tmp->left=op;
			}
			if(point->left!=NULL&&point->right!=NULL) {
				TreeNode *tmpop;//op的父节点指针 
				op=point->right;
				tmpop=op;
				while(true) {
					if(op->left==NULL) {
						break;
					} else tmpop=op,op=op->left;
				}
				tmpop->left=op->right;
			} 
			
			delete [] point;
		}
	}
	pre_order(pTree);
	return 0;
}

1 total views, 1 views today