java二叉树中数据插入算法的示例分析

这篇文章主要介绍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来链接插入的数。

那么我们如何获取到能正确插入该数据的节点呢？

我们可以通过循环移动节点的方式,来获取最后一个不为空的节点

 //定义一个父级二叉树 用来记录上个操作的节点        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);        }

整体代码

 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二叉树中数据插入算法的示例分析”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注编程网精选频道！