java二叉樹(shù)的數(shù)據(jù)插入算法介紹

更新時(shí)間：2021年12月20日 15:09:45 作者：Code丨Monkey

大家好，本篇文章主要講的是java二叉樹(shù)的數(shù)據(jù)插入算法介紹，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽

例題:

leetcode 第701題

題目：

給定二叉搜索樹(shù)（BST）的根節(jié)點(diǎn)和要插入樹(shù)中的值，將值插入二叉搜索樹(shù)。返回插入后二叉搜索樹(shù)的根節(jié)點(diǎn)。輸入數(shù)據(jù) 保證，新值和原始二叉搜索樹(shù)中的任意節(jié)點(diǎn)值都不同。

對(duì)于二叉樹(shù)的遍歷有三種方式

前序遍歷：根左右的順序
中序遍歷：左根右的順序
后序遍歷：左右根的順序

二叉樹(shù)插入數(shù)據(jù)的原理/思路是什么？

二叉樹(shù)的左側(cè)的數(shù)會(huì)比右側(cè)的數(shù)小，所以我們用需要插入的數(shù)據(jù)和根節(jié)點(diǎn)的值比較大小，如果插入的數(shù)據(jù)大于根節(jié)點(diǎn)，那么根節(jié)點(diǎn)就轉(zhuǎn)移到右側(cè)的節(jié)點(diǎn)上,此時(shí)重復(fù)上面的操作即可完成插入。

我們讀一下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;
      }
}

很顯然,二叉樹(shù)之間是通過(guò)left,right來(lái)鏈接的,和ListNode的next非常的相似,只不過(guò)二叉樹(shù)是雙向鏈接,而鏈表則是單向。所以我們就需要獲取到父節(jié)點(diǎn)，用父節(jié)點(diǎn)的left或right來(lái)鏈接插入的數(shù)。

那么我們?nèi)绾潍@取到能正確插入該數(shù)據(jù)的節(jié)點(diǎn)呢？

1.我們可以通過(guò)循環(huán)移動(dòng)節(jié)點(diǎn)的方式,來(lái)獲取最后一個(gè)不為空的節(jié)點(diǎn)

 //定義一個(gè)父級(jí)二叉樹(shù) 用來(lái)記錄上個(gè)操作的節(jié)點(diǎn)
        TreeNode parent =root,cur=root;
        while(cur!=null){
            //如果p部位空的話,就和val比較來(lái)進(jìn)行節(jié)點(diǎn)的移動(dòng)
            parent = cur; //記錄上一個(gè)節(jié)點(diǎn),用于最后的鏈接
            cur = cur.val<val?cur.right:cur.left;//節(jié)點(diǎn)進(jìn)行移動(dòng)。
        }

2.然后用最后一個(gè)不為空的節(jié)點(diǎn)的值與插入值進(jìn)行比較插入即可,小的則插入左側(cè),大的則插入右側(cè)。

代碼實(shí)現(xiàn)

if(parent.val>val){
            //如果父級(jí)的val是大于輸入的val，那么插在左邊
            parent.left = new TreeNode(val);
        }else{
            //否則插在右邊
            parent.right = new TreeNode(val);
        }

整體代碼

 if (root == null){
            return new TreeNode(val);
        }
        //定義一個(gè)父級(jí)二叉樹(shù) 用來(lái)記錄上個(gè)操作的節(jié)點(diǎn)
        TreeNode parent =root,cur=root;
        while(cur!=null){
            //如果p部位空的話,就和val比較來(lái)進(jìn)行節(jié)點(diǎn)的移動(dòng)
            parent = cur; //記錄上一個(gè)節(jié)點(diǎn),用于最后的鏈接
            cur = cur.val<val?cur.right:cur.left;//節(jié)點(diǎn)進(jìn)行移動(dòng)。
        }
        if(parent.val>val){
            //如果父級(jí)的val是大于輸入的val，那么插在左邊
            parent.left = new TreeNode(val);
        }else{
            //否則插在右邊
            parent.right = new TreeNode(val);
        }
        return root;

當(dāng)然,因?yàn)楣?jié)點(diǎn)的移動(dòng)一直重復(fù)一個(gè)操作,我們可以用更簡(jiǎn)單的遞歸實(shí)現(xiàn)

 public TreeNode insertIntoBST(TreeNode root, int val) {
          if (root == null){
            return new TreeNode(val);
          }
          if(root.val<val){
              //因?yàn)楦腹?jié)點(diǎn)的值小于插入值,則要進(jìn)行節(jié)點(diǎn)的右移
              root.right = insertIntoBST(root.right,val);
          }else{
              root.left = insertIntoBST(root.left,val);
          }
        return root;
    }

全部代碼

package JAVA算法.LeetCode;

public class t701 {
    /**
    701. 二叉搜索樹(shù)中的插入操作
    二叉樹(shù)分為前序插入,中序插入，后序插入
    解決思路 1.利用迭代思想實(shí)現(xiàn)二叉樹(shù)的插入
     */

}


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 {
    /*
        二叉樹(shù)插入原理:
        1.前序插入(根左右) 如果插入的樹(shù)大于根,數(shù)則往右側(cè)移動(dòng),與右側(cè)分支的根進(jìn)行比較，然后重復(fù)前面的操作
        */
    public TreeNode insertIntoBST(TreeNode root, int val) {
        //當(dāng)傳入的根節(jié)點(diǎn)為空,則將傳入的值設(shè)置為節(jié)點(diǎn)
        if (root == null){
            //如果tree為空的,那么就創(chuàng)建一個(gè)新的二叉并賦值
            return new TreeNode(val);
        }

        if (root.val<val){
            //當(dāng)當(dāng)前的值是大于左側(cè)的值，則往右側(cè)移動(dòng)
            root.right=insertIntoBST(root.right,val);
        }else{
            //反之
            root.left=insertIntoBST(root.left,val);
        }
        return root;
    }


    //解法2：循環(huán)判斷
    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; //記錄上個(gè)節(jié)點(diǎn)
                p = p.val>val?p.left:p.right;
            }else{
                //當(dāng)p為null了,則已經(jīng)找到位置了,現(xiàn)在則需要將值進(jìn)行插入
                if (parent.val>val){
                    parent.left = new TreeNode(val);
                }else{
                    parent.right = new TreeNode(val);
                }
                break;
            }

        }
        return root;
    }
    //解法三:循環(huán)遍歷,

    /**
     *
     * @param root
     * @param val
     * @return
     *
     * 解法思路：我們先通過(guò)一個(gè)循環(huán)找到能插入位置的父節(jié)點(diǎn)，
     * 然后我們就對(duì)值與父節(jié)點(diǎn)的值進(jìn)行比較,如果該值小于父節(jié)點(diǎn)的話我們就插入在父節(jié)點(diǎn)的左側(cè)
     */
    public TreeNode insertBST3(TreeNode root,int val){
        if (root == null){
            return new TreeNode(val);
        }
        //定義一個(gè)父級(jí)二叉樹(shù) 用來(lái)記錄上個(gè)操作的節(jié)點(diǎn)
        TreeNode parent =root,p=root;
        while(p!=null){
            //如果p部位空的話,就和val比較來(lái)進(jìn)行節(jié)點(diǎn)的移動(dòng)
            parent = p; //記錄上一個(gè)節(jié)點(diǎn),用于最后的鏈接
            p = p.val<val?p.right:p.left;//節(jié)點(diǎn)進(jìn)行移動(dòng)。
        }
        if(parent.val>val){
            //如果父級(jí)的val是大于輸入的val，那么插在左邊
            parent.left = new TreeNode(val);
        }else{
            //否則插在右邊
            parent.right = new TreeNode(val);
        }

        return root;
    }


}

到此這篇關(guān)于java二叉樹(shù)的數(shù)據(jù)插入算法介紹的文章就介紹到這了,更多相關(guān)java二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: