将要删除的节点的值，与节点 root 节点进行比较，若小于则去到左子树进行比较，若大于则去到右子树进行比较，重复以上操作直到找到一个节点的值等于删除的值，则将此节点删除。删除时有 4 中情况须分别处理：
1 //查找左子树最大值
2 int findLeftMax(Btree* root) {
3 /*采用递归方式查找
4 * if (root->rchild == NULL)
5 return root->data;
6 return findMax(root->rchild);
7 */
8 //采用循环查找
9 Btree indexNode = *root;
10 while (indexNode->rchild)
11 indexNode = indexNode->rchild;
12 return indexNode->data;
13 }
14
15
16 //采用递归的方式删除结点
17 /*
18 这种递归方式，是将要修改的结点的一层一层的返回
19 */
20 Btree deleteNode(Btree* root, int value) {
21 Btree compareNode = *root;
22 //节点为空（递归找不到value/根节点为空），直接返回
23 if (!compareNode)return compareNode;
24 //大于
25 if (compareNode->data > value) {
26 //左子树重新被赋值
27 compareNode->lchild = deleteNode(&(compareNode->lchild), value);
28 return compareNode;
29 }
30 //小于
31 else if (compareNode->data < value) {
32 //右子树重新被赋值
33 compareNode->rchild = deleteNode(&(compareNode->rchild), value);
34 return compareNode;
35 }
36 else {//等于
37 Btree temp = NULL;
38 //无左右子节点，直接返回NULL
39 if (compareNode->lchild == NULL && compareNode->rchild == NULL) {
40 delete compareNode;
41 }
42 //有左子树，返回左子树
43 else if (compareNode->lchild && compareNode->rchild == NULL) {
44 temp = compareNode->lchild;
45 delete compareNode;
46 }
47 //有右子树，返回右子树
48 else if (compareNode->rchild && compareNode->lchild == NULL) {
49 temp = compareNode->rchild;
50 delete compareNode;
51 }
52 else {
53 //这里采用左子树最大值替换
54 int leftMax = findLeftMax(&(compareNode->lchild));
55 //最大值替换删除结点的值
56 compareNode->data = leftMax;
57 //将最大值从树中删除
58 compareNode->lchild = deleteNode(&(compareNode->lchild), leftMax);
59 temp= compareNode;
60 }
61 return temp;
62 }
63 }
1 // 采用递归方式查找结点
2 /*
3 Bnode* queryByRec(Btree root, int value) {
4 if (root == NULL || root->data==value ){
5 return root;
6 }
7 else if (root->data < value) {
8 return queryByRec(root->lchild, value);
9 }
10 else {
11 return queryByRec(root->rchild, value);
12 }
13 }*/
14
15 // 使用非递归方式查找结点
16
17 Bnode* queryByLoop(Btree root, int value) {
18 while (root != NULL && root->data!=value) {
19 if (root->data>value) {
20 root = root->lchild;
21 }
22 else {
23 root = root->rchild;
24 }
25 }
26 return root;
27 }
1 void PreOrderRec(int x)//x为根节点
2 {
3 if (x == 0)return;//若遍历完成，返回函数
4 cout<<x;
5 PreOrderRec(a[x].left);//遍历左孩子
6 PreOrderRec(a[x].right);//遍历右孩子
7 }
1 void PreOrderRec(int x)//x为根节点
2 {
3 if (x == 0)return;//若遍历完成，返回函数
4 PreOrderRec(a[x].left);//遍历左孩子
5 cout<<x;
6 PreOrderRec(a[x].right);//遍历右孩子
7 }
