通用数据结构树—Java语言实现

迈不过友情╰ 2021-11-26 12:26 335阅读 0赞

树是一种常见的数据结构，得到了非常广泛的应用如文件系统、目录结构、霍夫曼编码等。根据树的特点及应用场景，我们通常会遇到二叉树、平衡树、红黑树、竞赛树、B树等。

在C、C++语言中我们在实现树时需要用到指针，如在二叉树中，我们会用指针指向左子树和右子树。在Java语言中并没有指针，但道理是类似的，我们使用对象来引用左子树和右子树。

下面是自己闲来无事时用Java语言实现的树，这不是一棵二叉树，而是一棵普通的树。提供了树了创建、层次遍历、查找等基本方法。

1.NodeData 是树中的节点或叶子存储的数据内容，可进行随意扩展

package  *com.eyecm.tree* ;  
  
*/\*\*  
 \* 树上每个节点存放的数据  
 \*   
 \*/*  
public  class NodeData  
\{   
     private  [String][] username ;  
     private  [String][] content ;  
  
     public NodeData ( )  
     \{   
  
     \}  
  
     public NodeData ( [String][] username,  [String][] content )  
     \{   
         this. username  = username ;  
         this. content  = content ;  
     \}  
  
     public  void output ( )  
     \{   
         [System][]. out. println (username  \+  " "  \+ content ) ;  
     \}  
\}

2.TredNode 是树的节点或叶子的抽象，提供层次遍历、查找等操作

package  *com.eyecm.tree* ;  
  
import  *java.util.ArrayList* ;  
import  *java.util.LinkedList* ;  
import  *java.util.Queue* ;  
  
*/\*\*  
 \* 树的节点  
 \*   
 \*/*  
public  class  [TreeNode][]  
\{   
     private  int id ;  
     private  [TreeNode][] parent ;  
     private ArrayList <TreeNode > children ;  
     private NodeData data ;  
  
     public  [TreeNode][] ( int id,  [TreeNode][] parent, ArrayList <TreeNode > children,  
            NodeData data )  
     \{   
         super ( ) ;  
         this. id  = id ;  
         this. parent  = parent ;  
         this. children  = children ;  
         this. data  = data ;  
     \}  
  
     public  int getId ( )  
     \{   
         return id ;  
     \}  
  
     public  void setId ( int id )  
     \{   
         this. id  = id ;  
     \}  
  
     public  [TreeNode][] getParent ( )  
     \{   
         return parent ;  
     \}  
  
     public  void setParent ( [TreeNode][] parent )  
     \{   
         this. parent  = parent ;  
     \}  
  
     public ArrayList <TreeNode > getChildren ( )  
     \{   
         return children ;  
     \}  
  
     public  void setChildren (ArrayList <TreeNode > children )  
     \{   
         this. children  = children ;  
     \}  
  
     public NodeData getData ( )  
     \{   
         return data ;  
     \}  
  
     public  void setData (NodeData data )  
     \{   
         this. data  = data ;  
     \}  
  
     */\*\*  
     \* 当前节点是否是根节点  
     \*   
     \* @return  
     \*/*  
     public  boolean isRoot ( )  
     \{   
         if  ( this. parent  ==  null )  
         \{   
             return  true ;  
         \}  else  
         \{   
             return  false ;  
         \}  
     \}  
  
     */\*\*  
     \* 当前节点是否是叶子节点  
     \*   
     \* @return  
     \*/*  
     public  boolean isLeaf ( )  
     \{   
         if  ( this. children  ==  null  ||  this. children. size ( )  ==  0 )  
         \{   
             return  true ;  
         \}  else  
         \{   
             return  false ;  
         \}  
     \}  
  
     */\*\*  
     \* 对该节点及其子树进行层次遍历  
     \*   
     \* @param treeNode  
     \*/*  
     public  static  void levelTraversal ( [TreeNode][] treeNode )  
     \{   
         if  (treeNode  ==  null )  
         \{   
             return ;  
         \}  
         if  (treeNode. isLeaf ( ) )  
         \{   
            treeNode. data. output ( ) ;  
         \}  else  
         \{   
            Queue <TreeNode > queue  =  new LinkedList <TreeNode > ( ) ;  
            queue. offer (treeNode ) ;  
             while  (queue. size ( )  >  0 )  
             \{   
                 [TreeNode][] node  = queue. poll ( ) ;  
                node. data. output ( ) ;  
  
                 if  (node. isLeaf ( )  ==  false )  
                 \{   
                     for  ( int i  =  0 ; i  < node. children. size ( ) ; i \++ )  
                     \{   
                        queue. offer (node. children. get (i ) ) ;  
                     \}  
                 \}  
             \}  
         \}  
     \}  
  
     */\*\*  
     \* 查找特点的节点，在此使用层次遍历进行查找  
     \*   
     \* @param id  
     \* @param treeNode  
     \* @return  
     \*/*  
     public  static  [TreeNode][] search ( int id,  [TreeNode][] treeNode )  
     \{   
         if  (treeNode  ==  null )  
         \{   
             return  null ;  
         \}  
         if  (treeNode. isLeaf ( ) )  
         \{   
             if  (treeNode. id  == id )  
             \{   
                 return treeNode ;  
             \}  else  
             \{   
                 return  null ;  
             \}  
         \}  else  
         \{   
            Queue <TreeNode > queue  =  new LinkedList <TreeNode > ( ) ;  
            queue. offer (treeNode ) ;  
             while  (queue. size ( )  >  0 )  
             \{   
                 [TreeNode][] node  = queue. poll ( ) ;  
                 if  (node. id  == id )  
                 \{   
                     return node ;  
                 \}  
  
                 if  (node. isLeaf ( )  ==  false )  
                 \{   
                     for  ( int i  =  0 ; i  < node. children. size ( ) ; i \++ )  
                     \{   
                        queue. offer (node. children. get (i ) ) ;  
                     \}  
                 \}  
             \}  
  
             return  null ;  
         \}  
     \}  
  
     */\*\*  
     \* 将节点插入为另一个节点的孩子  
     \*   
     \* @param childNode  
     \* @param toBeAppended  
     \* @return  
     \*/*  
     public  static  boolean appendAsChild ( [TreeNode][] childNode,  
             [TreeNode][] toBeAppended )  
     \{   
         if  (childNode  ==  null  || toBeAppended  ==  null )  
         \{   
             return  false ;  
         \}  else  
         \{   
             if  (toBeAppended. isLeaf ( ) )  
             \{   
                ArrayList <TreeNode > children  =  new ArrayList <TreeNode > ( ) ;  
                children. add (childNode ) ;  
                toBeAppended. children  = children ;  
             \}  else  
             \{   
                toBeAppended. children. add (childNode ) ;  
             \}  
  
             return  true ;  
         \}  
     \}  
  
     */\*\*  
     \* 将节点插入为另一个节点的兄弟  
     \*   
     \* @param sublingNode  
     \* @param toBeAppended  
     \* @return  
     \*/*  
     public  static  boolean appendAsSubling ( [TreeNode][] sublingNode,  
             [TreeNode][] toBeAppended )  
     \{   
         if  (sublingNode  ==  null  || toBeAppended  ==  null )  
         \{   
             return  false ;  
         \}  else  
         \{   
             *// 单根树，无法对根节点添加兄弟*  
             if  (toBeAppended. isRoot ( )  ==  true )  
             \{   
                 return  false ;  
             \}  else  
             \{   
                toBeAppended. parent. children. add (sublingNode ) ;  
                 return  true ;  
             \}  
         \}  
     \}  
\}

3.TreeHelper 提供了一段简单的代码来执行创建、查找等操作

package  *com.eyecm.tree* ;  
  
*/\*\*  
 \* 辅助工具类  
 \*   
 \*/*  
public  class TreeHelper  
\{   
     int id ;  
  
     public  int getId ( )  
     \{   
         return id ;  
     \}  
  
     public  void setId ( int id )  
     \{   
         this. id  = id ;  
     \}  
  
     public  static  void main ( [String][] \[ \] args )  
     \{   
        NodeData root  =  new NodeData ( "root",  "this is root" ) ;  
  
        NodeData n1\_1  =  new NodeData ( "n1\_1",  "level 1" ) ;  
        NodeData n1\_2  =  new NodeData ( "n1\_2",  "level 1" ) ;  
  
        NodeData n2\_1  =  new NodeData ( "n2\_1",  "level 2,n1\_1 child" ) ;  
        NodeData n2\_2  =  new NodeData ( "n2\_2",  "level 2,n1\_1 child" ) ;  
        NodeData n2\_3  =  new NodeData ( "n2\_3",  "level 2,n1\_2 child" ) ;  
        NodeData n2\_4  =  new NodeData ( "n2\_4",  "level 2,n1\_2 child" ) ;  
  
        NodeData n3\_1  =  new NodeData ( "n3\_1",  "level 3,n2\_2 child" ) ;  
  
         [TreeNode][] rootNode  =  new  [TreeNode][] ( 0,  null,  null, root ) ;  
  
         [TreeNode][] n1\_1\_node  =  new  [TreeNode][] ( 1,  null,  null, n1\_1 ) ;  
         [TreeNode][] n1\_2\_node  =  new  [TreeNode][] ( 2,  null,  null, n1\_2 ) ;  
         [TreeNode][]. appendAsChild (n1\_1\_node, rootNode ) ;  
         [TreeNode][]. appendAsChild (n1\_2\_node, rootNode ) ;  
  
         [TreeNode][] n2\_1\_node  =  new  [TreeNode][] ( 4,  null,  null, n2\_1 ) ;  
         [TreeNode][] n2\_2\_node  =  new  [TreeNode][] ( 5,  null,  null, n2\_2 ) ;  
         [TreeNode][]. appendAsChild (n2\_1\_node, n1\_1\_node ) ;  
         [TreeNode][]. appendAsChild (n2\_2\_node, n1\_1\_node ) ;  
  
         [TreeNode][] n2\_3\_node  =  new  [TreeNode][] ( 6,  null,  null, n2\_3 ) ;  
         [TreeNode][] n2\_4\_node  =  new  [TreeNode][] ( 7,  null,  null, n2\_4 ) ;  
         [TreeNode][]. appendAsChild (n2\_3\_node, n1\_2\_node ) ;  
         [TreeNode][]. appendAsChild (n2\_4\_node, n1\_2\_node ) ;  
  
         [TreeNode][] n3\_1\_node  =  new  [TreeNode][] ( 13,  null,  null, n3\_1 ) ;  
         [TreeNode][]. appendAsChild (n3\_1\_node, n2\_2\_node ) ;  
  
         [TreeNode][]. levelTraversal ( [TreeNode][]. search ( 5, rootNode ) ) ;  
     \}  
\}

[String]: http://www.google.com/search?hl=en&q=allinurl%3Astring+java.sun.com&btnI=I%27m%20Feeling%20Lucky
[System]: http://www.google.com/search?hl=en&q=allinurl%3Asystem+java.sun.com&btnI=I%27m%20Feeling%20Lucky
[TreeNode]: http://www.google.com/search?hl=en&q=allinurl%3Atreenode+java.sun.com&btnI=I%27m%20Feeling%20Lucky