Description

/已知二叉排序树BiSortTree的部分代码如下，勿改动。
请在此基础上补充实现递归查找算法SearchBST和InsertBST。/
#include
using namespace std;
//BiNode
template
struct BiNode
{
DataType data;
BiNode lchild, rchild;
};

//BiSortTree
template
class BiSortTree
{
public:
BiSortTree(DataType r[],int n); //建立关键字序列r[0]~r[n-1]的二叉排序树
~BiSortTree( ); //析构函数，释放二叉排序树中所有结点，同二叉链表的析构函数
void InsertBST(BiNode&bt,DataType key); //插入key
BiNode SearchBST(BiNode bt,DataType key); //查找值为k的结点，返回值为k所在结点的地址
void InOrderBST(BiNode bt); //中序遍历二叉树（递归）
BiNode *GetRoot();//获取root值

private:
BiNode root; //二叉排序树（即二叉链表）的根指针
void Release(BiNode &bt); //析构函数调用
};

//构造函数，将r[0]~r[n-1]各个元素依次插入，生成一棵二叉排序树
template
BiSortTree::BiSortTree(DataType r[],int n)//构造函数
{
root=nullptr; //初始化空二叉树
int i;
for(i=0;iInsertBST(root,r[i]);//将结点s插入到二叉排序树中
}
}

//析构函数，调用Release释放内存
template
BiSortTree::~BiSortTree( )
{
Release(root);
}

//释放二叉排序树的存储空间，调用析构函数实现
template
void BiSortTree::Release(BiNode* &bt)
{
if (bt){
Release(bt->lchild); //释放左子树
Release(bt->rchild); //释放右子树
delete bt;
}
}

template
BiNode *BiSortTree::GetRoot()
{
return root;
}

template
void BiSortTree::InOrderBST(BiNode*bt)
{
if(bt==nullptr) return;
else
{
InOrderBST(bt->lchild);
cout<data<<” “;
InOrderBST(bt->rchild);
}
}

//在下面补充实现相关算法

//二叉排序树的主函数
int main( ){
int a[10],n;
n=0;
while(1)
{
cin>>a[n];
if(!a[n])break; //输入数据以0结束
n++;
}
BiSortTree bst(a,n);//构造二叉排序树
BiNode root;
root=bst.GetRoot();
cout<<”Inorder:”;
bst.InOrderBST(root);//中序遍历二叉排序树（得到递增有序序列）
cout<int x;
cin>>x;
BiNode s;
s=bst.SearchBST(root,x);
if(s==nullptr) cout<<”Find “<else cout<<”Find “<cout<return 0;
}

Input

Output

Sample Input

3 42 4 32 42 42 32 56 37 0 32

Sample Output

Inorder:3 4 32 37 42 56
Find 32 success

HINT

Source

Submit

  1. package Q1031;
  4. import java.util.Scanner;
  6. /**
  7.  *
  8.  * 二叉链式存储结构下的二叉树结点
  9.  *
  10.  */
  11. class BiTreeNode {
  12.     public Object data;// 结点的数据元素
  14.     public BiTreeNode lchild, rchild; // 左右孩子
  16.     public BiTreeNode() {// 构造一个空结点
  17.         this(null);
  18.     }
  20.     public BiTreeNode(Object data) {// 构造一棵左右孩子为空的结点
  21.         this(data, null, null);
  22.     }
  24.     public BiTreeNode(Object data, BiTreeNode lchild, BiTreeNode rchild) {// 构造一棵数据元素和左右孩子都不为空的结点
  25.         this.data = data;
  26.         this.lchild = lchild;
  27.         this.rchild = rchild;
  28.     }
  31. }
  32. /**
  33.  * 顺序表记录结点类
  34.  */
  35. class RecordNode {
  37.     public Comparable key; // 关键字
  38.     public Object element; // 数据元素
  39.     /*
  40.         public Object getElement() {
  41.             return element;
  42.         }
  44.         public void setElement(Object element) {
  45.             this.element = element;
  46.         }
  48.         public Comparable getKey() {
  49.             return key;
  50.         }
  52.         public void setKey(Comparable key) {
  53.             this.key = key;
  54.         }
  55.     */
  56.     public RecordNode() {
  57.     }
  59.     public RecordNode(Comparable key) { // 构造方法1
  60.         this.key = key;
  62.     }
  64.     public RecordNode(Comparable key, Object element) { // 构造方法2
  65.         this.key = key;
  66.         this.element = element;
  67.     }
  69.     public String toString() { // 覆盖toString()方法
  70.         return key+"";
  71.     }
  72. }
  74. class BSTree { //二叉排序树类
  76.     public BiTreeNode root;   //根结点
  78.     public BSTree() {  //构造空二叉排序树
  79.         root = null;
  80.     }
  81. /*
  82.     public BiTreeNode getRoot() {
  83.         return root;
  84.     }
  86.     public void setRoot(BiTreeNode root) {
  87.         this.root = root;
  88.     }
  89. */
  91.     public boolean isEmpty() { //判断是否空二叉树
  92.         return this.root == null;
  93.     }
  95.     public void inOrderTraverse(BiTreeNode p) { //中根次序遍历以p结点为根的二叉树
  96.         if (p != null) {
  97.             inOrderTraverse(p.lchild);
  98.             System.out.print(((RecordNode) p.data).toString() + " ");
  99.             inOrderTraverse(p.rchild);
  100.         }
  101.     }
  103.     //查找关键字值为key的结点,若查找成功返回结点值，否则返回null
  104.     public Object searchBST(Comparable key) {
  105.         if (key == null || !(key instanceof Comparable)) {
  106.             return null;
  107.         }
  108.         return searchBST(root, key);
  109.     }
  111.     //二叉排序树查找的递归算法
  112.     //在二叉排序树中查找关键字为key的结点。若查找成功则返回结点值，否则返回null
  113.     private Object searchBST(BiTreeNode p, Comparable key) {
  114.         if (p != null) {
  115.             if (key.compareTo(((RecordNode) p.data).key) == 0) //查找成功
  116.             {
  117.                 return p.data;
  118.             }
  119.             //     System.out.print(((RecordNode) p.data).key + "? ");
  120.             if (key.compareTo(((RecordNode) p.data).key) < 0) {
  121.                 return searchBST(p.lchild, key);     //在左子树中查找
  122.             } else {
  123.                 return searchBST(p.rchild, key);    //在右子树中查找
  124.             }
  125.         }
  126.         return null;
  127.     }
  129.     //在二叉排序树中插入关键字为Key,数据项为theElement的结点,若插入成功返回true,否则返回false
  130.     public boolean insertBST(Comparable key, Object theElement) {
  131.         if (key == null || !(key instanceof Comparable)) {//不能插入空对象或不可比较大小的对象
  132.             return false;
  133.         }
  134.         if (root == null) {
  135.             root = new BiTreeNode(new RecordNode(key, theElement)); //建立根结点
  136.             return true;
  137.         }
  138.         return insertBST(root, key, theElement);
  139.     }
  141.     //将关键字为key,数据项为theElement的结点插入到以p为根的二叉排序树中的递归算法
  142.     private boolean insertBST(BiTreeNode p, Comparable key, Object theElement) {
  143.         if (key.compareTo(((RecordNode) p.data).key) == 0) {
  144.             return false;             //不插入关键字重复的结点
  145.         }
  146.         if (key.compareTo(((RecordNode) p.data).key) < 0) {
  147.             if (p.lchild == null) {        //若p的左子树为空
  148.                 p.lchild=new BiTreeNode(new RecordNode(key, theElement));  //建立叶子结点作为p的左孩子
  149.                 return true;
  150.             } else {                      //若p的左子树非空
  151.                 return insertBST(p.lchild, key, theElement);   //插入到p的左子树中
  152.             }
  153.         } else if (p.rchild == null) {    //若p的右子树为空
  154.             p.rchild=new BiTreeNode(new RecordNode(key, theElement));    //建立叶子结点作为p的右孩子
  155.             return true;
  156.         } else {                          //若p的右子树非空
  157.             return insertBST(p.rchild, key, theElement);   //插入到p的右子树中
  158.         }
  159.     }
  161.     //二叉排序树中删除结点算法。若删除成功返回删除结点值，否则返回null
  162.     public Object removeBST(Comparable key) {
  163.         if (root == null || key == null || !(key instanceof Comparable)) {
  164.             return null;
  165.         }
  166.         //在以root为根的二叉排序树中删除关键字为elemKey的结点
  167.         return removeBST(root, key, null);
  168.     }
  170.     //在以p为根的二叉排序树中删除关键字为elemKey的结点。parent是p的父结点，递归算法
  171.     private Object removeBST(BiTreeNode p, Comparable elemKey, BiTreeNode parent) {
  172.         if (p != null) {
  173.             if (elemKey.compareTo(((RecordNode) p.data).key) < 0) { //在左子树中删除
  174.                 return removeBST(p.lchild, elemKey, p);    //在左子树中递归搜索
  175.             } else if (elemKey.compareTo(((RecordNode) p.data).key) > 0) { //在右子树中删除
  176.                 return removeBST(p.rchild, elemKey, p);    //在右子树中递归搜索
  177.             } else if (p.lchild != null && p.rchild != null) {
  178.                 //相等且该结点有左右子树
  179.                 BiTreeNode innext = p.rchild;    //寻找p在中根次序下的后继结点innext
  180.                 while (innext.lchild != null) { //即寻找右子树中的最左孩子
  181.                     innext = innext.lchild;
  182.                 }
  183.                 p.data=innext.data;              //以后继结点值替换p
  184.                 return removeBST(p.rchild, ((RecordNode) p.data).key, p); //递归删除结点p
  185.             } else {//p是1度和叶子结点
  186.                 if (parent == null) {  //删除根结点，即p==root
  187.                     if (p.lchild != null) {
  188.                         root = p.lchild;
  189.                     } else {
  190.                         root = p.rchild;
  191.                     }
  192.                     return p.data;       //返回删除结点p值
  193.                 }
  194.                 if (p == parent.lchild) { //p是parent的左孩子
  195.                     if (p.lchild != null) {
  196.                         parent.lchild=p.lchild;  //以p的左子树填补
  197.                     } else {
  198.                         parent.lchild=p.rchild;
  199.                     }
  200.                 } else if (p.lchild != null) { //p是parent的右孩子且p的左子树非空
  201.                     parent.rchild=p.lchild;
  202.                 } else {
  203.                     parent.rchild=p.rchild;
  204.                 }
  205.                 return p.data;
  206.             }
  207.         }
  208.         return null;
  209.     }
  210. }
  212. public class Main {
  213.     public static void main(String[] args) {
  214.         int temp;
  215.         int n;
  216.         n = 0;
  218.         Scanner scanner = new Scanner(System.in);
  219.         BSTree bst = new BSTree();//构造二叉排序树
  220.         while(true){
  221.             temp = scanner.nextInt();
  222.             if(temp == 0)break;
  223.             bst.insertBST(temp,n);
  224.             n++;
  225.         }
  226.         System.out.print("Inorder:");
  227.         bst.inOrderTraverse(bst.root);//中序遍历二叉排序树（得到递增有序序列）
  228.         System.out.println();
  229.         int x = scanner.nextInt();;
  230.         Object s = bst.searchBST(x);
  231.         if (s == null)  System.out.println("Find " + x +" failure");
  232.         else System.out.println("Find " + x +" success");
  233.     }
  234. }