java二叉树的数据插入算法介绍
例题:
leetcode 第701题
二叉树插入数据
题目：
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
对于二叉树的遍历有三种方式
前序遍历：根左右 的顺序
中序遍历：左根右 的顺序
后序遍历：左右根 的顺序
二叉树插入数据的原理/思路是什么？
二叉树的左侧的数会比右侧的数小，所以我们用需要插入的数据和根节点的值比较大小，如果插入的数据大于根节点，那么根节点就转移到右侧的节点上,此时重复上面的操作即可完成插入。
我们读一下TreeNode代码段：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
很显然,二叉树之间是通过left,right来链接的,和ListNode的next非常的相似,只不过二叉树是双向链接,而链表则是单向。所以我们就需要获取到父节点，用父节点的left或right来链接插入的数。
那么我们如何获取到能正确插入该数据的节点呢？
1.我们可以通过循环移动节点的方式,来获取最后一个不为空的节点
//定义一个父级二叉树 用来记录上个操作的节点
TreeNode parent =root,cur=root;
while(cur!=null){
//如果p部位空的话,就和val比较来进行节点的移动
parent = cur; //记录上一个节点,用于最后的链接
cur = cur.val<val?cur.right:cur.left;//节点进行移动。
}
2.然后用最后一个不为空的节点的值与插入值进行比较插入即可,小的则插入左侧,大的则插入右侧。
代码实现
if(parent.val>val){
//如果父级的val是大于输入的val，那么插在左边
parent.left = new TreeNode(val);
}else{
//否则插在右边
parent.right = new TreeNode(val);
}
整体代码
if (root == null){
return new TreeNode(val);
}
//定义一个父级二叉树 用来记录上个操作的节点
TreeNode parent =root,cur=root;
while(cur!=null){
//如果p部位空的话,就和val比较来进行节点的移动
parent = cur; //记录上一个节点,用于最后的链接
cur = cur.val<val?cur.right:cur.left;//节点进行移动。
}
if(parent.val>val){
//如果父级的val是大于输入的val，那么插在左边
parent.left = new TreeNode(val);
}else{
//否则插在右边
parent.right = new TreeNode(val);
}
return root;
当然,因为节点的移动一直重复一个操作,我们可以用更简单的递归实现
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null){
return new TreeNode(val);
}
if(root.val<val){
//因为父节点的值小于插入值,则要进行节点的右移
root.right = insertIntoBST(root.right,val);
}else{
root.left = insertIntoBST(root.left,val);
}
return root;
}
全部代码
package JAVA算法.LeetCode;
public class t701 {
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
//当传入的根节点为空,则将传入的值设置为节点
if (root == null){
//如果tree为空的,那么就创建一个新的二叉并赋值
return new TreeNode(val);
}
if (root.val<val){
//当当前的值是大于左侧的值，则往右侧移动
root.right=insertIntoBST(root.right,val);
}else{
//反之
root.left=insertIntoBST(root.left,val);
}
return root;
}
//解法2：循环判断
public TreeNode insertIntoBST2(TreeNode root, int val) {
if (root == null){
return new TreeNode(val);
}
TreeNode parent=root,p=root;
while(true){
if (p!=null){
parent = p; //记录上个节点
p = p.val>val?p.left:p.right;
}else{
//当p为null了,则已经找到位置了,现在则需要将值进行插入
if (parent.val>val){
parent.left = new TreeNode(val);
}else{
parent.right = new TreeNode(val);
}
break;
}
}
return root;
}
//解法三:循环遍历,
public TreeNode insertBST3(TreeNode root,int val){
if (root == null){
return new TreeNode(val);
}
//定义一个父级二叉树 用来记录上个操作的节点
TreeNode parent =root,p=root;
while(p!=null){
//如果p部位空的话,就和val比较来进行节点的移动
parent = p; //记录上一个节点,用于最后的链接
p = p.val<val?p.right:p.left;//节点进行移动。
}
if(parent.val>val){
//如果父级的val是大于输入的val，那么插在左边
parent.left = new TreeNode(val);
}else{
//否则插在右边
parent.right = new TreeNode(val);
}
return root;
}
}
到此这篇关于java二叉树的数据插入算法介绍的文章就介绍到这了,更多相关java二叉树内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
