include

include<stdlib.h>

using namespace std;
typedef struct node {
int data;
struct node* left;
struct node* right;
}Node;
typedef struct tree{
Node* Tree_root=NULL;
}Tree;
void insert_tree(Tree tree, int data) {
Node node = (Node)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right=NULL;
if (tree->Tree_root == NULL) {
tree->Tree_root = node;
}
else
{
Node temp = tree->Tree_root;
while (temp != NULL)
{
if (data < temp->data)
if (temp->left == NULL)
{
temp->left = node;
return;
}
else
temp = temp->left;
else
if (temp->right == NULL)
{
temp->right = node;
return;
}
else
temp = temp->right;
}
}
}
void inorder(Node* node) {
if (node != NULL){
inorder(node->left);
cout << node->data <<" ";
inorder(node->right);
}

}
void preorder(Node* node) {
if (node != NULL) {
cout << node->data <<" ";

    inorder(node->left);
    inorder(node->right);
}

}
void postorder(Node* node) {
if (node != NULL) {
inorder(node->left);
inorder(node->right);
cout << node->data <<" ";

}

}
int search_order(Node* node, int m) {
if (node != NULL) {
if (node->data == m) {
cout << "find" << endl;;
return 0;
}
if (node->data > m)
return search_order(node->left,m);
if (node->data < m)
return search_order(node->right, m);
}
cout << "not find" << endl;
return -1;
}
Node* delete_order(Node* node, int m) {
Node* p, q;
if (node == NULL || node->data==m && node->left==NULL && node->right==NULL)
return NULL;
if (node->data == m)
{
/*case 1 叶子结点的删除操作/
if (node->left == NULL && node->right == NULL)
free(node);
/case 2 只有左子树/只有右子树的结点/
if (node->right == NULL) {
p = node;
node = node->left;
free(p);
}
else if (node->left == NULL) {
p = node;
node = node->right;
free(p);
}
/case 3左子树和右子树都存在的结点/
else {
//首先伪装成前驱结点
p = node;
q = node->left;
//假设有右子树，就不断向右推进，p随之推进
//假设q没有右子树，p和q都留在原地
while (q->right) {
p = q;
q = q->right;
}
//删除的是q,不是node;
node->data = q->data;
//情况:直接前驱为当前的结点的左结点的最右边的结点
if (p != node) {
//直接前驱结点一定不会存在右子树，已经推到最右边，所以左子树是他留给
//p的遗产，接到p的右子树上
p->right = q->left;
}
else {
p->left = q->left;
}
free(q);
}
}
else if (node->data > m)
{
node->left = delete_order(node->left, m);
}
else
node->right = delete_order(node->right, m);
return node;
}
int main()
{
Tree tree;
int arr[7] = {6,3,8,2,7,5,9};

for (int i = 0;i < 7;i++)
    insert_tree(&tree, arr[i]);
//检验BST插入操作
insert_tree(&tree, 9);//BST插入操作
preorder(tree.Tree_root);//线序序列
inorder(tree.Tree_root);//中序序列
postorder(tree.Tree_root);//后序序列
//查询操作
search_order(tree.Tree_root, 9);//查询操作
search_order(tree.Tree_root,-8);
//删除操作
delete_order(tree.Tree_root, 9);//删除操作
inorder(tree.Tree_root);//检测-8是否删除
system("pause");
return 0;

}