溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹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 {
/**
701. 二叉搜索樹中的插入操作
二叉樹分為前序插入,中序插入，后序插入
解決思路 1.利用迭代思想實現二叉樹的插入
*/
}
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;
}
}
/**
* Definition for a binary tree node.
* public 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 {
/*
二叉樹插入原理:
1.前序插入(根左右) 如果插入的樹大于根,數則往右側移動,與右側分支的根進行比較，然后重復前面的操作
*/
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;
}
//解法三:循環遍歷,
/**
*
* @param root
* @param val
* @return
*
* 解法思路：我們先通過一個循環找到能插入位置的父節點，
* 然后我們就對值與父節點的值進行比較,如果該值小于父節點的話我們就插入在父節點的左側
*/
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二叉樹中數據插入算法的示例分析”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
