JAVA实现二叉排序树（创建、中序遍历、插入节点和删除节点操作）
本文共 7510 字，大约阅读时间需要 25 分钟。
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 e = (Comparable ) element; int cmp = e.compareTo(t.element); if (cmp < 0) { return searchBST(t.leftChild, element, t, p); } else if (cmp > 0) { return searchBST(t.rightChild, element, t, p); } else { p = t; return true; } } /** * 非递归实现 */ private boolean searchBST(Object element, TreeNode [] p) { Comparable e = (Comparable ) element; TreeNode parent = root; TreeNode pp = null; // 保存parent父节点 while (parent != null) { int cmp = e.compareTo(parent.element); pp = parent; if (cmp < 0) { parent = parent.leftChild; } else if (cmp > 0) { parent = parent.rightChild; } else { p[0] = parent; return true; } } p[0] = pp; return false; } /** * 首先查找二叉排序树，如果找不到指定元素 则插入到二叉树中 */ public boolean add(E element) { TreeNode t = root; if (t == null) { // 如果根节点为空 root = new TreeNode (element, null); size = 1; return false; } Comparable e = (Comparable ) element; TreeNode[] p = new TreeNode[1]; if (!searchBST(element, p)) { // 查找失败，插入元素 TreeNode s = new TreeNode (element, p[0]); int cmp = e.compareTo((E) p[0].element); if (cmp < 0) { p[0].leftChild = s; } if (cmp > 0) { p[0].rightChild = s; } size++; return true; } return false; } /** * 移除节点，同时调整二叉树使之为二叉排序树 实现原理： * 假设要删除的节点为p，其父节点为f，而p是f的左节点 分三种情况讨论: * 1.若p为叶子节点，直接删除 * 2.若p有只有一个左孩子或者一个右孩子，则删除p，使PL或者PR为f的左子树 * 3.若p的左右子树均不为空，由二叉排序树的特点可知在删除p前，中序遍历此二叉树 * 可以得到一个有序序列，在删去p后为了保持其他元素的相对位置不变，可以这样做： * 令p的直接前驱(或直接后继)替代p，然后删除其直接前驱或直接后继。其直接前驱可由 中序遍历的特点获得 */ public boolean remove(Object o) { TreeNode [] p = new TreeNode[1]; if (searchBST(o, p)) { deleteTreeNode(p[0]); // 查找成功，删除元素 return true; } return false; } private void deleteTreeNode(TreeNode p) { size--; if (p.leftChild != null && p.rightChild != null) { // 如果p左右子树都不为空，找到其直接后继，替换p TreeNode s = successor(p); p.element = s.element; p = s; } TreeNode replacement = (p.leftChild != null ? p.leftChild : p.rightChild); if (replacement != null) { // 如果其左右子树有其一不为空 replacement.parent = p.parent; if (p.parent == null) // 如果p为root节点 root = replacement; else if (p == p.parent.leftChild) // 如果p是左孩子 p.parent.leftChild = replacement; else p.parent.rightChild = replacement; // 如果p是右孩子 p.leftChild = p.rightChild = p.parent = null; // p的指针清空 } else if (p.parent == null) { // 如果全树只有一个节点 root = null; } else { // 左右子树都为空,p为叶子节点 if (p.parent != null) { if (p == p.parent.leftChild) p.parent.leftChild = null; else if (p == p.parent.rightChild) p.parent.rightChild = null; p.parent = null; } } } /** * 返回以中序遍历方式遍历树时，t的直接后继 */ static TreeNode successor(TreeNode t) { if (t == null) return null; else if (t.rightChild != null) { TreeNode p = t.rightChild; // 往右，然后向左直到尽头 while (p.leftChild != null) p = p.leftChild; return p; } else { // rightChild为空，如果t是p的左子树，则p为t的直接后继 TreeNode p = t.parent; TreeNode ch = t; while (p != null && ch == p.rightChild) { ch = p; // 如果t是p的右子树，则继续向上搜索其直接后继 p = p.parent; } return p; } } public Iterator itrator() { return new BinarySortIterator(); } /** * 返回中序遍历此树的迭代器 */ private class BinarySortIterator implements Iterator { TreeNode next; TreeNode lastReturned; public BinarySortIterator() { TreeNode s = root; if (s != null) { while (s.leftChild != null) { s = s.leftChild; // 找到中序遍历的第一个元素 } } next = s; // 赋给next } @Override public boolean hasNext() { return next != null; } @Override public E next() { TreeNode e = next; if (e == null) throw new NoSuchElementException(); next = successor(e); lastReturned = e; return e.element; } @Override public void remove() { if (lastReturned == null) throw new IllegalStateException(); if (lastReturned.leftChild != null && lastReturned.rightChild != null) next = lastReturned; deleteTreeNode(lastReturned); lastReturned = null; } } // 测试代码 public static void main(String[] args) { BinarySortTree tree = new BinarySortTree (); tree.add(62); tree.add(15); tree.add(68); tree.add(12); tree.add(46); tree.add(65); tree.add(79); tree.add(35); tree.add(57); System.out.println("root=" + tree.getRoot()); System.out.println("二叉树的中序遍历："); Iterator it = tree.itrator(); while (it.hasNext()) { System.out.print(it.next()+"\t"); } System.out.println(); System.out.println(tree.countSize()); } }
运行结果：
root=62
二叉树的中序遍历： 12 15 35 46 57 62 65 68 79 9插入一个节点元素：53 的情况
在main方法中 加入下面的代码
// 省略前面的代码 System.out.println("插入一个节点 53"); tree.add(53); System.out.println("root=" + tree.getRoot()); System.out.println("二叉树的中序遍历："); Iterator it2 = tree.itrator(); while (it2.hasNext()) { System.out.print(it2.next()+"\t"); } System.out.println(); System.out.println(tree.countSize()); // 省略后面的代码 运行结果：
root=62
二叉树的中序遍历： 12 15 35 46 57 62 65 68 79 9 插入一个节点 53 root=62 二叉树的中序遍历： 12 15 35 46 53 57 62 65 68 79 10通过分析插入节点之后二叉排序树的遍历结果得到，节点53被插入到了正确的位置。
再次插入一个节点元素：13
树形调整为：
在main方法中 加入下面的代码
// 省略前面的代码 System.out.println("插入一个节点 13"); tree.add(13); System.out.println("root=" + tree.getRoot()); System.out.println("二叉树的中序遍历："); Iterator it3 = tree.itrator(); while (it3.hasNext()) { System.out.print(it3.next()+"\t"); } System.out.println(); System.out.println(tree.countSize()); // 省略后面的代码 运行结果为：
root=62
二叉树的中序遍历： 12 15 35 46 57 62 65 68 79 9 插入一个节点 53 root=62 二叉树的中序遍历： 12 15 35 46 53 57 62 65 68 79 10 插入一个节点 13 root=62 二叉树的中序遍历： 12 13 15 35 46 53 57 62 65 68 79 11通过分析插入节点之后二叉排序树的遍历结果得到，节点13被插入到了正确的位置。
（完）
你可能感兴趣的文章
No.182 - LeetCode1325 - C指针的魅力
查看>>
mysql:sql create database新建utf8mb4 数据库
查看>>
mysql:sql alter database修改数据库字符集
查看>>
mysql:sql drop table (删除表)
查看>>
mysql:sql truncate (清除表数据)
查看>>
scrapy:xpath string(.)非常注意问题
查看>>
yuv to rgb 转换失败呀。天呀。谁来帮帮我呀。
查看>>
yuv420 format
查看>>
YUV420只绘制Y通道
查看>>
yuv420 还原为RGB图像
查看>>
LED恒流驱动芯片
查看>>
驱动TFT要SDRAM做为显示缓存
查看>>
使用file查看可执行文件的平台性，x86 or arm ?
查看>>
qt5 everywhere 编译summary
查看>>
qt5 everywhere编译完成后，找不到qmake
查看>>
arm-linux开机读取硬件时钟，设置系统时钟。
查看>>
交叉编译在x86上调试好的qt程序
查看>>
qt 创建异形窗体
查看>>
可重入函数与不可重入函数
查看>>
简单Linux C线程池
查看>>