万年网站建设,商业招商网站,wordpress提工单,黄骅市有什么好玩的地方目录
1.概念
2.性质 3.二叉搜索树的操作
1.查找
2.插入
3.删除(难点) 1.概念
二叉搜索树又称二叉排序树.利用中序遍历它就是一个有顺序的一组数.
2.性质
1.若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
2.若它的右子树不为空,则右子树上所有节点的值都…目录
1.概念
2.性质 3.二叉搜索树的操作
1.查找
2.插入
3.删除(难点) 1.概念
二叉搜索树又称二叉排序树.利用中序遍历它就是一个有顺序的一组数.
2.性质
1.若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
2.若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
3.它的左右子树也分别为二叉搜索树 3.二叉搜索树的操作
1.查找
根据搜索树的性质来进行查找操作.
/*** 查找* param root* param val*/public TreeNode find(TreeNode root, int val) throws FindException{if (root null) {throw new FindException(root 为空);}while (root ! null) {if (root.val val) {return root;} else if (root.val val) {root root.right;} else {root root.left;}}return null;}
2.插入
每次插入进去的值都在叶子节点.
如果插入的是相同的数那么直接return. (在搜索树中插入相同的数没有意义)
/*** 插入* param root* param val* return*/public TreeNode insert(TreeNode root, int val) {if (root null) {root new TreeNode(val);return root;}TreeNode cur root;TreeNode parent null;while (cur ! null) {parent cur;if (cur.val val) {cur cur.right;} else {cur cur.left;}}if (parent.val val) {parent.right new TreeNode(val);} else {parent.left new TreeNode(val);}return root;}
3.删除(难点)
对于删除我们要去判断3种情况 : 假设要删除的节点是cur
一 . cur.left null 在这个前提下 还有三种情况: 1 . cur 是 root , root cur.right; 2 . cur不是root, cur是parent.left ; parent.left cur.right; 3 . cur不是root, cur是parent.right; parent.right cur.right; 二 . cur.right null 在这个前提下 还有三种情况: 1 . cur 是 root , root cur.left; 2 . cur不是root, cur是parent.left ; parent.left cur.left; 3 . cur不是root, cur是parent.right; parent.right cur.left; 三 (重). cur 的左右都不为空 : 思路 : 假设要被删除的是cur , 我们去找到cur右树中最小的那个节点 . 把它的val值跟cur.val交换.
交换之后我们的任务就是去删除交换后的那个节点(之前右树中最小的值).
但是这样做的话还有一个问题 : 在我们去删被交换后的那个节点时,它的左子树肯定是空的.
比如是这样 :
第一种情况 : 第二种情况 : 结合以上两种情况 : 我们就要去判断parent.left del 还是 parent.right del 代码实现 :
public class BinarySearchTree {static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val val;}}/*** 查找* param root* param val*/public TreeNode find(TreeNode root, int val) throws FindException{if (root null) {throw new FindException(root 为空);}while (root ! null) {if (root.val val) {return root;} else if (root.val val) {root root.right;} else {root root.left;}}return null;}/*** 插入* param root* param val* return*/public TreeNode insert(TreeNode root, int val) {if (root null) {root new TreeNode(val);return root;}TreeNode cur root;TreeNode parent null;while (cur ! null) {parent cur;if (cur.val val) {cur cur.right;} else {cur cur.left;}}if (parent.val val) {parent.right new TreeNode(val);} else {parent.left new TreeNode(val);}return root;}//中序遍历public void inorder(TreeNode root) {if (root null) {return;}inorder(root.left);System.out.print(root.val );inorder(root.right);}/*** 删除* param root* param val*/public void remove(TreeNode root, int val) {TreeNode cur root;if (cur null) {throw new RootNullException(root 为空);}TreeNode parent null;while (cur ! null) {if (cur.val val) {del(cur,parent,root);break;} else if (cur.val val) {parent cur;cur cur.right;} else {parent cur;cur cur.left;}}}//删除cur节点public void del(TreeNode cur, TreeNode parent, TreeNode root) {if (cur.left null) {if (cur root) {root root.right;} else if (parent.right cur) {parent.right cur.right;} else {parent.left cur.right;}} else if (cur.right null) {if (cur root) {root root.left;} else if (parent.right cur) {parent.right cur.left;} else {parent.left cur.left;}} else {//程序到这 就是cur的左右都不为空TreeNode del cur.right;parent cur;while (del.left ! null) {parent del;del del.left;}cur.val del.val;if (parent.right del) {parent.right del.right;} else {parent.left del.right;}}}
}以上就是关于搜索树的一些基本操作.
有任何问题可以私信我!
