2023年6月22日发(作者：)

JAVA实现⼆叉排序树（创建、中序遍历、插⼊节点和删除节点操作）JAVA实现⼆叉排序树⼆叉排序树的定义⼆叉排序树或者是⼀棵空树，或者是具有下列性质的⼆叉树：

（1）若左⼦树不空，则左⼦树上所有结点的值均⼩于或等于它的根结点的值；

（2）若右⼦树不空，则右⼦树上所有结点的值均⼤于或等于它的根结点的值；

（3）左、右⼦树也分别为⼆叉排序树；从上述定义可以看出，⼆叉排序树的定义本⾝就是依赖于递归思想的。⼆叉排序树举例⼆叉排序树的JAVA实现1、⾸先定义树节点package binarytreedemo;public class TreeNode { E element;

TreeNode parent;

TreeNode leftChild;

TreeNode rightChild;

public TreeNode(E element, TreeNode parent) {

t = element;

= parent;

}

public TreeNode() {

} public E getElement() { return element; } public void setElement(E element) { t = element; } public TreeNode getParent() { return parent; } public void setParent(TreeNode parent) { = parent; } public TreeNode getLeftChild() { return leftChild; } public void setLeftChild(TreeNode leftChild) { ild = leftChild; } public TreeNode getRightChild() { return rightChild; } public void setRightChild(TreeNode rightChild) { hild = rightChild; }

}2、算法设计package binarytreedemo;import or;import ElementException;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 : t;

}

/**

* 递归实现: 查找指定元素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 = eTo(t);

if (cmp < 0) {

return searchBST(ild, element, t, p);

} else if (cmp > 0) {

return searchBST(hild, 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 = eTo(t);

pp = parent;

if (cmp < 0) {

parent = ild;

} else if (cmp > 0) {

parent = hild;

} 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 = eTo((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 (ild != null && hild != null) { // 如果p左右⼦树都不为空，找到其直接后继，替换p

TreeNode s = successor(p);

t = t;

p = s;

}

TreeNode replacement = (ild != null ? ild : hild);

if (replacement != null) { // 如果其左右⼦树有其⼀不为空

= ;

if ( == null) // 如果p为root节点

root = replacement;

else if (p == ild) // 如果p是左孩⼦

ild = replacement;

else

hild = replacement; // 如果p是右孩⼦

ild = hild = = null; // p的指针清空

} else if ( == null) { // 如果全树只有⼀个节点

root = null;

} else { // 左右⼦树都为空,p为叶⼦节点 } else { // 左右⼦树都为空,p为叶⼦节点

if ( != null) {

if (p == ild)

ild = null;

else if (p == hild)

hild = null;

= null;

}

}

}

/**

* 返回以中序遍历⽅式遍历树时，t的直接后继

*/

static TreeNode successor(TreeNode t) {

if (t == null)

return null;

else if (hild != null) {

TreeNode p = hild; // 往右，然后向左直到尽头

while (ild != null)

p = ild;

return p;

} else { // rightChild为空，如果t是p的左⼦树，则p为t的直接后继

TreeNode p = ;

TreeNode ch = t;

while (p != null && ch == hild) {

ch = p; // 如果t是p的右⼦树，则继续向上搜索其直接后继

p = ;

}

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 (ild != null) {

s = ild; // 找到中序遍历的第⼀个元素

}

}

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); next = successor(e);

lastReturned = e;

return t;

}

@Override

public void remove() {

if (lastReturned == null)

throw new IllegalStateException();

if (ild != null && hild != null)

next = lastReturned;

deleteTreeNode(lastReturned);

lastReturned = null;

}

}

// 测试代码 public static void main(String[] args) {

BinarySortTree tree = new BinarySortTree();

(62);

(15);

(68);

(12);

(46);

(65);

(79);

(35);

(57);

n("root=" + t());

n("⼆叉树的中序遍历："); Iterator it = r();

while (t()) {

(()+"t");

}

n(); n(ize());

}

}运⾏结果：root=62

⼆叉树的中序遍历：

12 15 35 46 57 62 65 68 79

9插⼊⼀个节点元素：53 的情况在main⽅法中 加⼊下⾯的代码 // 省略前⾯的代码 n("插⼊⼀个节点 53"); (53); n("root=" + t());

n("⼆叉树的中序遍历："); Iterator it2 = r();

while (t()) {

(()+"t");

}

n(); n(ize());

// 省略后⾯的代码运⾏结果：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⽅法中 加⼊下⾯的代码 // 省略前⾯的代码 n("插⼊⼀个节点 13"); (13); n("root=" + t());

n("⼆叉树的中序遍历："); Iterator it3 = r();

while (t()) {

(()+"t");

}

n(); n(ize());

// 省略后⾯的代码运⾏结果为：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被插⼊到了正确的位置。（完）