杭州网站建设优化案例,wordpress新建页面无法选择模板,githup网站建设,想学动漫制作可以上什么学校一、二叉树基础
1.1 二叉排序树定义
二叉排序树#xff08;Binary Sort Tree#xff09;又称二叉查找(搜索)树#xff08;Binary Search Tree#xff09;。它是一颗空树#xff0c;或者具有下列性质#xff1a;
若它的左子树不为空#xff0c;则左子树上所有结点的值…一、二叉树基础
1.1 二叉排序树定义
二叉排序树Binary Sort Tree又称二叉查找(搜索)树Binary Search Tree。它是一颗空树或者具有下列性质
若它的左子树不为空则左子树上所有结点的值均小于它的根结点的值若它的右子树不为空则右子树上所有结点的值均大于它的根结点的值它的左、右子树分别为二叉排序树。
上述性质简称二叉排序树性质(BST性质)故二叉排序树实际上是满足BST性质的二叉树。
注意
当用线性表作为表的组织形式时可以有三种查找法。其中以二分查找效率最高。但由于二分查找要求表中结点按关键字有序且不能用链表作存储结构因此当表的插入或删除操作频繁时为维护表的有序性势必要移动表中很多结点。这种由移动结点引起的额外时间开销就会抵消二分查找的优点。也就是说二分查找只适用于静态查找表。若要对动态查找表进行高效率的查找可采用下二叉树或树作为表的组织形式。不妨将它们统称为树表。
1.2 特点
由BST性质可得
1 二叉排序树中任一结点x其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。
2 二叉排序树中各结点关键字是惟一的。
注意
实际应用中不能保证被查找的数据集中各元素的关键字互不相同所以可将二叉排序树定义中BST性质(1)里的小于改为大于等于或将BST性质(2)里的大于改为小于等于甚至可同时修改这两个性质。 3 按中序遍历该树所得到的中序序列是一个递增有序序列。
【例】下图所示的两棵树均是二叉排序树它们的中序序列均为有序序列234578。
2、二叉树操作
二叉树TreeNode节点定义
class TreeNode{public int data;public TreeNode left;public TreeNode right;TreeNode(int data){this.datadata;}
}2.1 二叉树的插入
2.1.1 递归实现
//添加节点递归模式
public static boolean AddTreeNode1(TreeNode root, int data){TreeNode treeNodenew TreeNode(data);//树为空if(rootnull){roottreeNode;return true;}//比根节点小插入到左子树if(root.datadata){if(root.leftnull){root.lefttreeNode;return true;}elsereturn AddTreeNode1(root.left, data);}else if(root.datadata){ //比根节点大插入到右子树if(root.rightnull){root.righttreeNode;return true;}elsereturn AddTreeNode1(root.right,data);}elsereturn false;
}2.1.2 非递归模式
//增加节点非递归模式
public static boolean AddTreeNode2(TreeNode root, int data){//树为空if(rootnull){rootnew TreeNode(data);return true;}TreeNode treeNodenew TreeNode(data);TreeNode currNoderoot;while(true){if(currNode.datadata){if(currNode.left!null)currNodecurrNode.left;else{currNode.lefttreeNode;return true;}}else if(currNode.datatreeNode.data){if(currNode.right!null)currNodecurrNode.right;else {currNode.righttreeNode;return true;}}elsereturn false;}
}2.2 二叉树的查找
public static boolean search(TreeNode root, int data){if(rootnull){return false;}else if(root.datadata){return true;}else if(root.datadata){return search(root.left,data);}else{return search(root.right,data);}
}2.3 二叉树的删除
删除可为BST问题最为复杂的一部分需要考虑一下要删除的节点的四种情况
该节点为叶子节点删除即可该节点只有左子树没有右子树删除后将该节点的左子树连接到该节点的父节点即可该节点只有右子树没有左子树删除后将该节点的右子树连接到该节点的父节点即可该节点既有左子树也有右子树这时候删除比较复杂可以分为两种情况 首先我们知道二叉排序树经过中序遍历后得到的是一个递增有序序列该节点的前一个即为直接前驱后一个为直接后继。我们要得到直接前驱和直接后继的节点。
方法一
得到该删除节点的左节点如果此左节点没有右节点则该左节点即为直接前驱左节点有右节点则一直沿最右侧右节点迭代下去最后面的那个即为直接前驱
方法二
得到该删除节点的右节点如果此右节点没有左节点则该右节点即为直接后继右节点有左节点则一直沿最左侧左节点迭代下去最后面的那个即为直接后继。
以上四种情况均要考虑要删除的节点为根节点root的情况。
代码实现如下 //删除public static boolean delete(TreeNode root, int data){//current为查找得到的节点TreeNode currentroot;//parent为时刻更新父节点TreeNode parentroot;//tempParent为同时存在左右子树的迭代临时父节点TreeNode tempParentroot;//isLeft记录current节点的左右属性boolean isLefttrue;while(current.data!data){parentcurrent;//到左子树查找if(current.datadata){isLefttrue;currentcurrent.left;}else if(current.datadata){ //到右子树查找isLeftfalse;currentcurrent.right;}//查不到返回falseif(currentnull)return false;}//第一种情况删除节点为叶节点if(current.leftnull current.rightnull){if(currentroot)rootnull;if(isLeft) {parent.left null;}else{parent.right null;}return true;}else if(current.rightnull){ //第二种情况删除节点只有左节点if(currentroot)rootcurrent.left;else if(isLeft)parent.leftcurrent.left;elseparent.rightcurrent.left;return true;}else if(current.leftnull){ //第三种情况删除节点只有右节点if(currentroot)rootcurrent.right;else if(isLeft)parent.leftcurrent.right;elseparent.rightcurrent.right;return true;}else{ //第四种情况删除节点均存在左节点和右节点if(currentroot){rootroot.left;}TreeNode tempNodecurrent.left;//没有左节点if(tempNode.rightnull){if(isLeft)parent.lefttempNode;elseparent.righttempNode;}else{ //存在左节点迭代到最右侧子节点即直接前驱while(tempNode.right!null){tempParenttempNode;tempNodetempNode.right;}if(isLeft){ //为左节点连接parent.lefttempNode;parent.left.leftcurrent.left;}else{ //为右节点连接parent.righttempNode;parent.right.leftcurrent.left;}//删除前驱节点连接if(tempNode.leftnull)tempParent.rightnull;elsetempParent.righttempNode.left;}return true;}}2.4 二叉树的遍历
//二叉树中序遍历
public static void midSort(TreeNode root){if(rootnull){return;}midSort(root.left);System.out.print(root.data );midSort(root.right);
}2.5 测试代码
public static void main(String[] args){int[] anew int[]{62,88,58,47,35,73,51,99,37,93};TreeNode rootnew TreeNode(a[0]);for(int i1; ia.length; i){AddTreeNode1(root, a[i]);}System.out.println(中序遍历结果为);midSort(root);System.out.println(47存在SearchTreeNode(root,47));AddTreeNode1(root,100);System.out.println(添加100后中序遍历结果为);midSort(root);System.out.println(添加100后100存在SearchTreeNode(root,100));
} 输出结果
中序遍历结果为
35 37 47 51 58 62 73 88 93 99 47存在true
添加100后中序遍历结果为
35 37 47 51 58 62 73 88 93 99 100 添加100后100存在true
删除100后中序遍历结果为
35 37 47 51 58 62 73 88 93 99 删除100后100存在false3、二叉排序树拓展
平衡二叉排序树https://blog.csdn.net/zhaohong_bo/article/details/90311112
