关于搜索二叉树的各种操作(插入，删除，输出，查找，递归非递归排序)

最近整理了一下有关二叉树的各种操作：

#include<iostream>
#include<vector>
#include<stack>
#include<deque>
using namespace std;

//node结构
struct BTnode {
BTnode * left;
BTnode * right;
int value;
} ;

//逐行打印 改进的广搜 ，需要记录打印回车的位置
void PrintTree(BTnode ** root){
if(*root==NULL){
return ;
}
deque<BTnode*> bt_deque;
bt_deque.push_back(*root);

BTnode *last;
while(bt_deque.size()){
int size=bt_deque.size();
//记录当前队列的大小，用来打印回车
while(size--){
BTnode *temp=bt_deque.front();
bt_deque.pop_front();
cout<<temp->value<<" ";
if(temp->left) bt_deque.push_back(temp->left);
if(temp->right) bt_deque.push_back(temp->right);
}
cout<<endl;

}

}
//前序递归遍历
void Preorder(BTnode * root){
if(root==NULL){
return ;
}

printf("%d ",root->value);
Preorder(root->left);
Preorder(root->right);
}
//中序递归遍历
void Inorder(BTnode * root){

if(root==NULL){
return ;
}

Inorder(root->left);
printf("%d ",root->value);
Inorder(root->right);
}
//后序递归遍历
void Postorder(BTnode * root){
if(root==NULL){
return ;
}

Postorder(root->left);
Postorder(root->right);
printf("%d ",root->value);
}


//前序非递归遍历
void PreOrder_unrec(BTnode* root){
stack<BTnode*> nodes;
if(root==NULL) return;
nodes.push(root);
BTnode * temp;
while(!nodes.empty()){
temp=nodes.top();
nodes.pop();
cout<<temp->value<<" ";
if(temp->right)
nodes.push(temp->right);
if(temp->left)
nodes.push(temp->left);
}
}

//中序非递归遍历
void InOrder_unrec(BTnode* root){
stack<BTnode*> nodes;
if(root==NULL) return;
//nodes.push(root);
BTnode * temp=root;
while(temp||!nodes.empty()){
//遍历左子树
while(temp!=NULL){
nodes.push(temp);
temp=temp->left;
}
if(!nodes.empty()){
temp=nodes.top();
cout<<temp->value<<" ";
nodes.pop();
temp=temp->right;
}
}
}

//后序非递归遍历
void PostOrder_unrec(BTnode* root){
if(!root) return;
BTnode* temp=root;
BTnode* pre=NULL;

stack<BTnode*> nodes;
while(temp||!nodes.empty()){
if(temp){
nodes.push(temp);
temp=temp->left;
}else{
temp=nodes.top();
// 判断右边子节点是否被访问
if(temp->right&&temp->right!=pre){
//nodes.push(temp->right);
temp=temp->right;
}else{
pre=temp;
nodes.pop();
cout<<temp->value<<" ";
temp=NULL;
}
}
}
}
//插入
void insert(BTnode **root,int value){
if(*root==NULL){
BTnode *temp=new BTnode;
temp->value=value;
temp->left=NULL;
temp->right=NULL;
*root=temp;

temp=NULL;
delete temp;
return;
}
if(value<=(*root)->value){
insert(&(*root)->left,value);
}
else{
insert(&(*root)->right,value);
}
}

//搜索
BTnode* search(BTnode *root,int value){
if(root==NULL){
printf("ROOT IS NULL\n");
return NULL;
}
if(root->value==value){
printf("found the node\n");
return root;
}
if(root->value>value){
search(root->left,value);
} 
else {
search(root->right,value);
}
}
//查找并返回其父亲节点，以便删除操作
BTnode * search_with_parent(BTnode *root,int value,int *position){
BTnode *parent=root;
*position =0;
while(root!=NULL){

if(root->value==value){
return parent;
}else{
parent=root;
if(root->value>value){
root=root->left;
*position=-1;
}else if(root->value<value){
root=root->right;
*position=1;
}
}
}
return NULL;
}

//删除节点
int deletenode(BTnode **root,int value){
int position;
//查找到节点位置对应的父亲节点
BTnode *parent=search_with_parent(*root,value,&position);

if(parent==NULL){ 
printf("null node");
return 0;
}
BTnode *node;
//根据位置判断是父节点的哪一个孩子
if(position==0){
  node=parent;
  cout<<"same node"<<endl;
}else if(position==-1){
node=parent->left;
cout<<"left node"<<endl;
}else {
node=parent->right;

cout<<"right node"<<endl;

}
//没有孩子，直接将父节点指向NULL
if(!node->left&&!node->right){
cout<<"have none leaves"<<endl;
if(position==-1){
parent->left=NULL;
}
else if(position==1){
parent->right=NULL;
}else{
cout<<"last node";
*root=NULL;
delete *root;

}

node=NULL;
delete node;
return 1;
}
//有一个孩子，将父节点指向孩子
if(!node->left&&node->right){
cout<<"have right leaves"<<endl;
if(position==1)
parent->right=node->right;
if(position==-1)
parent->left=node->right;
if(position==0)
parent=node->right;
node=NULL;
delete node;
return 1;
}

if(node->left&&!node->right){
cout<<"have left leaves"<<endl;
if(position==1)
parent->right=node->left;

if(position==-1)
parent->left=node->left;

if(position==0){
*root=node->left;
}
node=NULL;
delete node;
return 1;
}

cout<<"both leaves"<<endl;
//两个孩子都有，将待删除节点的内容替换为中序遍历的下一个节点的内容，并删除中序遍历下一个节点
BTnode *temp=node->right;
BTnode *pre_temp=node;
if(temp->left==NULL){
node->value=temp->value;
node->right=NULL;
temp=NULL;
delete temp;
return 1;
}

while(temp->left){
pre_temp=temp;
temp=temp->left;

}
node->value=temp->value;
pre_temp->left=NULL;

temp=NULL;
delete temp;
return 1;

}



int main(){
BTnode * root=NULL;
insert(&root,10);
insert(&root,14);
insert(&root,1);
insert(&root,10);
insert(&root,2);
insert(&root,12);
insert(&root,15);
PostOrder_unrec(root);
cout<<"\n";
PrintTree(&root);
cout<<endl;

deletenode(&root,15);
deletenode(&root,10);
deletenode(&root,10);
deletenode(&root,1);

deletenode(&root,14);
deletenode(&root,12);
deletenode(&root,2);


PrintTree(&root);



return 0;
}