网站开发 微信 支付搭建网站教程

网站开发 微信 支付,搭建网站教程,wordpress判断自定义页面,网站建设改代码改哪些二叉排序树是一种特殊的二叉树#xff0c;它的每个节点都满足#xff1a;左子树所有节点值小于当前节点#xff0c;右子树所有节点值大于当前节点。一、二叉排序树的核心结构首先定义树节点TreeNode#xff0c;包含左孩子、右孩子和节点值#xff1a;public class TreeNod…二叉排序树是一种特殊的二叉树它的每个节点都满足左子树所有节点值小于当前节点右子树所有节点值大于当前节点。一、二叉排序树的核心结构首先定义树节点TreeNode包含左孩子、右孩子和节点值public class TreeNode { public TreeNode lChild; public TreeNode rChild; public Integer data; public TreeNode(Integer data){ this.data data; } }二、二叉排序树的构建插入操作构建二叉排序树的过程本质是依次插入节点并维护 “左小右大” 规则的过程。以BinaryTree类的create方法为例public class BinaryTree { TreeNode root; public void create(Integer value) { TreeNode newNode new TreeNode(value); if (root null) { root newNode; return; } 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; } } } }三、二叉排序树的遍历方式遍历是按一定规则访问树中所有节点的操作二叉排序树常用深度优先遍历先序、中序、后序和广度优先遍历层次遍历。1. 深度优先遍历1先序遍历根→左→右void beforeOrder(TreeNode root) { if (root null) return; System.out.println(root.data); beforeOrder(root.lChild); beforeOrder(root.rChild); }2中序遍历左→根→右二叉排序树的中序遍历结果是 “升序序列”void inOrder(TreeNode root) { if (root null) return; inOrder(root.lChild); System.out.println(root.data); inOrder(root.rChild);3后序遍历左→右→根void afterOrder(TreeNode root) { if (root null) return; afterOrder(root.lChild); afterOrder(root.rChild); System.out.println(root.data); }2. 广度优先遍历层次遍历按 “从上到下、从左到右” 的顺序访问节点借助队列实现void levelOrder(TreeNode root) { LinkedListTreeNode queue new LinkedList(); queue.add(root); while (!queue.isEmpty()) { root queue.pop(); System.out.println(root.data); if (root.lChild ! null) { queue.add(root.lChild); } if (root.rChild ! null) { queue.add(root.rChild); } } }四、二叉排序树的查找操作利用 “左小右大” 的特性查找操作可以快速定位节点public TreeNode find(TreeNode root, Integer target) { if (root null) return null; TreeNode cur root; while (cur ! null) { if (cur.data.equals(target)) { return cur; } else if (cur.data target) { cur cur.rChild; } else { cur cur.lChild; } } return null; }五、测试验证package com.qcby; public class Test { public static void main(String[] args) { BinaryTree bt new BinaryTree(); // 构建二叉排序树 bt.create(5); bt.create(3); bt.create(7); bt.create(0); bt.create(4); bt.create(9); bt.levelOrder(bt.root); Integer target 8; TreeNode result bt.find(bt.root, target); if (result ! null) { System.out.println(找到了); } else { System.out.println(没找到); } } }结果