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é)點存放的數據，left，right 左右子節(jié)點

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

insert():參數：root node root為你的根節(jié)點，node為你要插入的節(jié)點。遞歸調用insert()當遞歸到某個節(jié)點的右節(jié)點為空時表示可以插入數據

流程：

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

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

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

但是這樣會造成一個問題：這樣的查找效率很低，對于這樣特定的數據，所以要使用平衡二叉樹中的旋轉，重新選定節(jié)點來平衡二叉樹。關于二叉樹的文章，過幾天發(fā)布。

主函數：

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);
? ? ?
? ? }
?
}

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: