Java数据结构与算法(4):二叉查找树
发布时间:2020-12-15 07:18:58 所属栏目:Java 来源:网络整理
导读:一、二叉查找树定义 二叉树每个节点都不能有多于两个的儿子。二叉查找树是特殊的二叉树,对于树中的每个节点X,它的左子树中的所有项的值小于X中的项,而它的右子树中所有项的值大于X中的项。 二叉查找树节点的定义: private static class BinaryNodeT { T
一、二叉查找树定义二叉树每个节点都不能有多于两个的儿子。二叉查找树是特殊的二叉树,对于树中的每个节点X,它的左子树中的所有项的值小于X中的项,而它的右子树中所有项的值大于X中的项。 二叉查找树节点的定义: private static class BinaryNode<T> { T element; // 节点的值 BinaryNode<T> left; // 左子节点 BinaryNode<T> right; // 右子节点 public BinaryNode(T element) { this(element,null,null); } public BinaryNode(T element,BinaryNode<T> left,BinaryNode<T> right) { this.element = element; this.left = left; this.right = right; } } 二、树的遍历树的三种遍历方式:前序遍历、中序遍历、后序遍历。这里的前中后是相对于根节点而言的:
对于下面这样一棵树,不同的遍历方式结果如下: 前序遍历:ABDGHCEIF private void preOrder(BinaryNode<T> root) { if (root == null) { return; } System.out.printf("%d ",root.element); preOrder(root.left); preOrder(root.right); } 中序遍历:GDHBAEICF private void inOrder(BinaryNode<T> root) { if (root == null) { return; } inOrder(root.left); System.out.printf("%d ",root.element); inOrder(root.right); } 后序遍历:GHDBIEFCA private void postOrder(BinaryNode<T> root) { if (root == null) { return; } postOrder(root.left); postOrder(root.right); System.out.printf("%d ",root.element); } 三、二叉查找树的基本操作3.1 contains方法/** * 判断树t中是否存在含有项x的节点 * * @param x 值 * @param t 以t为根节点的一棵树 * @return */ private boolean contains(T x,BinaryNode<T> t) { if (t == null) { return false; } int compareResult = x.compareTo(t.element); if (compareResult < 0) { return contains(x,t.left); } else if (compareResult > 0) { return contains(x,t.right); } else { return true; } } public boolean contains(T x) { return contains(x,root); } 3.2 find方法/** * 查找树t中值为x的节点 * @param x * @param t * @return */ private BinaryNode<T> find(T x,BinaryNode<T> t) { if (t == null) { return t; } int compareResult = x.compareTo(t.element); if (compareResult < 0) { return find(x,t.left); } else if (compareResult > 0) { return find(x,t.right); } else { return t; } } public BinaryNode<T> find(T x) { return find(x,root); } 3.3 最大值与最小值查找树中最大值的节点 private BinaryNode<T> findMax(BinaryNode<T> t) { if (t == null) { return null; } while (t.right != null) { t = t.right; } return t; } public BinaryNode<T> findMax() { return findMax(root); } 查找树中最小值的节点 private BinaryNode<T> findMin(BinaryNode<T> t) { if (t == null) { return null; } while (t.left != null) { t = t.left; } return t; } public BinaryNode<T> findMin() { return findMin(root); } 3.4 insert方法private BinaryNode<T> insert(T x,BinaryNode<T> t) { if (t == null) { return new BinaryNode<>(x,null); } int compareResult = x.compareTo(t.element); if (compareResult < 0) { t.left = insert(x,t.left); } else if (compareResult > 0) { t.right = insert(x,t.right); } else { // 出现重复值,忽略不处理 } return t; } public void insert(T x) { root = insert(x,root); } 3.5 remove方法
public void remove(T x) { root = remove(x,root); } private BinaryNode<T> remove(T x,BinaryNode<T> t) { if (t == null) { return t; } int compareResult = x.compareTo(t.element); if (compareResult < 0) { t.left = remove(x,t.left); } else if (compareResult > 0) { t.right = remove(x,t.right); } else if (t.left != null && t.right != null) { t.element = findMin(t.right).element; t.right = remove(t.element,t.right); } else { t = (t.left != null) ? t.left : t.right; } return t; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |