锐客网

  1. 首页 > 生活百科 > it技术 > >

java中关于树的代码 java树形( 三 )

IT技术管理


⒉剩下的结点被分成n=0个互不相交的集合T1、T2、......Tn ， 而且 ，  这些集合的每一个又都是树 。树T1、T2、......Tn被称作根的子树(Subtree) 。
树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树
1.树的度——也即是宽度，简单地说，就是结点的分支数 。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为2;树中度为零的结点称为叶结点或终端结点 。树中度不为零的结点称为分枝结点或非终端结点 。除根结点外的分枝结点统称为内部结点 。
2.树的深度——组成该树各结点的最大层次 。
3.森林——指若干棵互不相交的树的集合 ， 如上图，去掉根结点A ， 其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林；
4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树 。
树的表示
树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来 ， 同层子树之间用逗号隔开，最后用闭括号括起来 。如右图可写成如下形式：
二叉树
(a( b(d,e), c( f(,g(h,i) ),)))
建立一个二叉树，附带查询代码，JAVA代码import java.util.ArrayList;
// 树的一个节点
class TreeNode {
Object _value = https://www.04ip.com/post/null; // 他的值
TreeNode _parent = null; // 他的父节点，根节点没有PARENT
ArrayList _childList = new ArrayList(); // 他的孩子节点
public TreeNode( Object value, TreeNode parent ){
this._parent = parent;
this._value = https://www.04ip.com/post/value;
}
public TreeNode getParent(){
return _parent;
}
public String toString() {
return _value.toString();
}
}
public class Tree {
// 给出宽度优先遍历的值数组，构建出一棵多叉树
// null 值表示一个层次的结束
// "|" 表示一个层次中一个父亲节点的孩子输入结束
// 如：给定下面的值数组：
// { "root", null, "left", "right", null }
// 则构建出一个根节点，带有两个孩子("left","right")的树
public Tree( Object[] values ){
// 创建根
_root = new TreeNode( values[0], null );
// 创建下面的子节点
TreeNode currentParent = _root; // 用于待创建节点的父亲
//TreeNode nextParent = null;
int currentChildIndex = 0; // 表示 currentParent 是他的父亲的第几个儿子
//TreeNode lastNode = null; // 最后一个创建出来的TreeNode，用于找到他的父亲
for ( int i = 2; ivalues.length; i++ ){
// 如果null ,表示下一个节点的父亲是当前节点的父亲的第一个孩子节点
if ( values[i] == null ){
currentParent = (TreeNode)currentParent._childList.get(0);
currentChildIndex = 0;
continue;
}
// 表示一个父节点的所有孩子输入完毕
if ( values[i].equals("|") ){
if ( currentChildIndex+1currentParent._childList.size() ){
currentChildIndex++;
currentParent = (TreeNode)currentParent._parent._childList.get(currentChildIndex);
}
continue;
}
TreeNode child = createChildNode( currentParent, values[i] );
}
}
TreeNode _root = null;
public TreeNode getRoot(){
return _root;
}
/**
// 按宽度优先遍历，打印出parent子树所有的节点
private void printSteps( TreeNode parent, int currentDepth ){
for ( int i = 0; iparent._childList.size(); i++ ){
TreeNode child = (TreeNode)parent._childList.get(i);

推荐阅读


上一篇：快速erp系统，eRP系统

下一篇：a55me支持什么cpu，a55m配什么cpu