バイナリソートツリーは、バイナリ検索ツリーとも呼ばれます。これは、空のツリーまたは次のプロパティを備えたバイナリツリーのいずれかです。
左のサブツリーが空でない場合、左サブツリーのすべてのノードの値は、そのルートノードの値よりも小さくなります。
右のサブツリーが空でない場合、右サブツリー上のすべてのノードの値は、そのルートノードの値よりも大きくなります。
左と右のサブツリーもそれぞれバイナリソートツリーです。
次のコード実装:
Import Java.util.linkedList; Import java.util.queue; class node {public int data;パブリックノードは左;パブリックノード右; public int leftmaxdistance; public int rightmaxdistance; public node(int data){this.data = data; this.left = null; this.right = null; }}/*** @author ty*挿入、順序のトラバーサル、予約注文のトラバーサル、ポストオーバートラバーサル、およびすべてのノードの最大距離を計算するバイナリソートツリーの実装*/public class binarytree {private node root; public binarytree(){root = null; } public void insert(int data){node newNode = new Node(data); if(root == null)root = newNode; else {node current = root;ノード親; while(true){//挿入位置parent = currentを見つけます。 if(data <current.data){current = current.left; if(current == null){parent.left = newNode;戻る; }} else {current = current.right; if(current == null){parent.right = newNode;戻る; }}}}}}}} //数値値を入力して、バイナリツリーpublic void buildtree(int [] data){for(int i = 0; i <data.length; i ++){insert(data [i]); }}} //注文のトラバーサル法は、public void inorder(node localroot){if(localroot!= null){inorder(localroot.left); System.out.print(localroot.data+""); inorder(localroot.right); }} public void inorder(){this.inorder(this.root); } //予約注文トラバーサル法は、public void preorder(node localroot){localroot!= null){system.out.print(localroot.data+"");予約(LocalRoot.Left);予約(localRoot.right); }} public void preorder(){this.preorder(this.root); } // Postorderトラバーサル法は、public void postorder(node localroot){if(localroot!= null){postorder(localroot.left); Postorder(localRoot.right); System.out.print(localroot.data+""); }} public void postorder(){this.postorder(this.root); } /***レイヤーシーケンストラバーサルバイナリツリー:ルートノードをキューに入れてから、毎回キューからノードを使用してノードの値を印刷します。 *このノードにチャイルドノードがある場合、キューが空になるまで子ノードをキューのテールに入れます*/ public void layertranverse(){if(this.root == null)return; queue <node> q = new linkedlist <node>(); Q.Add(this.root); while(!q.isempty()){node n = q.poll(); System.out.print(n.data+""); if(n.left!= null)q.add(n.left); if(n.right!= null)q.add(n.right); }} private int maxlen = 0; private int max(int a、int b){return a> b?a:b; } public void findmaxdistance(node root){if(root == null)return; if(root.left == null)root.leftmaxdistance = 0; if(root.right == null)root.rightMaxDistance = 0; if(root.left!= null)findmaxdistance(root.left); if(root.right!= null)findmaxdistance(root.right); //左ワードツリーのルートノードからの最大距離を計算します(root.left!= null)root.leftmaxdistance = max(root.left.leftmaxdistance、root.left.rightmaxdistance)+1; //右ワードツリーのルートノードからの最大距離を計算します(root.right!= null)root.rightmaxdistance = max(root.right.leftmaxdistance、root.right.rightmaxdistance)+1; //バイナリツリーのすべてのノードの最大距離を取得しますif(root.leftmaxdistance+root.rightmaxdistance> maxlen){maxlen = root.leftmaxdistance+root.rightmaxdistance; }} public static void main(string [] args){binarytree bitree = new binaryTree(); int [] data = {2,8,7,4,9,3,1,6,7,5}; bitree.buildtree(data); System.out.print( "バイナリツリーの順序トラバーサル:"); bitree.inorder(); System.out.println(); System.out.print( "バイナリツリーの予約注文トラバーサル:"); bitree.preorder(); System.out.println(); System.out.println(); System.out.println(); System.out.print( "バイナリツリーの順序後のトラバーサル:"); bitree.postorder(); System.out.println(); System.out.print( "バイナリツリーのレイヤーオーバートラバーサル:"); bitree.layertranverse(); System.out.println(); bitree.findmaxdistance(bitree.root); System.out.println( "バイナリツリーのノードの最大距離:"+bitree.maxlen); }}上記はこの記事のすべての内容です。この記事の内容が、すべての人の勉強や仕事に役立つことを願っています。また、wulin.comをもっとサポートしたいと思っています!