织梦dedecms微信微网站模板做网站加盟

织梦dedecms微信微网站模板,做网站加盟,个人网站建设研究意义,石碣企业网站建设公司一、概念二叉排序树#xff08;也叫二叉搜索树#xff09;是一种基于 “左小右大” 规则的有序二叉树特点#xff1a;左子节点的值 小于 父节点的值右子节点的值 大于 父节点的值每个节点由 3 部分组成#xff08;类 / 对象结构#xff09;#xff1a;lChild#xff1a;…一、概念二叉排序树也叫二叉搜索树是一种基于 “左小右大” 规则的有序二叉树特点左子节点的值小于父节点的值右子节点的值大于父节点的值每个节点由 3 部分组成类 / 对象结构lChild左子节点引用data节点存储的数据rChild右子节点引用二、节点定义package com.qcby.Tree; public class TreeNode { public TreeNode lChild; // 左子节点 public TreeNode rChild; // 右子节点 public Integer data; // 节点数据 // 构造方法初始化节点数据 public TreeNode(Integer data) { this.data data; } }三、二叉排序树的相关操作包括创建插入节点、遍历、查询1. 新建插入节点插入节点的逻辑遵循 “左小右大” 的规则步骤如下若树为空root null新节点直接作为根节点若树非空循环判断新节点与当前节点的大小新节点值大于当前节点向右子树查找直到右子节点为空插入新节点新节点值小于 / 等于当前节点向左子树查找直到左子节点为空插入新节点。package com.qcby.Tree; import java.util.LinkedList; public class BinaryTree { TreeNode root; // 二叉树根节点 // 向二叉排序树插入节点 public void create(Integer value) { TreeNode newNode new TreeNode(value); // 情况1树为空新节点作为根 if (root null) { root newNode; return; } // 情况2树非空循环查找插入位置 TreeNode curNode root; while (true) { if (curNode.data newNode.data) { // 新节点更大走右子树 if (curNode.rChild null) { curNode.rChild newNode; return; } curNode curNode.rChild; } else { // 新节点更小/相等走左子树 if (curNode.lChild null) { curNode.lChild newNode; return; } curNode curNode.lChild; } } } }2. 遍历操作二叉排序树支持 4 种常见遍历方式分别对应不同的访问顺序1先序遍历根→左→右// 先序遍历 public void beforeOrder(TreeNode node) { if (node null) { return; } System.out.print(node.data ); // 访问根 beforeOrder(node.lChild); // 遍历左子树 beforeOrder(node.rChild); // 遍历右子树 }2中序遍历左→根→右二叉排序树的中序遍历结果是升序序列// 中序遍历 public void inOrder(TreeNode node) { if (node null) { return; } inOrder(node.lChild); // 遍历左子树 System.out.print(node.data ); // 访问根 inOrder(node.rChild); // 遍历右子树 }3后序遍历左→右→根// 后序遍历 public void afterOrder(TreeNode node) { if (node null) { return; } afterOrder(node.lChild); // 遍历左子树 afterOrder(node.rChild); // 遍历右子树 System.out.print(node.data ); // 访问根 }4层次遍历广度优先按层级访问通过队列实现依次访问每一层的节点// 层次遍历 public void levelOrder(TreeNode root) { if (root null) { return; } LinkedListTreeNode queue new LinkedList(); queue.add(root); while (!queue.isEmpty()) { TreeNode node queue.poll(); System.out.print(node.data ); // 访问当前节点 if (node.lChild ! null) { queue.add(node.lChild); // 左子节点入队 } if (node.rChild ! null) { queue.add(node.rChild); // 右子节点入队 } } }3. 节点查询利用 “左小右大” 的特性递归查找目标节点// 递归查询指定节点 public TreeNode find(TreeNode root, Integer data) { if (root null) { // 节点为空未找到 return null; } if (root.data.equals(data)) { // 找到目标节点 return root; } if (root.data data) { // 目标值更大查右子树 return find(root.rChild, data); } else { // 目标值更小查左子树 return find(root.lChild, data); } }