二叉树是一种非常重要的数据结构，它同时具有数组和链表各自的特点，在实际工作中，我们也会经常用到二叉树知识点，那java如何设计二叉树类结构?接下来我们就来给大家讲解一下。
一、二叉树的结构
二叉树是每个节点最多有两个子树的树结构
二、几种类型的二叉树
(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。 (3)平衡二叉树——平衡二叉树又被称为AVL树(区别于AVL算法)，它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
三、二叉树的实现代码
package javaTest;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
public class BinaryTree
{
private int[] array = {
1
, 2
, 3
, 4
, 5
, 6
, 7
, 8
, 9
};
private static List nodeList = null;
private static class Node
{
public int data;
public Node leftChild;
public Node rightChild;
Node(int newDate)
{
data = newDate;
leftChild = null;
rightChild = null;
}
}
public void createBinTree()
{
nodeList = new LinkedList();
//将数组转换成Node组成的一个list
for (int nodeIndex = 0; nodeIndex nodeList.add(new Node(array[nodeIndex]));
//System.out.println(array[nodeIndex]);
//System.out.println(nodeList.get(nodeIndex).data);
}
for (int i = 0; i nodeList.get(i)
.leftChild = nodeList.get(2 * i + 1); nodeList.get(i)
.rightChild = nodeList.get(2 * i + 2);
}
int lastParentIndex = array.length / 2 - 1;
nodeList.get(lastParentIndex)
.leftChild = nodeList.get(2 * lastParentIndex + 1);
if (array.length % 2 == 1)
{
nodeList.get(lastParentIndex)
.rightChild = nodeList.get(2 * lastParentIndex + 2);
}
}
/**
* 先序遍历
*
* 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已
*
* @param node
* 遍历的节点
*/
public static void preOrderTraverse(Node node)
{
if (node == null)
return;
System.out.print(node.data + " ");
preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);
}
public static void nrPreOrderTraverse(Node node)
{
Stack stack = new Stack();
while (node != null || !stack.isEmpty())
{
while (node != null)
{
System.out.print(node.data + " ");
stack.push(node);
node = node.leftChild;
}
node = stack.pop();
node = node.rightChild;
}
}
/**
* 中序遍历
*
* 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已
*
* @param node
* 遍历的节点
*/
public static void inOrderTraverse(Node node)
{
if (node == null)
return;
inOrderTraverse(node.leftChild);
System.out.print(node.data + " ");
inOrderTraverse(node.rightChild);
}
public static void nrInOrderTraverse(Node node)
{
Stack stack = new Stack();
while (node != null || !stack.isEmpty())
{
while (node != null)
{
stack.push(node);
node = node.leftChild;
}
node = stack.pop();
System.out.print(node.data + " ");
node = node.rightChild;
}
}
/**
* 后序遍历
*
* 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已
*
* @param node
* 遍历的节点
*/
public static void postOrderTraverse(Node node)
{
if (node == null)
return;
postOrderTraverse(node.leftChild);
postOrderTraverse(node.rightChild);
System.out.print(node.data + " ");
}
public static void nrPostOrderTraverse(Node node)
{
Stack stack = new Stack();
Node preNode = null; //表示最近一次访问的节点
while (node != null || !stack.isEmpty())
{
while (node != null)
{
stack.push(node);
node = node.leftChild;
}
node = stack.peek();
if (node.rightChild == null || node.rightChild == preNode)
{
System.out.print(node.data + " ");
node = stack.pop();
preNode = node;
node = null;
}
else
{
node = node.rightChild;
}
}
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.createBinTree();
Node root = nodeList.get(0);
//System.out.println(root.data);
System.out.println("先序遍历：");
preOrderTraverse(root);
System.out.println();
System.out.println("中序遍历：");
inOrderTraverse(root);
System.out.println();
System.out.println("后序遍历：");
postOrderTraverse(root);
System.out.println();
System.out.println("非递归中序遍历：");
nrInOrderTraverse(root);
System.out.println();
System.out.println("非递归先序遍历：");
nrPreOrderTraverse(root);
System.out.println();
System.out.println("非递归后序遍历：");
nrPostOrderTraverse(root);
System.out.println();
}
}二叉树的特点总结：
(1)树执行查找、删除、插入的时间复杂度都是O(logN);
(2)遍历二叉树的方法包括前序、中序、后序;
(3)非平衡树指的是根的左右两边的子节点的数量不一致;
(4) 在非空二叉树中，第i层的结点总数不超过 , i>=1;
(5)深度为h的二叉树最多有个结点(h>=1)，最少有h个结点;
(6)对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;
在实际工作中，二叉树的知识点是很重要的，所以设计二叉树类的结构一定要多琢磨，掌握好其中的逻辑。最后大家如果想要了解更多java实例知识，敬请关注奇Q工具网。
推荐阅读：
arcgis怎么导出json?ArcGis如何建立/链接企业级地理数据库?