JAVA实现二叉排序树（创建、中序遍历、插入节点和删除节点操作） |
您所在的位置：网站首页 › 排序二叉树的有序序列 › JAVA实现二叉排序树（创建、中序遍历、插入节点和删除节点操作） |
JAVA实现二叉排序树（创建、中序遍历、插入节点和删除节点操作）
|
JAVA实现二叉排序树
二叉排序树的定义 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值； （3）左、右子树也分别为二叉排序树； 从上述定义可以看出，二叉排序树的定义本身就是依赖于递归思想的。 二叉排序树举例 二叉排序树的JAVA实现 1、首先定义树节点 package com.bean.sortedbinarytreedemo; public class TreeNode { E element; TreeNode parent; TreeNode leftChild; TreeNode rightChild; public TreeNode(E element, TreeNode parent) { this.element = element; this.parent = parent; } public TreeNode() { } public E getElement() { return element; } public void setElement(E element) { this.element = element; } public TreeNode getParent() { return parent; } public void setParent(TreeNode parent) { this.parent = parent; } public TreeNode getLeftChild() { return leftChild; } public void setLeftChild(TreeNode leftChild) { this.leftChild = leftChild; } public TreeNode getRightChild() { return rightChild; } public void setRightChild(TreeNode rightChild) { this.rightChild = rightChild; } }2、算法设计 package com.bean.sortedbinarytreedemo; import java.util.Iterator; import java.util.NoSuchElementException; public class BinarySortTree { // 根节点 private TreeNode root = null; // 树中元素个数 private int size = 0; //空构造方法 public BinarySortTree() { } //统计二叉树中的节点数 public int countSize() { return size; } //获得节点元素的值 public E getRoot() { return root == null ? null : root.element; } /** * 递归实现: 查找指定元素element是否在树中存在，如果查找失败确认其添加的位置,查找成功直接返回 * @param t 表示从此节点开始往下查找 * @param f 保存t的父节点 * @param p 若查找成功p指向此数据元素节点，否则返回查找路径上的最后一个节点 */ private boolean searchBST(TreeNode t, Object element, TreeNode f, TreeNode p) { if (t == null) { p = f; return false; } Comparable |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |