二叉搜索树的结构java’pta'

### 关于二叉搜索树的结构及其Java实现 #### 定义与特性 二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树数据结构，具有如下性质[^2]: - 对任意节点`n`而言，其左子树中的所有节点值均严格小于`n`的关键字； - 同样地，对于右子树，则所有的关键字都大于等于当前节点的关键字。 这种有序性使得查找、插入和删除操作变得高效。然而需要注意的是，如果输入序列已经排序过，那么构建出来的BST可能会退化成链表形式，从而影响性能。 #### 数据结构设计 在Java中表示一个简单的二叉搜索树可以通过创建类来完成： ```java class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int value){ this.val = value; left = null; right = null; } } ``` 这里定义了一个名为`TreeNode`的内部静态类用于存储单个节点的信息，包括整数值`val`以及指向左右孩子的指针`left`和`right`。 #### 插入新元素的方法 当向BST中添加新的元素时，应该遵循上述提到的规则来进行放置: ```java public void insert(TreeNode root, int key) { if (root == null) { // 如果根为空则新建节点作为根节点 root = new TreeNode(key); return ; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode temp = queue.poll(); if (key < temp.val && temp.left != null || key >= temp.val && temp.right != null) { if (key < temp.val) queue.add(temp.left); else queue.add(temp.right); } else { if (key < temp.val) temp.left = new TreeNode(key); else temp.right = new TreeNode(key); break; } } } ``` 注意这段代码实现了按层序遍历来寻找合适的位置进行插入的操作方式，而不是传统的递归方法。这样做是为了后续能够方便地检查是否构成完全二叉树并获取层序遍历的结果。 #### 判断是否为完全二叉树及输出层序遍历结果 为了验证最终形成的二叉搜索树是不是完全二叉树，并获得它的层次遍历序列，可以采用广度优先搜索算法(BFS): ```java import java.util.*; public List<Integer> levelOrderTraversalAndCheckCompleteBT(TreeNode root) { boolean flag = false; //标记遇到的第一个null之后不能再有非空孩子 ArrayList<Integer> result = new ArrayList<>(); if (root==null){ System.out.println("The tree is empty."); return Collections.emptyList(); } Deque<TreeNode> deque = new ArrayDeque<>(); deque.offerLast(root); while(!deque.isEmpty()){ TreeNode node = deque.pollFirst(); if(node!=null){ result.add(node.val); if(flag){ //一旦发现前面出现了null而后面还有非空的孩子就不是完全二叉树了 System.out.println("This binary search tree isn't a complete binary tree"); return result; } deque.offerLast(node.left); deque.offerLast(node.right); }else{ flag=true; //遇到了第一个null } } System.out.println("This binary search tree is also a complete binary tree!"); return result; } ``` 通过以上函数不仅可以得到按照从上到下逐层访问各个节点值得列表，还可以检测出该树是否满足完全二叉树的要求——即除了最后一层外其他各层都被填满，并且最后一层的所有节点尽可能靠左边排列。