二叉树的插入、删除、查寻等接口实现和经典笔试题

2023-09-24 12:02:51

代码实现：
class BSTNode<T extends Comparable>{
private T data; // 数据域
private BSTNode left; // 左孩子域
private BSTNode right; // 右孩子域

public BSTNode(T data, BSTNode<T> left, BSTNode<T> right) {
    this.data = data;
    this.left = left;
    this.right = right;
}

public T getData() {
    return data;
}

public void setData(T data) {
    this.data = data;
}

public BSTNode<T> getLeft() {
    return left;
}

public void setLeft(BSTNode<T> left) {
    this.left = left;
}

public BSTNode<T> getRight() {
    return right;
}

public void setRight(BSTNode<T> right) {
    this.right = right;
}

}

/**

BST树的实现
@param
*/
class BST<T extends Comparable>{
private BSTNode root; // 指向根节点

/**
- BST树的初始化
  */
  public BST() {
  this.root = null;
  }
/**
- BST树的插入操作
- @param data
  */
  public void insert(T data){
}
}
/**
- 非递归实现BST树的删除操作
- @param data
  */
  public void non_remove(T data){
  if(this.root == null){
  return;
  }
  // 1. 先搜索BST树，找到待删除的节点
  BSTNode cur = this.root;
  BSTNode parent = null;
  while(cur != null){
  if(cur.getData().compareTo(data) > 0){
  parent = cur;
  cur = cur.getLeft();
  } else if(cur.getData().compareTo(data) < 0){
  parent = cur;
  cur = cur.getRight();
  } else {
  break;
  }
  }
  
  if(cur == null){ // 表示BST树中没有值为data的节点
  return;
  }
  // 2. 判断删除节点是否有两个孩子，如果有，用前驱的值代替，直接删除前驱
  if(cur.getLeft() != null && cur.getRight() != null){
  // 找前驱节点，用前驱节点的值代替待删节点的值，然后直接删除前驱节点cur
  BSTNode old = cur;
  parent = cur;
  cur = cur.getLeft();
  while(cur.getRight() != null){
  parent = cur;
  cur = cur.getRight();
  }
  old.setData(cur.getData()); // 前驱节点的值代替待删节点的值
  }
  
  // 3. 删除有一个孩子的节点，或者没有孩子的节点（看作有一个孩子，孩子是null）
  BSTNode child = cur.getLeft();
  if(child == null){
  child = cur.getRight();
  }
  
  if(parent == null){ // 删除的就是根节点
  this.root = child;
  } else {
  if(parent.getLeft() == cur){
  parent.setLeft(child);
  } else {
  parent.setRight(child);
  }
  }
  }
  /**
- 前序遍历BST树的API接口
  */
  public void preOrder(){
  System.out.print(“递归前序遍历:”);
  preOrder(this.root);
  System.out.println();
  }
/**
- 前序遍历BST树的递归操作 VLR
- @param root
  */
  private void preOrder(BSTNode root) {
  if(root != null){
  System.out.print(root.getData() + " ");
  preOrder(root.getLeft());
  preOrder(root.getRight());
  }
  }
/**
- 中序遍历BST树的API接口
  */
  public void inOrder(){
  System.out.print(“递归中序遍历:”);
  inOrder(this.root);
  System.out.println();
  }
/**
- 中序遍历BST树的递归操作 LVR
- @param root
  */
  private void inOrder(BSTNode root) {
  if(root != null){
  inOrder(root.getLeft());
  System.out.print(root.getData() + " ");
  inOrder(root.getRight());
  }
  }
/**
- 后序遍历BST树的API接口
  */
  public void postOrder(){
  System.out.print(“递归后序遍历:”);
  postOrder(this.root);
  System.out.println();
  }
/**
- 中序遍历BST树的递归操作 LRV
- @param root
  */
  private void postOrder(BSTNode root) {
  if(root != null){
  postOrder(root.getLeft());
  postOrder(root.getRight());
  System.out.print(root.getData() + " ");
  }
  }
/**
- 层序遍历BST树的API接口
  */
  public void levelOrder(){
  System.out.print(“递归层序遍历:”);
  int hight = level();
  for (int i = 0; i < hight; i++) {
  levelOrder(this.root, i);
  }
  System.out.println();
  }
/**
- 层序遍历的递归实现
- @param root
- @param i
  */
  private void levelOrder(BSTNode root, int i) {
  if(root != null){
  if(i == 0){
  System.out.print(root.getData() + " ");
  return;
  }
  levelOrder(root.getLeft(), i-1);
  levelOrder(root.getRight(), i-1);
  }
  }
/**
- 返回BST树中所有节点个数的API
- @return
  */
  public int number(){
  return number(this.root);
  }
/**
- 以root为根节点计算BST树的节点个数
- @param root
- @return
  */
  private int number(BSTNode root) {
  if(root == null){
  return 0;
  } else {
  return number(root.getLeft()) + number(root.getRight()) + 1;
  }
  }
/**
- 返回BST树的高度/层数的API
- @return
  */
  public int level(){
  return level(this.root);
  }
/**
- 计算以root为根节点的BST树的高度
- @param root
- @return
  /
  private int level(BSTNode root) {
  if(root == null){
  return 0;
  } else {
  int left = level(root.getLeft());
  int right = level(root.getRight());
  return left > right ? left+1 : right+1;
  }
  }
  /*
- 求BST树的镜像翻转API
  */
  public void mirror(){
  mirror(this.root);
  }
/**
- 求BST镜像翻转的递归实现
- @param root
  */
  private void mirror(BSTNode root) {
  if(root == null){
  return;
  }
  
  BSTNode tmp = root.getLeft();
  root.setLeft(root.getRight());
  root.setRight(tmp);
  
  mirror(root.getLeft());
  mirror(root.getRight());
  }
/**
- 把BST树中，满足[begin, end]区间的所有元素打印出来
- @param begin
- @param end
  */
  public void printAreaDatas(T begin, T end){
  printAreaDatas(this.root, begin, end);
  System.out.println();
  }
private void printAreaDatas(BSTNode root, T begin, T end) {
if(root == null){
return;
}
```
 // 如果当前节点的值小于begin，就不用再递归节点的左子树了
 if(root.getData().compareTo(begin) > 0){
     printAreaDatas(root.getLeft(), begin, end);
 }

 //root.getData();
 if(root.getData().compareTo(begin) >= 0
 && root.getData().compareTo(end) <= 0){
     System.out.print(root.getData() + " ");
 }

 // 当前节点的值小于end，才有必要继续访问当前节点的右子树
 if(root.getData().compareTo(end) < 0){
     printAreaDatas(root.getRight(), begin, end);
 }
```
}

/**
- 判断一个二叉树是否是BST树，是返回true，否则返回false
  */
  public boolean isBSTree(){
  //return isBSTree(this.root);
  T value = null;
  return isBSTree(this.root, value);
  }
/**
- value记录的是中序遍历上一个元素的值
- @param root
- @param value
- @return
  */
  private boolean isBSTree(BSTNode root, T value) {
  if(root == null){
  return true;
  }
  
  // 左子树已经不满足BST树性质了，直接返回，不用继续向下递归了
  if(!isBSTree(root.getLeft(), value)){
  return false;
  }
  
  // root.getData value =>
  if(value != null && value.compareTo(root.getData()) > 0){
  return false;
  }
  // 注意当前节点判断完成后，需要更新一下value值
  value = root.getData();
  
  return isBSTree(root.getRight(), value);
  }
  private boolean isBSTree(BSTNode root) {
  if(root == null){
  return true;
  }
  
  if(root.getLeft() != null
  && root.getLeft().getData().compareTo(root.getData()) > 0){
  return false;
  }
  if(root.getRight() != null
  && root.getData().compareTo(root.getRight().getData()) > 0){
  return false;
  }
  return isBSTree(root.getLeft()) && isBSTree(root.getRight());
  }
/**
- 返回两个节点的最近公共祖先节点
- @param data1
- @param data2
- @return
  */
  public T getLCA(T data1, T data2){
  return getLCA(this.root, data1, data2);
  }
private T getLCA(BSTNode root, T data1, T data2) {
if(root == null){
return null;
}
```
 if(root.getData().compareTo(data1) > 0
     && root.getData().compareTo(data2) > 0){
     return getLCA(root.getLeft(), data1, data2);
 } else if(root.getData().compareTo(data1) < 0
             && root.getData().compareTo(data2) < 0){
     return getLCA(root.getRight(), data1, data2);
 } else {
     return root.getData();
 }
```
}

码农公寓

相关文章