虚拟主机怎么设计网站,微信贷款怎么申请开通,最新的国际新闻事件,服饰网站建设 e-idea二叉树是一种非常重要的数据结构#xff0c;它同时具有数组和链表各自的特点#xff1a;它可以像数组一样快速查找#xff0c;也可以像链表一样快速添加。但是他也有自己的缺点#xff1a;删除操作复杂。我们先介绍一些关于二叉树的概念名词。二叉树#xff1a;是每个结点…二叉树是一种非常重要的数据结构它同时具有数组和链表各自的特点它可以像数组一样快速查找也可以像链表一样快速添加。但是他也有自己的缺点删除操作复杂。我们先介绍一些关于二叉树的概念名词。二叉树是每个结点最多有两个子树的有序树在使用二叉树的时候数据并不是随便插入到节点中的一个节点的左子节点的关键值必须小于此节点右子节点的关键值必须大于或者是等于此节点所以又称二叉查找树、二叉排序树、二叉搜索树。完全二叉树若设二叉树的高度为h除第 h 层外其它各层 (1h-1) 的结点数都达到最大个数第h层有叶子结点并且叶子结点都是从左到右依次排布这就是完全二叉树。满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。深度——二叉树的层数就是深度。二叉树的特点总结(1)树执行查找、删除、插入的时间复杂度都是O(logN)(2)遍历二叉树的方法包括前序、中序、后序(3)非平衡树指的是根的左右两边的子节点的数量不一致(4) 在非空二叉树中第i层的结点总数不超过 , i1(5)深度为h的二叉树最多有个结点(h1)最少有h个结点(6)对于任意一棵二叉树如果其叶结点数为N0而度数为2的结点总数为N2则N0N21二叉树的Java代码实现首先是树的节点的定义下面的代码中使用的是最简单的int基本数据类型作为节点的数据如果要使用节点带有更加复杂的数据类型换成对应的对象即可。/**** ClassName: com.tree.TreeNode* Description: 节点* author zhaokaiqiang* date 2014-12-5 下午4:43:24**/public class TreeNode {// 左节点private TreeNode lefTreeNode;// 右节点private TreeNode rightNode;// 数据private int value;private boolean isDelete;public TreeNode getLefTreeNode() {return lefTreeNode;}public void setLefTreeNode(TreeNode lefTreeNode) {this.lefTreeNode lefTreeNode;}public TreeNode getRightNode() {return rightNode;}public void setRightNode(TreeNode rightNode) {this.rightNode rightNode;}public int getValue() {return value;}public void setValue(int value) {this.value value;}public boolean isDelete() {return isDelete;}public void setDelete(boolean isDelete) {this.isDelete isDelete;}public TreeNode() {super();}public TreeNode(int value) {this(null, null, value, false);}public TreeNode(TreeNode lefTreeNode, TreeNode rightNode, int value,boolean isDelete) {super();this.lefTreeNode lefTreeNode;this.rightNode rightNode;this.value value;this.isDelete isDelete;}Overridepublic String toString() {return TreeNode [lefTreeNode lefTreeNode , rightNode rightNode , value value , isDelete isDelete ];}}下面给出二叉树的代码实现。由于在二叉树中进行节点的删除非常繁琐因此下面的代码使用的是利用节点的isDelete字段对节点的状态进行标识/**** ClassName: com.tree.Tree* Description: 二叉树的定义* author zhaokaiqiang* date 2014-12-8 上午7:51:49**/public class BinaryTree {// 根节点private TreeNode root;public TreeNode getRoot() {return root;}/*** 插入操作** param value*/public void insert(int value) {TreeNode newNode new TreeNode(value);if (root null) {root newNode;root.setLefTreeNode(null);root.setRightNode(null);} else {TreeNode currentNode root;TreeNode parentNode;while (true) {parentNode currentNode;// 往右放if (newNode.getValue() currentNode.getValue()) {currentNode currentNode.getRightNode();if (currentNode null) {parentNode.setRightNode(newNode);return;}} else {// 往左放currentNode currentNode.getLefTreeNode();if (currentNode null) {parentNode.setLefTreeNode(newNode);return;}}}}}/*** 查找** param key* return*/public TreeNode find(int key) {TreeNode currentNode root;if (currentNode ! null) {while (currentNode.getValue() ! key) {if (currentNode.getValue() key) {currentNode currentNode.getLefTreeNode();} else {currentNode currentNode.getRightNode();}if (currentNode null) {return null;}}if (currentNode.isDelete()) {return null;} else {return currentNode;}} else {return null;}}/*** 中序遍历** param treeNode*/public void inOrder(TreeNode treeNode) {if (treeNode ! null treeNode.isDelete() false) {inOrder(treeNode.getLefTreeNode());System.out.println(-- treeNode.getValue());inOrder(treeNode.getRightNode());}}}在上面对二叉树的遍历操作中使用的是中序遍历这样遍历出来的数据是增序的。下面是测试代码:public class Main {public static void main(String[] args) {BinaryTree tree new BinaryTree();// 添加数据测试tree.insert(10);tree.insert(40);tree.insert(20);tree.insert(3);tree.insert(49);tree.insert(13);tree.insert(123);System.out.println(root tree.getRoot().getValue());// 排序测试tree.inOrder(tree.getRoot());// 查找测试if (tree.find(10) ! null) {System.out.println(找到了);} else {System.out.println(没找到);}// 删除测试tree.find(40).setDelete(true);if (tree.find(40) ! null) {System.out.println(找到了);} else {System.out.println(没找到);}}}
