快捷導(dǎo)航

java數(shù)據(jù)結(jié)構(gòu)之搜索二叉樹

更新時(shí)間：2022年01月11日 08:05:45 作者：zhouzhouandliuliu

這篇文章主要為大家詳細(xì)介紹了java數(shù)據(jù)結(jié)構(gòu)之搜索二叉樹，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

本文實(shí)例為大家分享了java數(shù)據(jù)結(jié)構(gòu)之搜索二叉樹的具體代碼，供大家參考，具體內(nèi)容如下

搜索二叉樹的定義是：在一個(gè)二叉樹上，左節(jié)點(diǎn)一定比父節(jié)點(diǎn)小，右節(jié)點(diǎn)一定比父節(jié)點(diǎn)大，其他定義跟二叉樹相同。

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

public class node {
? ? int data;
? ? public node left, right=null;
?
? ? public node(int data) {
? ? ? ? this.data = data;
?
? ? }
?
? ? public node(int data, node left, node right) {
? ? ? ? this.data = data;
? ? ? ? this.right = right;
? ? ? ? this.left = left;
? ? }
? ? //二叉搜索樹
? ? public static void insert(node root, node node) {
?
? ? ? ? if (root.data >= node.data) {
?
? ? ? ? ? ? if (root.right != null) {
? ? ? ? ? ? ? ? insert(root.right, node);
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? root.right=node;
? ? ? ? ? ? }
?
? ? ? ? } else {
?
? ? ? ? ? ? if (root.left != null) {
? ? ? ? ? ? ? ? insert(root.left,node);
? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? root.left=node;
? ? ? ? ? ? }
? ? ? ? }
?
? ? }
?
? ? //前序遍歷
? ? public static void before(node root) {
? ? ? ? if (root == null) {
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? System.out.println("data:" + root.data);
? ? ? ? before(root.left);
? ? ? ? before(root.right);
? ? }
?
? ? //中序遍歷
? ? public static void mid(node root) {
? ? ? ? if (root == null) {
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? mid(root.left);
? ? ? ? System.out.println("data:" + root.data);
? ? ? ? mid(root.right);
? ? }
?
? ? //后序遍歷
? ? public static void after(node root) {
? ? ? ? if (root == null) {
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? after(root.left);
? ? ? ? after(root.right);
? ? ? ? System.out.println("data:" + root.data);
?
? ? }
?
? ? public static boolean search(int target, node root) {
? ? ? ? if(root == null) {
? ? ? ? ? ? return false;
? ? ? ? }
? ? ? ? if (root.data > target) {
? ? ? ? ? ? search(target, root.left);
? ? ? ? } else if (root.data < target) {
? ? ? ? ? ? search(target, root.right);
? ? ? ? } else {
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? return false;
? ? }
?
?
}

node.java中：data 節(jié)點(diǎn)存放的數(shù)據(jù)，left，right 左右子節(jié)點(diǎn)

before() after() mid()為三種前序遍歷，中序遍歷，后序遍歷。關(guān)鍵方法 insert() search()

insert():參數(shù)：root node root為你的根節(jié)點(diǎn)，node為你要插入的節(jié)點(diǎn)。遞歸調(diào)用insert()當(dāng)遞歸到某個(gè)節(jié)點(diǎn)的右節(jié)點(diǎn)為空時(shí)表示可以插入數(shù)據(jù)

流程：

這里有六個(gè)節(jié)點(diǎn)作為示例：圓中為數(shù)據(jù)，簡(jiǎn)單的一個(gè)節(jié)點(diǎn)。選定3為根節(jié)點(diǎn)，隨機(jī)插入0 2 1 4 5 6

第一步，根節(jié)點(diǎn)3，第二步分別插入021 比三大的數(shù)跟這個(gè)類似，不做展示了。

插入0的時(shí)候沒有問題，放在3的左邊，插入2的時(shí)候，遞歸，2<3,2>0先看當(dāng)前節(jié)點(diǎn)（也就是3）的右邊是否有數(shù)據(jù)，為什么不看當(dāng)前節(jié)點(diǎn)左子節(jié)點(diǎn)的數(shù)據(jù)，因?yàn)?，?dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)一定比當(dāng)前節(jié)點(diǎn)大，所以只找當(dāng)前節(jié)點(diǎn)右邊的數(shù)據(jù)。當(dāng)右邊節(jié)點(diǎn)為空的時(shí)候，才會(huì)插入數(shù)據(jù)，這樣2就插入完成了，現(xiàn)在輪到1了，對(duì)于1，跟上面類似..

但是這樣會(huì)造成一個(gè)問題：這樣的查找效率很低，對(duì)于這樣特定的數(shù)據(jù)，所以要使用平衡二叉樹中的旋轉(zhuǎn)，重新選定節(jié)點(diǎn)來(lái)平衡二叉樹。關(guān)于二叉樹的文章，過幾天發(fā)布。

主函數(shù)：

public class main {
? ? public static void main(String[] args) {
? ? ? ? node root = new node(0);
? ? ? ? node root1 = new node(2);
? ? ? ? node root2 = new node(1);
? ? ? ? node root3 = new node(3);
? ? ? ? node root4 = new node(4);
? ? ? ? node root5 = new node(5);
? ? ? ? node root6 = new node(6);
? ? ? ? node.insert(root3,root);
? ? ? ? node.insert(root3,root2);
? ? ? ? node.insert(root3,root1);
? ? ? ? node.insert(root3,root4);
? ? ? ? node.insert(root3,root5);
? ? ? ? node.insert(root3,root6);
? ? ? ? node.mid(root3);
? ? ? ? boolean i= node.search(10,root3);
? ? ? ? System.out.println(i);
? ? ?
? ? }
?
}

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: