java 满二叉树算法

Question

根据一个二进制数组，建一个固定的满二叉树，然后根据二叉树的层数，分成几段，例如二叉树有三层，就每两个0,1字符为一组。位数不够补0。还有就是二叉树不是根节点没有0,1代表，每个结点只有编号，即S几。每一段遍历一次二叉树，例如第一段是01，则先S1左孩子，再S2右孩子，假设为S8，则将S8发给接收端，接收端再根据S8，从S0遍历到S8得到01，将信息的所有段整合起来。即除了叶子结点外没有0,1意义。而树的高度是固定的，字符串变成的0,1代码段只能比他短，短的位数补0.请各位帮个忙.因为二叉树不熟悉.
请各位帮忙写一下代码.提示一下.
遍历.查找.建立.....谢谢了.

Answer 1

字符串转换成二进制数组
然后根据二进制数据的建立一颗满二叉树.
左节点为0.右节点为1. 节点名称:为S开头的.比如根节点为S0.下面的左节点为S1.S1=0;S2=1;
遍历的话:
如果传入S8的话.找出来S8所有的节点的.比如:S0-S1-S3-S8.
找出的二进制值是:000.(S0不用.)

Answer 2

应该是:
遍历的话:
如果传入S8的话.找出来S8所有的节点的.比如:S0-S1-S3-S8.
找出的二进制值是:001.(S0不用.)

Answer 3

输入:一个英文字符串:"ABC".
转换成一个二进制数组比如:
String [] arr=new String[]{"01000001","01000010","01000011"};
然后根据上面的数组建立一颗满二叉树.根结点名称为S0.其它节点名称分别为:S1,S2,S3...
左节点的值为:0.右节点的值为1:=====================================================================================
然后根据二叉树的层数，分成几段，例如二叉树有三层，就每两个0,1字符为一组。位数不够补0。还有就是二叉树不是根节点没有0,1代表，每个结点只有编号，即S几。每一段遍历一次二叉树，例如第一段是01，则先S1左孩子，再S2右孩子，假设为S8，则将S8发给接收端，接收端再根据S8，从S0遍历到S8得到01，将信息的所有段整合起来。即除了叶子结点外没有0,1意义。而树的高度是固定的，字符串变成的0,1代码段只能比他短，短的位数补0.=====================================================================================输出:然后根据上面的二进制数据.返回对应的节点.
===============================================================其实要做的就是:
我输入一段英文字符串.然后转换成二进制数组.根据二进制数组生成一颗满二叉树.
然后返回对应的节点.
发送级接收端.然后接收端根据接收到的节点名称.遍历满二叉树.得到二进制数据.
然后转换成英文字符串.
就是利用满二叉树加密与解密字符串.不知道我有没有说明白.

Answer 4

输入:一个英文字符串:"ABC".
转换成一个二进制数组比如:
String [] arr=new String[]{"01000001","01000010","01000011"};
然后根据上面的数组建立一颗满二叉树.根结点名称为S0.其它节点名称分别为:S1,S2,S3...
左节点的值为:0.右节点的值为1:===============================================================
上面说的A的二制为:"01000001".B为:"01000010".C为:"01000011".
根据arr中的数据建立一颗满二叉树.就是把二进制的值.转换成满二叉树的节点的值.
0为左节点的值.1为右节点的值. 比如：S1为左节点：则它的值为0．S2为右节点：则它的值为1．相当于　　　　　　　　　　　　　　　　　　S0(根据结节点)
                                / \
                     (value:0)s1   S2(value:1)
　　　　　　　　　　　　　　　/   \        /   \　　
                         (0)s3   S4(1) (0)s5   S6(1)比如：我有一个01的二进制．遍历得的节点是S4.00的话就是S3S4.我发送给接收端后．再查找满二叉树　得到的二进制值是01
S3.我发送给接收端后．再查找满二叉树　得到的二进制值是00
再把二进制转换成字符．＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝思路是这样子的发送端：输入字符串后．转换成二进制数组．根据二进制数组生成二叉树．
然后遍历得到节点．发送级接收端．
接收端遍历二叉树得到二进制数组．二进制数组转换成字符串．
实现字符串的加密与解密．明文是字符串．密文是二叉树节点名称．

Answer 5

1, "0"
2, "1"
3, "00"
4, "01"
5, "10"
6, "11"
7, "000"
8, "001"
9, "010"
10, "011"

11, "100"
12, "101"
13, "110"
14, "111"
15, "0000"
16, "0001"
17, "0010"
18, "0011"
19, "0100"
20, "0101"上面是节点对应的所有经过的节点的值．
比如：S8: S1(0)-S3(0)-S8(1)  所以对应的值是001比如：我一个字符串转换成二制话．是001．建立一颗满二叉树．根据左节点为0.右节点为1的规则．则路线是 S1(0)-S3(0)-S8(1)
所以返回的值是S8这个节点．我的接收端接收到S8这个节点值．
在去找S8.所对应的节点与相对应的值：S8(1)-S3(0)-S1(0)
所以得到的值是001．
再转换成字符串．只是上面的要求．二进制数组以及分成几段．整合．
不明白．这些东西．也不了解．所以请各位．指点指点．能不能给我相关代码参考．
因为二叉树不了解．自己写．不知道从何下手．

Answer 6

目录结构如下:
包:mars.security有8个类
BinaryTree.java
Decrypt.java
DecryptHelper.java
Encrypt.java
EncryptHelper.java
EncryptTree.java
Node.java
Tool.java
包:mars.test 测试类
Test.java

Answer 7

package mars.security;public class BinaryTree {

private Node binaryTree=null;

public BinaryTree(Node node)
{
binaryTree=node;
} public Node getBinaryTree() {
return binaryTree;
}
public void setBinaryTree(Node binaryTree) {
this.binaryTree = binaryTree;
}


// /**
//  * 
//  * @param list
//  * @return
//  */
// public static BinaryTree init(LinkedList<Node> list)
// {
// BinaryTree returnValue=null;
//
// if(validateNodeCount(list.size()))
// {
//
// }
//
// return returnValue;
// }
//
// /**
//  * 判断结点个数是否有效
//  * @param count 结点个数
//  * @return true有效/false无效
//  * 
//  */
// public static boolean validateNodeCount(int count)
// {
// boolean returnValue=false;
// for(int i=1;i>0;i++)
// {
// if(getNodeCount(i)==count)
// {
// returnValue=true;
// break;
// }
// }
// return returnValue;
// }
//
// /**
//  * 计算结点个数
//  * @param layer 层数
//  * @return 结点个数
//  */
// public static int getNodeCount(int layer)
// {
// int returnValue=0;
//
// if(layer<=0)
// {
// returnValue=0;
// }
//
// if(layer>0)
// {
// returnValue=(int)Math.pow(2,layer-1)+getNodeCount(layer-1);
//
// }
// return returnValue;
// }



}

Answer 8

package mars.security;
public class Decrypt {
/**
 * 根据密码二进制流获取明文二进制流
 */
public static String getTextBits(String digits) throws Exception
{
String returnValue="";
if(digits.length()%4!=0)
{
throw new Exception();
}

for(int i=0;i<=digits.length()-4;i+=4)
{
try {
int index=DecryptHelper.getDigit(digits.substring(i, i+4))-1;
returnValue+=EncryptTree.DigitValue.get(index);
} catch (Exception e) {
e.printStackTrace();
}
}

return returnValue;
}

/**
 * 
 * @param textBits  调用getTextBits(digit)的返回结果
 * @return
 * @throws Exception
 */
public static String getText(String textBits) throws Exception
{
String returnValue="";
if(textBits.length()%8!=0)
{
throw new Exception();
}
String temp="";
for(int i=0;i<=textBits.length()-8;i+=8)
{
temp=textBits.substring(i,i+8);
returnValue+=String.valueOf(Tool.convert(temp));
}

return returnValue;
}

}
//-----------------------------------------------------------------------
package mars.security;public class DecryptHelper {


/**
 * 四位二进制转换为数字
 * @param fourBits
 * @return
 * @throws Exception
 */
public static int getDigit(String fourBits) throws Exception
{
int returnValue=-1;
for(int i=0;i<EncryptHelper.BinaryDigit.length;i++)
{
if(EncryptHelper.BinaryDigit[i].compareTo(fourBits)==0)
{
returnValue=i;
break;
}
}
if(returnValue==-1)
{
throw new Exception();
}
return returnValue;

}


}
//-----------------------------------------------------------------------
package mars.security;public class Encrypt {

public static String getCipherText(String input) throws Exception
{
String returnValue="";
String cipher=convertToDigits(EncryptHelper.convert(input));
char[] chars=cipher.toCharArray();
int i=0;

while(i<chars.length)
{  
returnValue+=EncryptHelper.BinaryDigit[java.lang.Integer.valueOf(String.valueOf((chars[i++])))];
}
return returnValue;
}
 
/**
 * 加密数字序列结果
 * @param bits 
 * @return
 */
public static String convertToDigits(String bits)
{
String returnValue="";
int i=0;
boolean flag=true;
char[] chars=bits.toCharArray();
Node temp=EncryptTree.Instance.getTree().getBinaryTree();

while(i<chars.length)
{
if(chars[i]=='0')//='0'
{
if(temp.getLeft()!=null)
{
flag=false;
temp=temp.getLeft();
}
else
{
flag=true;

}
}
else  //='1'
{
if(temp.getRight()!=null)
{
flag=false;
temp=temp.getRight();
}
else
{
flag=true;
}
} if(flag) //flag==true 从当前开始计算
{
returnValue+=temp.getId();
temp=EncryptTree.Instance.getTree().getBinaryTree();
}
else//flag==false 继续计算
{
i++;
}
}
returnValue+=temp.getId();//补足最后一位计算结果

return returnValue;
}

}
//-----------------------------------------------------------------------

Answer 9

package mars.test;import mars.security.*;public class Test { /**
 * @param args
 */
public static void main(String[] args) { try
{
System.out.println(Encrypt.getCipherText("abc"));
System.out.println(Encrypt.convertToDigits("100110101001"));

System.out.println(Decrypt.getText(
Decrypt.getTextBits("01010110010010000011011001110111011001110011")));
}
catch(Exception ex)
{

}

}}

Answer 10

package mars.security;
import java.util.regex.*;public class Tool {
public enum ValidateType
{
WORDS,//[a-zA-Z_0-9]
CHARS,//[a-zA-Z]
CHAR_OR_DIGIT//[a-zA-Z0-9];
}
/**
 * 将byte转化为二进制序列
 * @param b
 * @return
 */
public static String convert(byte b)
{
String returnValue="";
while(b!=0)
{
returnValue=String.valueOf(b%2)+returnValue;
b/=2;
}

while(returnValue.length()<8)
{
returnValue="0"+returnValue;
}

return returnValue;
}

/**
 * 将二进制字符串转化为byte
 * @param bits
 * @return
 */
public static char convert(String bits) throws Exception
{
char c=0;
if(bits.length()%8!=0)
{
throw new Exception();
}
c=(char)Integer.parseInt(bits, 2);
return c;
}


/**
 * 判断待加密的字符串是否合法
 * @param type 验证类型
 * @param input 待加密的字符串
 * @return true/false  合法 /不合法
 */
public static boolean validateChars(ValidateType type,String input)
{
String validateString=null;
switch(type)
{
case WORDS:
validateString="^\\w+$"; 
break;
case CHARS:
validateString="^[a-zA-Z]+$";
break;
case CHAR_OR_DIGIT:
validateString="^[a-zA-Z0-9]+$";
break;
}

Pattern pattern=  Pattern.compile(validateString);
Matcher matcher=pattern.matcher(input);

return matcher.matches();
}



}

Answer 11

package mars.security;public class Node {


private int id;//这个节点ID不需要的，为了加密速度，特意加这个id
private char data; //0|1|R根结点
private Node left=null;
private Node right=null;


public Node(int id,char data)
{
this.id=id;
this.data=data;
}



public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}

public int getData() {
return data;
}
public void setData(char data) {
this.data = data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}


}

Answer 12

package mars.security;import java.util.LinkedList;public class EncryptTree {
private BinaryTree tree=null;
/*
 * 用于密钥初始化后，数字对应的二进制流的计算
 */
public static LinkedList<String> DigitValue=new LinkedList<String>(); 

public static EncryptTree Instance=new EncryptTree();
private EncryptTree()
{
if(tree==null)
{
DigitValue.add("");//0
DigitValue.add("");//1
DigitValue.add("");//2
DigitValue.add("");//3
DigitValue.add("");//4
DigitValue.add("");//5
DigitValue.add("");//6
DigitValue.add("");//7
DigitValue.add("");//8
DigitValue.add("");//9

/*
 * 这里相当于密钥的初始化，当改变这个树时，加密后的密文就会不同
 * */
Node n1=new Node(1,'R');
Node n2=new Node(2,'0');
Node n3=new Node(3,'1');
Node n4=new Node(4,'0');
Node n5=new Node(5,'1');
Node n6=new Node(6,'0');
Node n7=new Node(7,'1');
Node n8=new Node(8,'0');
Node n9=new Node(9,'1');

n1.setLeft(n2);
n1.setRight(n3);
n2.setLeft(n4);
n2.setRight(n5);
n3.setLeft(n6);
n4.setRight(n7);
n5.setLeft(n8);
n6.setRight(n9);
tree=new BinaryTree(n1);
computeDigitValue(n1);
}
}

public BinaryTree getTree() {
return tree;
}

public void computeDigitValue(Node node)
{
if(node.getLeft()!=null)
{
DigitValue.set(node.getLeft().getId()-1,DigitValue.get(node.getId()-1)+"0");
computeDigitValue(node.getLeft());
}
if(node.getRight()!=null)
{
DigitValue.set(node.getRight().getId()-1,DigitValue.get(node.getId()-1)+"1");
computeDigitValue(node.getRight());
}
}




}

Answer 13

package mars.security;import java.nio.charset.Charset;import mars.security.Tool.ValidateType;public class EncryptHelper {
/*
 * 密文二进制数组
 */
public static String[] BinaryDigit=new String[]{
"0000",
"0001",
"0010",
"0011",
"0100",
"0101",
"0110",
"0111",
"1000",
"1001"
};

/**
 * 将加密完成的数字序列转化为二进制字符串
 * @param digits
 * @return
 * @throws Exception 当录入的数字序列不合法时，会出现转换出错，但是由于是直接调用，不会出现异常情况
 */
public static String convertToCipher(String digits) throws Exception
{
String returnValue="";
char[] chars=digits.toCharArray();
int i=0;

while(i<chars.length)
{  
returnValue+=EncryptHelper.BinaryDigit[java.lang.Integer.valueOf(String.valueOf((chars[i++])))];
}
return returnValue;
}

/**
 * 按照ASCII编码把input转换成bytes数组
 * @param input
 * @return
 * @throws Exception 
 */
public static String convert(ValidateType type,String input) throws Exception
{
String returnValue="";
if(!Tool.validateChars(type,input))
{
throw new Exception("加密字符串不合法！");
}

byte[] bytes=input.getBytes(Charset.forName("ASCII"));

int i=0;
while(i<bytes.length)
{
returnValue+=Tool.convert(bytes[i]);
i++;
}
return returnValue;
}

public static String convert(String input) throws Exception
{
return convert(ValidateType.WORDS,input);
}

}

Answer 14

 这是我的作业， 我还是学生。 大家帮忙看看
import java.util.Scanner;public class Tree {
static Node root = null; enum Direcation {
right, left
} public static int getInt() {
return Integer.parseInt(new Scanner(System.in).next().trim());
} public static void main(String[] args) {
while (true) {
System.out.println("1.增加  2.中序  3.删除  ");
int  = getInt();
switch () {
case 1:
System.out.println("输入节点值");
builderTree(getInt());
break;
case 2:
query(root);
break;
case 3:
System.out.println("输入节点值");
delete(getInt());
break;
case 4:
System.exit(0);
}
}
} public static void builderTree(int i) {
if (root == null) {
root = new Node(i);
return;
}
Node tempRood = root;
while (true) {
if (tempRood.getI() > i) {
if (tempRood.getLeft() != null) {
tempRood = tempRood.getLeft();
} else {
tempRood.setLeft(new Node(i));
break;
}
} else {
if (tempRood.getRight() != null) {
tempRood = tempRood.getRight();
} else {
tempRood.setRight(new Node(i));
break;
}
}
}
} public static void query(Node root) {
if (root != null) {
if (root.getLeft() != null) {
query(root.getLeft());
}
System.out.println(root.getI());
if (root.getRight() != null) {
query(root.getRight());
}
}
} public static void delete(int i) {
if (root != null) {
if (root.getI() == i) {
root = null;
return;
}
Node temp = root;
Node farter = temp;
Direcation dir = null;
while (true) {
if (temp.getI() == i) {
execute(farter, temp, dir);
break;
} else if (temp.getI() > i) {
if (temp.getLeft() == null) {
return;
}
farter = temp;
temp = temp.getLeft();
dir = Direcation.left;
} else if (temp.getI() < i) {
if (temp.getRight() == null) {
return;
}
farter = temp;
temp = temp.getRight();
dir = Direcation.right;
}
}
}
} public static void execute(Node fater, Node son, Direcation dir) {// 删除
if (son.getLeft() == null && son.getRight() == null) {
if (dir == Direcation.left) {
fater.setLeft(null);
} else if (dir == Direcation.right) {
fater.setRight(null);
}
} else if (son.getLeft() != null && son.getRight() == null) {
if (dir == Direcation.left) {
fater.setLeft(son.getLeft());
} else if (dir == Direcation.right) {
fater.setRight(son.getLeft());
}
son.setLeft(null); } else if (son.getLeft() == null && son.getRight() != null) {
if (dir == Direcation.left) {
fater.setLeft(son.getRight());
} else if (dir == Direcation.right) {
fater.setRight(son.getRight());
}
son.setRight(null); } else if (son.getLeft() != null && son.getRight() != null) {
Node unfater = son;
Node unRight = son.getLeft();
while(unRight.getRight()!=null){
unfater = unRight;
unRight = unRight.getRight();
}
if (unfater == son) {
unfater.setLeft(null);
unRight.setRight(son.getRight());
son.setRight(null);
son.setLeft(null);
} else {
unfater.setRight(unRight.getLeft());
unRight.setLeft(son.getLeft());
unRight.setRight(son.getRight());
son.setRight(null);
son.setLeft(null);
}
if (dir == Direcation.left) {
fater.setLeft(unRight);
} else if (dir == Direcation.right) {
fater.setRight(unRight);
}
}
}
}class Node {
private Integer i;
private Node right;
private Node left; public Node getRight() {
return right;
} public void setRight(Node right) {
this.right = right;
} public Node getLeft() {
return left;
} public void setLeft(Node left) {
this.left = left;
} public Node(Integer i) {
this.i = i;
} public Integer getI() {
return i;
}
}