最近终于静下心来,自己实现了个二叉排序树,还是很有成就感的。
package tree; public class TreeNode<T> { //结点存放的数据 public T data; //当前结点的父结点 public TreeNode<T> parent; //当前结点的左孩子 public TreeNode<T> leftChild; //当前结点的右孩子 public TreeNode<T> rightChild; public TreeNode(T data,TreeNode<T> parent) { this.data = data; this.leftChild = null; this.rightChild = null; this.parent = parent; } } package tree; /** * 二叉排序树或者是一棵空树, 或者是一棵具有如下性质的二叉树 * (1)、若左子树不空,则左子树上所有结点的值均小于它的根结点的值; * (2)、若右子树不空,则右子树上所有结点的值均大于它的根结点的值; * (3)、左、右子树也分别为二叉排序树; */ //二叉排序树的结构通常不是一次生成的,而是在查找过程中动态构建的; public class BinarySortTree<T extends Comparable<T>> { //根结点指针 public TreeNode<T> rootNode = null; //二叉树的结点个数 public int nodeCount = 0; //获取targetData在二叉排序树中对应的结点指针 public TreeNode<T> find(T targetData) { TreeNode<T> curNode = this.rootNode; while (curNode != null) { T curNodeData = curNode.data; if(curNodeData.compareTo(targetData) == 0) { return curNode; } else if(curNodeData.compareTo(targetData) > 0) { curNode = curNode.leftChild; } else { curNode = curNode.rightChild; } } return null; } public TreeNode<T> add(T targetData) { TreeNode<T> targetNode= find(targetData); //已经存在,不用再插入新结点 if(targetNode != null) { return targetNode; } //没有根结点,需要创建一个根结点,存放数据targetData if(this.rootNode == null) { this.rootNode = new TreeNode<T>(targetData, null); this.nodeCount = 1; return this.rootNode; } //已经存在根节点的情况,但是没有对应targetData的结点 TreeNode<T> insertPos = findInsertPos(targetData); TreeNode<T> tempNode = new TreeNode<T>(targetData, insertPos); this.nodeCount++; if(targetData.compareTo(insertPos.data) > 0 ) { insertPos.rightChild = tempNode; } else { insertPos.leftChild = tempNode; } return tempNode; } public void delete(T targetData) { TreeNode<T> tagNode = find(targetData); //不存在,直接返回 if( tagNode == null) { return; } //要删除的结点是叶子结点 if(tagNode.leftChild == null && tagNode.rightChild == null) { deleteWhenLeaf(tagNode); } //要删除的结点只有左子树,或只有右子树 else if(tagNode.leftChild == null || tagNode.rightChild == null) { deleteWhenSingleChild(tagNode); } else { deleteWhenTwoChild(tagNode); } } //删去叶子结点不破坏整棵树的结构,只需修改其父结点的孩子指针 private void deleteWhenLeaf(TreeNode<T> tagNode) { this.nodeCount--; TreeNode<T> parent = tagNode.parent; //要删除的是根结点 if(parent == null) { this.rootNode = null; } else { if(parent.leftChild == tagNode) { parent.leftChild = null; } else { parent.rightChild = null; } } } //若p结点只有左子树PL或右子树PR,此时只要令PL或PR直接成为其双亲结点f的左子树(当*p是左子树) //或右子树(当*p是右子树)即可 private void deleteWhenSingleChild(TreeNode<T> tagNode) { this.nodeCount--; //当前结点的父亲 TreeNode<T> parent = tagNode.parent; //当前结点的左孩子 TreeNode<T> left = tagNode.leftChild; //当前结点的右孩子 TreeNode<T> right = tagNode.rightChild; if(left != null) { left.parent = parent; } else { right.parent = parent; } //要删除的是根结点 if(parent == null) { if(left != null) { this.rootNode = left; } else { this.rootNode = right; } } else//删除的结点不是根结点 { if(left != null) { parent.leftChild = left; } else { parent.rightChild = right; } } } //tagNode结点的后继结点肯定无左子树;前驱结点肯定没有右子树; //由于tagNode既有左孩子,又有右孩子,所以前驱和后继都不可能是null //假如tagNode的前驱是before,则用before代替tagNode位置; //before的左子树代替before的位置 private void deleteWhenTwoChild(TreeNode<T> tagetNode) { this.nodeCount--; //tagetNode的前驱结点是before TreeNode<T> before = searchPredecessor(tagetNode); //1.before的左子树取代结点before的位置 if(before.parent.leftChild == before) { before.parent.leftChild = before.leftChild; } else { before.parent.rightChild = before.leftChild; } if(before.leftChild != null) { before.leftChild.parent = before.parent; } //2.before取代tagetNode的位置 before.parent = tagetNode.parent; before.leftChild = tagetNode.leftChild; before.rightChild = tagetNode.rightChild; //3.改变tagetNode的父结点的孩子指针 if(tagetNode.parent == null) { this.rootNode = before; } else { if(tagetNode.parent.leftChild == tagetNode) { tagetNode.parent.leftChild = before; } else { tagetNode.parent.rightChild = before; } } } //获取targetData在二叉排序中插入位置 //如果targetData在二叉树中已经存在,则不需要再插入,返回null public TreeNode<T> findInsertPos(T targetData) { //将要插入的位置 TreeNode<T> willInsert = null; TreeNode<T> curNode = this.rootNode; while (curNode != null) { T curNodeData = curNode.data; //结点已经存在,插入位置设为null if(curNodeData.compareTo(targetData) == 0) { willInsert = null; break; } else if(curNodeData.compareTo(targetData) >0) { willInsert = curNode; curNode = curNode.leftChild; } else { willInsert = curNode; curNode = curNode.rightChild; } } return willInsert; } //二叉排序树的中序遍历,查找tagetNode结点的后继结点 //如果没有后继结点,则返回null; public TreeNode<T> searchSuccessor(TreeNode<T> tagetNode) { if(tagetNode == null) { return null; } //从右子树中寻找后继结点 if(tagetNode.rightChild != null) { return searchMinValueNode(tagetNode.rightChild); } //从父节点向上寻找后继 else { //根结点没有右子树,就没有后继结点 if(tagetNode.parent == null) { return null; } else { TreeNode<T> temp = tagetNode; while (temp.parent != null) { if(temp.parent.leftChild == temp) { break; } temp = temp.parent; } return temp.parent; } } } //查找某个结点的前驱,如果没有前驱结点,则返回null public TreeNode<T> searchPredecessor(TreeNode<T> tagetNode) { if(tagetNode == null) { return null; } if(tagetNode.leftChild != null) { return searchMaxValueNode(tagetNode.leftChild); } else { //根结点没有左子树,就没有前驱结点 if(tagetNode.parent == null) { return null; } else { TreeNode<T> temp = tagetNode; while (temp.parent != null) { if(temp.parent.rightChild == temp) { break; } temp = temp.parent; } return temp.parent; } } } //查找以root为根结点的二叉排序树中,最小的数据值对应的结点 public TreeNode<T> searchMinValueNode(TreeNode<T> root) { if(root == null) { return null; } TreeNode<T> resultNode = root; while (resultNode.leftChild != null) { resultNode = resultNode.leftChild; } return resultNode; } //查找以root为根结点的二叉排序树中,最大的数据值对应的结点 public TreeNode<T> searchMaxValueNode(TreeNode<T> root) { if(root == null) { return null; } TreeNode<T> resultNode = root; while (resultNode.rightChild != null) { resultNode = resultNode.rightChild; } return resultNode; } public void inorderTraversal(TreeNode<T> node) { if(node == null) { return; } inorderTraversal(node.leftChild); System.out.println(node.data); inorderTraversal(node.rightChild); } }
相关推荐
说明: 可实现:构造树,插入,查找,删除. 通过模式的选择,可以插入值相等的点.但是不建议使用.
java 实现二叉排序树
数据结构 二叉排序树 二叉搜索树 java swing图形界面实现
ios编程:实现二叉排序树增删改查。 开发环境:windows下codeblocks。
用java语言来构造二叉排序树,理解java数据结构。
C++编写的查找算法,用二叉排序树查找,是在VC++6.0上实现的
分别采用二叉链表和顺序表作存储结构,实现对二叉排序树与平衡二叉树的操作。 重庆理工大学,软件工程系,课程设计。
自然语言理解 关于词频统计的代码 利用treemap来完成
java语言控制台实现的二叉排序树,含详细设计文档
写一算法,判断一棵二叉树是否是一棵二叉排序树。
平衡二叉排序树的算法实现
红黑树、二叉平衡树、二叉排序树的java实现,做了泛型封装,可以装任何对象,其中还附带工具类,可以友好一点地打印树,还有各种遍历树方法的递归实现和非递归实现。
NULL 博文链接:https://709002341.iteye.com/blog/2258327
排序二叉树的基础代码,包含递归非递归二叉树构建、递归非递归遍历,获取最小最大值。
二叉排序树的插入删除中序遍历等!!!!!!!!!!!!!!
如果您想在Matlab中实现查找二叉排序树,可以按照以下步骤进行: 1/定义二叉树节点类型 2/实现二叉排序树的插入操作 3/实现二叉排序树的查找操作
java使用jtree动态实现二叉树,包含二叉树的插入删除很查找
java编写的二叉树的各种操作,其中包括二叉排序树和平衡二叉树的各项操作,用于学习数据结构,可以运行
数据结构课设代码完整版,使用了java