バイナリツリーの分類(ストレージ構造による)
木の分類(ストレージ構造による)
シーケンシャルストレージ(配列で表される(静的バイナリツリー))
チェーンストレージ
いくつかの特別なバイナリルーツ:
完全なバイナリツリー、バランスバイナリツリー(AVL)、手がかりバイナリツリー、トライフォーク(父とのポインター)
バイナリ検索ツリーまたはバイナリ検索ツリー(BST)
使用されるバイナリツリーは、次の図に示されています。
バイナリツリーのJava実装(チェーンストレージ構造)
class treeNode {private int key = 0;プライベート文字列データ= null;プライベートブールisvisted = false; private treenode leftchild = null; private treenode rightchild = null; public treenode(){} public treenode(int key、string data){this.key = key; this.data = data; this.leftchild = null; this.rightchild = null; } public int getKey(){return key; } public void setKey(int key){this.key = key; } public string getData(){return data; } public void setData(string data){this.data = data; } public treenode getLeftChild(){return leftchild; } public void setLeftChild(treenode leftchild){this.leftchild = leftchild; } public treenode getRightChild(){return rightchild; } public void setrightchild(treenode rightchild){this.rightchild = rightchild; } public boolean isvisted(){return isvisted; } public void setVisted(boolean isvisted){this.isvisted = isvisted; }} public class binarytree {private treenode root = null; public binarytree(){root = new Treenode(1、 "rootnode(a)"); } public void createbintree(treenode root){//マニュアル作成(構造は図に示されています)treeNode newNodeb = new Treenode(2、 "b"); treenode newNodec = new Treenode(3、 "c"); treenode newNoded = new Treenode(4、 "d"); treenode newNodee = new Treenode(5、 "e"); treenode newNodef = new Treenode(6、 "f"); root.setLeftChild(NewNodeB); root.setrightchild(newnodec); root.getLeftChild()。setLeftChild(newNoded); root.getLeftChild()。setRightChild(newNodee); root.getRightChild()。setRightChild(newNodef); } public boolean isempty(){//バイナリツリーが空かどうかを判断しますrute root == null; } public int height(){//ツリーの高さの戻り高さを見つけます(root); } public height(treeNode subtree){if(subtree == null)return 0; //再帰端:空のツリーの高さは0です{int i = height(subtree.getLeftChild()); int j = height(subtree.getRightChild()); return(i <j)? J + 1:i + 1; }} public int size(){//ノードの数を検索しますreturn size(root); } public int size(treenode subtree){if(subtree == null)return 0; else {return 1 + size(subtree.getLeftChild()) + size(subtree.getRightchild()); }} public treenode parent(treeNode element){//親ノードreturn(root == null || root ==要素)を返しますか? null:parent(root、element); } public treenode parent(treenode subtree、treenode element){if(subtree == null)return null; if(subtree.getLeftChild()== element || subtree.getRightChild()== element)// finish、親ノードアドレスを返しますreturn subtree; Treenode P; //左サブツリーの最初の外観。左のサブツリーにない場合は、右サブツリーに移動して(p = parent(subtree.getLeftchild()、element)!= null)//再帰的にpを再帰的に検索します。 else // returicive returicive returive returtive return parent(subtree.getRightChild()、element); } public treenode leftchild(treeNode element){//左のサブツリーリターン(要素!= null)を返しますか? element.getLeftChild():null; } public treenode rightchild(treenode element){//右のサブツリーリターン(要素!= null)を返しますか? element.getRightChild():null; } public treenode getRoot(){//ルートノードリターンルートを取得します。 } public void destroy(treenode subtree){// private function:root subtreeでsubtreeを削除if(subtree!= null){Destroy(subtree.getLeftChild()); //左サブツリーを削除してください(subtree.getRightchild()); //右サブツリーを削除// delete subtree; //ルートノードサブツリー= nullを削除します。 }} public void traverse(treenode subtree){system.out.println( "key:" + subtree.getKey() + " - name:" + subtree.getData()); traverse(subtree.getLeftChild()); traverse(subtree.getRightChild()); } public void preorder(treenode subtree){// root first if(subtree!= null){visted(subtree); PREORDER(SUBTREE.GETLEFTCHILD());予約(Subtree.getRightChild()); }} public void inorder(treeNode subtree){//中root if(subtree!= null){inorder(subtree.getLeftChild()); Visted(subtree); inorder(subtree.getRightChild()); }} public void postorder(treenode subtree){// post root if(subtree!= null){postorder(subtree.getLeftChild()); Postorder(subtree.getRightchild()); Visted(subtree); }} public void levelorder(treenode subtree){// horily periphery} public boolean insert(treeNode element){// return true; } public boolean find(treenode element){// return true; }公開void目撃(treeNode subtree){subtree.setvisted(true); System.out.println( "key:" + subtree.getKey() + " - name:" + subtree.getData()); } public static void main(string [] args){binarytree bt = new binarytree(); Bt.CreateBintree(bt.Root); System.out.println( "ツリーのサイズは" + bt.size()); System.out.println( "ツリーの高さは" + bt.height()); System.out.println( "********* preorder(preorder)[abdecf]転送***************"); bt.preorder(bt.root); System.out.println( "********* medium root(inner order)[dbeacf]転送***************"); bt.inorder(bt.root); System.out.println( "********* last root(post order)[debfca]転送***************"); bt.postorder(bt.root); }}結果出力:
ツリーのサイズは6です
木の高さは3です
******* First Root(Preorder)[Abdecf] Traversal **************
キー:1-NAME:rootnode(a)
キー:2-NAME:b
キー:4-NAME:d
キー:5-NAME:e
キー:3-NAME:c
キー:6-NAME:f
*******ミディアムルート(ミドルオーダー)[dbeacf]トラバーサル****************
キー:4-NAME:d
キー:2-NAME:b
キー:5-NAME:e
キー:1-NAME:rootnode(a)
キー:3-NAME:c
キー:6-NAME:f
*******最後のルート(投稿注文)[Debfca]トラバーサル****************
キー:4-NAME:d
キー:5-NAME:e
キー:2-NAME:b
キー:6-NAME:f
キー:3-NAME:c
キー:1-NAME:rootnode(a)
この記事がJavaプログラミングを勉強する学生に役立つことを願っています。