建立二叉树的两种方法。

1.数组表示法

利用数组来存储二叉树的元素。
建立二叉树的规则：小于等于父节点的值放在左子节点，大于父节点的值放在右子节点。


代码如下：

/***

• 需求：使用一维数组存储二叉树

  
  



• 步骤：

  
  



• 1、查看原始数据的个数（8个），从而制定二叉树层级（4层），得到满二叉树节点个数（15个）

  
  



• 2、二叉树节点（15个）为一维数组，全设置为0

  
  



• 3、循环遍历原始数据，第一个值为树根

  
  



• 4、第二个值与父节点比较，如果大于树根，则往右子树比较，如果数组内的值小于或等于树根，则往左子树比较

  
  



• 5、【循环】步骤4，直到形成二叉树

  
  





• 备注：左节点的坐标等于父节点的坐标2，右节点的坐标等于父节点的坐标2+1
  
  /
  
  package 建立二叉树_数组表示法;
  
  import java.io.;
  
  public class demoBinTree{
  
  public static void main(String args[]) throws IOException
  
  {
  
  int i,level;
  
  int data[]={6,3,5,9,7,8,4,2}; /原始数组/
  
  int btree[]=new int[16];
  
  for(i=0;i<16;i++) btree[i]=0;
  
  System.out.print(“原始数组内容: \n”);
  
  for(i=0;i<8;i++)
  
  System.out.print("["+data[i]+"] “);
  
  System.out.println();
  
  for(i=0;i<8;i++) /把原始数组中的值逐一对比/
  
  {
  
  System.out.println(“i==>”+i);
  
  for(level=1;btree[level]!=0;) /比较树根及数组内的值/
  
  {
  
  System.out.println(“levele==>”+level+” btree[level]==>"+btree[level]);

  if(data[i]>btree[level]) /*如果数组内的值大于树根，则往右子树比较*/
level=level*2+1;
else /*如果数组内的值小于或等于树根，则往左子树比较*/
level=level*2;
} /*如果子树节点的值不为0，则再与数组内的值比较一次*/
System.out.println();
btree[level]=data[i]; /*把数组值放入二叉树*/
System.out.print("level后==>"+level+" ");
}
System.out.print("二叉树内容：\n");
for (i=1;i<16;i++)
System.out.print("["+btree[i]+"] ");
System.out.print("\n");
}

  

}

/*自己的困惑

• 1.level为什么从一开始。


• 2.不清楚整个循环是如何进行的。


• 3.不清楚 for(level=1;btree[level]!=0;)这条语句，


• 4.不清楚每次循环之后level的值是多少，也就是不明白循环。


• 总结：


• 就是每次从根节点开始与数组的值比较，大于根节点与其右子树比较，再把右子树当做子树的根节点继续比较，直到遇到叶子节点就结束循环(小于或等于与左子树比较，后面步骤类似)。


• */

2.链表表示法

顾名思义，用链表来存储二叉树，最简的二叉链表。
代码如下：


/program description==/

//自己对于这个算法还是不太了解，主要是建树的那两个地方。那两个指针是如何工作的，里面存放的是什么。那个参数是如何传递的。

//以上都设计到了程序的运行次序以及构造方法的知识，自己还需要去学习，这里就不深究，留个疑问先。

package 建立二叉树_列表表示法;

import java.io.*;

//二叉树结点类声明

class TreeNode{

int value;

TreeNode left_Node;

TreeNode right_Node;

//TreeNode构造函数

public TreeNode(int value){

this.value = value;

this.left_Node = null;

this.right_Node = null;

}

}

//二叉树类声明。

class BinaryTree{

public TreeNode rootNode; //二叉树的根节点。

public BinaryTree(int[]data){ //构造函数，利用参数建立二叉树

for(int i = 0;i
Add_Node_To_Tree(data[i]);

}

}

void Add_Node_To_Tree(int value){

TreeNode currentNode = rootNode;

if(rootNodenull){ //建立树根

rootNode = new TreeNode(value);

return;

}

//建立二叉树。

while(true){

if(value
if(currentNode.left_Nodenull){

currentNode.left_Node = new TreeNode(value);

return;

}

else currentNode = currentNode.left_Node;

}

else{

if(currentNode.right_Node==null){ //在右子树。

currentNode.right_Node = new TreeNode(value);

return;

}

else currentNode = currentNode.right_Node;

}

}

}

}

public class demoBinaryTree {

//主函数。

public static void main(String[] args)throws IOException {

int ArraySize = 10;

int tempdata;

int [] cOntent= new int [ArraySize];

BufferedReader keyin = new BufferedReader(new InputStreamReader(System.in));

System.out.println(“请连续输入”+ArraySize+“个数据”);

for(int i = 0;i
System.out.println(“请输入第”+(i+1)+“个数据”);

tempdata = Integer.parseInt(keyin.readLine());

content[i] = tempdata; //将值传递给数组。

}

new BinaryTree(content); //将数组的值传递给二叉树。

System.out.println("=以链表的形式建立二叉树，成功!!!=");

}

}