四叉树代码java 二叉树完整代码

java实现多叉树的某层遍历，求思路。一棵多叉树有M层，子节点数不定，要求打印输出第N层的节点。说

package action;

成都创新互联专注于衡阳县网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供衡阳县营销型网站建设，衡阳县网站制作、衡阳县网页设计、衡阳县网站官网定制、成都小程序开发服务，打造衡阳县网络公司原创品牌,更为您提供衡阳县网站排名全网营销落地服务。

import java.util.HashMap;

import java.util.List;

import java.util.Map;

public class Test {

/**

* M层中给出层节点找出这层的子节点

* 你的需求并没有说有一个树的要求

*/

public static void main(String args[]){

int m;//M

int n;//n

Map mapone=new HashMap();

//你坑定要知道子节点父节点关系

for(int i=0;im;i++){

mapone.put(父节点的key, 子节点的结合);

}

//遍历完成不是每层的父节点下的所有子节点都在这个MAP里面了吗

List list=mapone.get(第n层的节点key值);

}

}

已知点求与已知点集中的最近点的算法

可以用四叉树（二维）或者八叉树（三维）来对点分组，把空间分块，计算每块的中心点坐标即为树的中间结点，与其距离小于组半径的即为其组内的叶节点。已知点所在的组可以根据要求再缩短半径细分，直到点的数量达到要求。

八叉树参考：

哪位能讲讲四叉树算法以及其实现原理

1、HMACSHA1的概念

HMACSHA1 是

从 SHA1 哈希函数构造的一种键控哈希算法，被用作 HMAC（基于哈希的消息验证代码）。此 HMAC

进程将密钥与消息数据混合，使用哈希函数对混合结果进行哈希计算，将所得哈希值与该密钥混合，然后再次应用哈希函数。输出的哈希值长度为 160

位，可以转换为指定位数。

上面是微软的标准定义，我看了也没太明白，他的作用一句话来理解：就是确认请求的URL或者参数是否存在被篡改，以

签名为例：发送方（自己）将参数等进行HMAC算法计算，将得到的哈希值（即签名值）与请求的参数一同提交至接收方（端），然后接收方再次将参数等值

进行HMAC算法计算，将得到的哈希值与你传递过来的哈希值进行核对验证，若一样，说明请求正确、验证通过，进行一下步工作，若不一样，将返回错误。

（下面说的够详细了吧，还不理解，留言给我）

2、 OAuth 1.0中用到的哈希算法

/// summary

/// HMACSHA1算法加密并返回ToBase64String

/// /summary

/// param name="strText"签名参数字符串/param

/// param name="strKey"密钥参数/param

/// returns返回一个签名值(即哈希值)/returns

public static string ToBase64hmac(string strText, string strKey)

{

HMACSHA1 myHMACSHA1 = new HMACSHA1(Encoding.UTF8.GetBytes(strKey));

byte[] byteText = myHMACSHA1.ComputeHash(Encoding.UTF8.GetBytes(strText));

return System.Convert.ToBase64String(byteText);

}

或者写成，原理一样：

public static string HMACSHA1Text(string EncryptText, string EncryptKey)

{

//HMACSHA1加密

string message;

string key;

message = EncryptText;

key = EncryptKey;

System.Text.ASCIIEncoding encoding = new System.Text.ASCIIEncoding();

byte[] keyByte = encoding.GetBytes(key);

HMACSHA1 hmacsha1 = new HMACSHA1(keyByte);

byte[] messageBytes = encoding.GetBytes(message);

byte[] hashmessage = hmacsha1.ComputeHash(messageBytes);

return ByteToString(hashmessage);

}

前面都注释了参数含义，就不再说明了。COPY就可使用

注明：页面请引用

using System.Security.Cryptography;

3、介绍另外一种HMACSHA1算法的写法

public static string HMACSHA1Text(string EncryptText, string EncryptKey)

{

//HMACSHA1加密

HMACSHA1 hmacsha1 = new HMACSHA1();

hmacsha1.Key = System.Text.Encoding.UTF8.GetBytes(EncryptKey);

byte[] dataBuffer = System.Text.Encoding.UTF8.GetBytes(EncryptText);

byte[] hashBytes = hmacsha1.ComputeHash(dataBuffer);

return Convert.ToBase64String(hashBytes);

}

求四叉树完整建立和遍历的运行代码（c或c++）

一个四叉树的实现代码

class QuadTreeCode

{

public:

vectorint m_Numbers;

/*判断两个四叉树码是否相等*/

bool operator ==( QuadTreeCode tempTree )

{

if ( m_Numbers.size()!=tempTree.m_Numbers.size() )

{

return false;

}

else

{

for ( int i=0; im_Numbers.size(); i++ )

{

if ( m_Numbers[i]!=tempTree.m_Numbers[i])

{

return false;

}

}

}

return true;

}

/*返回四叉树码的长度*/

int GetLength()

{

return m_Numbers.size();

}

int operator[](int Index)

{

return m_Numbers[Index];

}

};

enum ChildType

{

UL = 0,

UR = 3,

LL = 1,

LR = 2

};

templateclass T

class QuadTreeNode

{

public:

T *m_pData;

QuadTreeNode *m_pUpperLeft,*m_pUpperRight,*m_pLowerLeft,*m_pLowerRight;

QuadTreeCode m_Code; //节点在树中位置的编码

QuadTreeNode ()

{

m_pData = NULL;

m_pUpperLeft = m_pUpperRight = m_pLowerLeft = m_pLowerRight = NULL;

}

~QuadTreeNode ()

{

delete m_pData;

}

/*返回子成员的地址*/

QuadTreeNode ** GetChild( ChildType ctype )

{

switch( ctype )

{

case ChildType::UL:

return m_pUpperLeft;

break;

case ChildType::UR:

return m_pUpperRight;

break;

case ChildType::LL:

return m_pLowerLeft;

break;

case ChildType::LR:

return m_pLowerRight;

break;

}

}

};

templateclass T

class QuadTree

{

public:

int m_nTreeDepth; //树的深度

QuadTreeNodeT *m_pHeadNode; //树的头部

QuadTree()

{

m_nTreeDepth = 0;

m_pHeadNode = NULL;

}

~QuadTree()

{

void (QuadTree::*func)(QuadTreeNodeT *) ;

func = QuadTree::DestroyNode;

PostOrderOperation( m_pHeadNode, func );

}

/*

后序遍历方式操作四叉树

*/

void PostOrderOperation( QuadTreeNodeT * ptempNode, void (QuadTreeT::*NodeOp)( QuadTreeNodeT * ) )

{

if( ptempNode!=NULL )

{

PostOrderOperation( ptempNode-m_pLowerLeft, NodeOp );

PostOrderOperation( ptempNode-m_pLowerRight, NodeOp );

PostOrderOperation( ptempNode-m_pUpperLeft, NodeOp );

PostOrderOperation( ptempNode-m_pUpperRight, NodeOp );

(this-*NodeOp) ( ptempNode );

}

}

void DestroyNode( QuadTreeNodeT * ptempNode )

{

delete ptempNode;

}

/*创建树枝*/

void CreateBranch( QuadTreeNodeT**ppNode , int TreeDepth, int CurrentDepth )

{

if( CurrentDepthTreeDepth )

{

return;

}

else

{

QuadTreeNodeT *pNewNode = new QuadTreeNodeT;

*ppNode = pNewNode;

QuadTreeNodeT **pTempNode;

CreateBranch( pNewNode-GetChild(ChildType::UL), TreeDepth, CurrentDepth+1 );

CreateBranch( pNewNode-GetChild(ChildType::UR), TreeDepth, CurrentDepth+1 );

CreateBranch( pNewNode-GetChild(ChildType::LL), TreeDepth, CurrentDepth+1 );

CreateBranch( pNewNode-GetChild(ChildType::LR), TreeDepth, CurrentDepth+1 );

}

}

/*按照四叉树码进行操作*/

bool OperateNodeByCode( QuadTreeCode code, void (*Op)( QuadTreeNodeT *) )

{

QuadTreeNode* ptempNode = m_pHeadNode;

for( int i=0; icode.GetLength(); i++ )

{

ptempNode = ptempNode-GetChild( code[i] );

if( ptempNode==NULL )

return false;

}

Op( ptempNode );

return true;

}

/*近创建内存结构，数据内容并未赋值*/

void CreateTree( int TreeDepth )

{

m_nTreeDepth = TreeDepth;

CreateBranch( m_pHeadNode, TreeDepth, 0);

}

//virtual void CreateNode( QuadTreeNodeT * ptempNode ) const = 0;

};

24.8°+12°37'等于？

这个先要把两个数换算成一致的单位。1度等于60分，就是24.8度+12.617度=37.417度，就是37度25分。

简单的JAVA多叉树问题实现

TreeNode.java

/*

* Copyright Walker Studio

* All Rights Reserved.

* 

* 文件名称： TreeNode.java

* 摘 要：

* 作 者： Walker

* 创建时间： 2013-03-19

*/

package com.walker.commons.data.model;

/**

* 树节点

* 

* @author Walker

* @version 1.0.0.0

*/

public class TreeNode 

{

/** 节点Id*/

private String nodeId;

/** 父节点Id*/

private String parentId;

/** 文本内容*/

private String text;

/**

 * 构造函数

 * 

 * @param nodeId 节点Id

 */

public TreeNode(String nodeId)

{

this.nodeId = nodeId;

}

/**

 * 构造函数

 * 

 * @param nodeId 节点Id

 * @param parentId 父节点Id

 */

public TreeNode(String nodeId, String parentId)

{

this.nodeId = nodeId;

this.parentId = parentId;

}

public String getNodeId() {

return nodeId;

}

public void setNodeId(String nodeId) {

this.nodeId = nodeId;

}

public String getParentId() {

return parentId;

}

public void setParentId(String parentId) {

this.parentId = parentId;

}

public String getText() {

return text;

}

public void setText(String text) {

this.text = text;

}

}

ManyTreeNode.java

/*

* Copyright Walker Studio

* All Rights Reserved.

* 

* 文件名称： ManyTreeNode.java

* 摘 要：

* 作 者： Walker

* 创建时间： 2013-03-19

*/

package com.walker.commons.data.model;

import java.util.ArrayList;

import java.util.List;

/**

* 多叉树节点

*

* @author Walker

* @verion 1.0.0.0

*/

public class ManyTreeNode 

{

/** 树节点*/

private TreeNode data;

/** 子树集合*/

private ListManyTreeNode childList;

/**

 * 构造函数

 * 

 * @param data 树节点

 */

public ManyTreeNode(TreeNode data)

{

this.data = data;

this.childList = new ArrayListManyTreeNode();

}

/**

 * 构造函数

 * 

 * @param data 树节点

 * @param childList 子树集合

 */

public ManyTreeNode(TreeNode data, ListManyTreeNode childList)

{

this.data = data;

this.childList = childList;

}

public TreeNode getData() {

return data;

}

public void setData(TreeNode data) {

this.data = data;

}

public ListManyTreeNode getChildList() {

return childList;

}

public void setChildList(ListManyTreeNode childList) {

this.childList = childList;

}

}

ManyNodeTree.java

/*

* Copyright Walker Studio

* All Rights Reserved.

* 

* 文件名称： ManyNodeTree.java

* 摘 要：

* 作 者： Walker

* 创建时间： 2013-03-19

*/

package com.walker.commons.data.model;

import java.util.ArrayList;

import java.util.List;

/**

* 多叉树生成、遍历工具

* 

* @author Walker

* @version 1.0.0.0

*/

public class ManyNodeTree 

{

/** 树根*/

private ManyTreeNode root;

/**

 * 构造函数

 */

public ManyNodeTree()

{

root = new ManyTreeNode(new TreeNode("root"));

}

/**

 * 生成一颗多叉树，根节点为root

 * 

 * @param treeNodes 生成多叉树的节点集合

 * @return ManyNodeTree

 */

public ManyNodeTree createTree(ListTreeNode treeNodes)

{

if(treeNodes == null || treeNodes.size()  0)

return null;

ManyNodeTree manyNodeTree =  new ManyNodeTree();

//将所有节点添加到多叉树中

for(TreeNode treeNode : treeNodes)

{

if(treeNode.getParentId().equals("root"))

{

//向根添加一个节点

manyNodeTree.getRoot().getChildList().add(new ManyTreeNode(treeNode));

}

else

{

addChild(manyNodeTree.getRoot(), treeNode);

}

}

return manyNodeTree;

}

/**

 * 向指定多叉树节点添加子节点

 * 

 * @param manyTreeNode 多叉树节点

 * @param child 节点

 */

public void addChild(ManyTreeNode manyTreeNode, TreeNode child)

{

for(ManyTreeNode item : manyTreeNode.getChildList())

{

if(item.getData().getNodeId().equals(child.getParentId()))

{

//找到对应的父亲

item.getChildList().add(new ManyTreeNode(child));

break;

}

else

{

if(item.getChildList() != null  item.getChildList().size()  0)

{

addChild(item, child);

}

}

}

}

/**

 * 遍历多叉树 

 * 

 * @param manyTreeNode 多叉树节点

 * @return 

 */

public String iteratorTree(ManyTreeNode manyTreeNode)

{

StringBuilder buffer = new StringBuilder();

buffer.append("\n");

if(manyTreeNode != null) 

{

for (ManyTreeNode index : manyTreeNode.getChildList()) 

{

buffer.append(index.getData().getNodeId()+ ",");

if (index.getChildList() != null  index.getChildList().size()  0 ) 

{

buffer.append(iteratorTree(index));

}

}

}

buffer.append("\n");

return buffer.toString();

}

public ManyTreeNode getRoot() {

return root;

}

public void setRoot(ManyTreeNode root) {

this.root = root;

}

public static void main(String[] args)

{

ListTreeNode treeNodes = new ArrayListTreeNode();

treeNodes.add(new TreeNode("系统权限管理", "root"));

treeNodes.add(new TreeNode("用户管理", "系统权限管理"));

treeNodes.add(new TreeNode("角色管理", "系统权限管理"));

treeNodes.add(new TreeNode("组管理", "系统权限管理"));

treeNodes.add(new TreeNode("用户菜单管理", "系统权限管理"));

treeNodes.add(new TreeNode("角色菜单管理", "系统权限管理"));

treeNodes.add(new TreeNode("用户权限管理", "系统权限管理"));

treeNodes.add(new TreeNode("站内信", "root"));

treeNodes.add(new TreeNode("写信", "站内信"));

treeNodes.add(new TreeNode("收信", "站内信"));

treeNodes.add(new TreeNode("草稿", "站内信"));

ManyNodeTree tree = new ManyNodeTree();

System.out.println(tree.iteratorTree(tree.createTree(treeNodes).getRoot()));

}

}