【Java】高级数据结构算法 -- BST树( 二 ) _节点

文章插图

/*** BST树的实现* @param */class BST>{private BSTNode root; // 指向根节点//BST树的初始化public BST() {this.root = null;}

插入（非递归、递归）

/*** BST树的非递归插入操作* @param data*/public void non_insert(T data){// 1.判断如果root是null，如果root是null，直接生成根节点，让root指向，结束if(root == null){this.root = new BSTNode<>(data, null, null);return;}// 2.如果root不为空，从根节点开始搜索一个合适的位置，放新节点BSTNode cur = this.root;BSTNode parent = null; // this.rootwhile(cur != null){if(cur.getData().compareTo(data) > 0){parent = cur;cur = cur.getLeft();} else if(cur.getData().compareTo(data) < 0){parent = cur;cur = cur.getRight();} else {return;}}// 3.生成新节点，把节点的地址，写入父节点相应的地址域if(parent.getData().compareTo(data) > 0){parent.setLeft(new BSTNode(data, null, null));} else {parent.setRight(new BSTNode(data, null, null));}}

/*** BST的递归插入函数接口* @param data*/public void insert(T data){this.root = insert (this.root,data);}//递归插入的具体实现函数private BSTNode insert(BSTNode root, T data) {if(root == null){return new BSTNode<> (data,null,null);}if(root.getData ().compareTo (data) > 0){root.setLeft ((insert (root.getLeft (),data)));}else if(root.getData ().compareTo (data) < 0){root.setRight (insert (root.getLeft (),data));}else {;}return root;}

删除（递归、非递归）

/*** 非递归实现BST树的删除操作* @param data*/public void non_remove(T data){if(this.root == null){return;}// 1. 先搜索BST树，找到待删除的节点BSTNode cur = this.root;BSTNode parent = null;while(cur != null){if(cur.getData().compareTo(data) > 0){parent = cur;cur = cur.getLeft();} else if(cur.getData().compareTo(data) < 0){parent = cur;cur = cur.getRight();} else {break;}}if(cur == null){ // 表示BST树中没有值为data的节点return;}// 2. 判断删除节点是否有两个孩子，如果有，用前驱的值代替，直接删除前驱if(cur.getLeft() != null && cur.getRight() != null){// 找前驱节点，用前驱节点的值代替待删节点的值，然后直接删除前驱节点curBSTNode old = cur;parent = cur;cur = cur.getLeft();while(cur.getRight() != null){parent = cur;cur = cur.getRight();}old.setData(cur.getData()); // 前驱节点的值代替待删节点的值}// 3. 删除有一个孩子的节点，或者没有孩子的节点（看作有一个孩子，孩子是null）BSTNode child = cur.getLeft();if(child == null){child = cur.getRight();}if(parent == null){ // 删除的就是根节点this.root = child;} else {if(parent.getLeft() == cur){parent.setLeft(child);} else {parent.setRight(child);}}}

/*** BST的递归删除函数接口* @param data*/public void remove(T data){this.root = remove (this.root,data);}/*** 递归删除的具体实现函数* @param root* @param data* @return*/private BSTNode remove(BSTNode root, T data) {if(root == null){return null;}if(root.getData().compareTo(data) > 0){root.setLeft(remove(root.getLeft(), data));} else if(root.getData().compareTo(data) < 0){root.setRight(remove(root.getRight(), data));} else {if(root.getLeft() != null && root.getRight() != null){BSTNode pre = root;pre = pre.getLeft();while(pre.getRight() != null){pre = pre.getRight();}root.setData(pre.getData());root.setLeft(remove(root.getLeft(), pre.getData()));} else {if(root.getLeft() != null){return root.getLeft();} else if(root.getRight() != null){return root.getRight();} else {return null;}}}return root;}

查询（递归、非递归）
【【Java】高级数据结构算法 -- BST树】