树是我们常用的数据结构，如堆、二叉搜索树、B树等，它们都有自己的特点，使得我们在程序设计中常常使用。下面就说说树的基础知识，树、二叉树和完全二叉树。并用java使用链表描述完全二叉树。
1、树
一棵树是一个非空的有限元素的集合，其中一个元素为根其余的元素组成树的子树。这个定义并不是那么的直观，在图论中，树的定义是无环的连通图。例如下图三棵树：
在画一棵树时，每个元素都代表一个节点。树根画在上面，其子树画在下面，在树中节点之间的关系有孩子、父母、兄弟、孙子、祖父、祖先、后代。如上图中最右边的树，1是2、3的父母；2和3是兄弟；2、3是1的孩子，4、5、6、7是1的后代。在树中没有孩子的元素称为叶子（右图中的4、5、6、7）数据结构 完全二叉树 数据结构 树、二叉树、完全二叉树，树根是唯一没有父母的元素。
一棵树的高度或深度是树的层数。如上三图的高度都是3.
树中一个元素的度是其孩子的个数，如上右图中1的度是2.一棵树的度是元素度的最大值。
2、二叉树
一棵二叉树是有限个元素的集合（可以为空）。当二叉树非空时，其中有一个元素称为根，余下（如果有的话）被划分成两棵二叉树，分别称为左子树和右子树。
二叉树与树的区别：二叉树的每个元素都恰好有两棵子树（其中一个或两个可能为空）。而树的每个元素可有任意数量的子树。在二叉树中，每个元素都是有序的，也就是说有左子树和右子树之分。而树的子树是无序的。
二叉树的特性：一棵二叉树有n个元素，n>0,它有n-1条边。一棵二叉树的高度为h，h>=0,它至少有h个元素，最多有2的h次方-1个元素。一棵二叉树有n个元素，n>0，它的高度最大为n，最小为log2（n+1）取上整。当高度为h的二叉树恰好含有2的h次方-1个元素时称为满二叉树，如上图右图就是一棵满二叉树。
3、完全二叉树
对高度为h的满二叉树的最后一层从左到右编号1到2的h-1次方，删除i（0
当完全二叉树含有n个元素时，从根开始编号1，最后一个元素编号为n，新添加的元素编号为n+1。这是完全二叉树的数组描述的依据。另外还可以寻找出最后一个节点或新建节点到根的路径。
4、二叉树的操作：
常用的操作：确定高度，确定元素数目，复制，显示或打印二叉树，比较两个二叉树是否相同，删除整棵树。以上的操作都可以使用二叉树的遍历来完成，遍历是指每个元素仅被访问一次，访问一个元素就意味着可以对该实施任何操作。二叉树的遍历有前序遍历、中序遍历、后序遍历和层次遍历以上图的完全二叉树的最左图为例数据结构 完全二叉树，各种遍历的结果为：
前序遍历：1 2 4 5 3 6 7
中序遍历：4 2 5 1 6 3 7
后序遍历：4 5 2 6 7 3 1
层次遍历：1 2 3 4 5 6 7
前序遍历是先访问根再访问左子树最后是右子树。中序遍历是先访问左子树的再访问根最后是右子树。后序遍历是先访问左子树再访问右子树最后是根，中序遍历是一层一层的从左到右访问每一个元素。
5、二叉树的描述
二叉树的描述可以由数组描述，也可以使用链表描述。在数组描述中，二叉树的元素索引和数组元素的对应如下：二叉树的根元素对应数组的1位置，左子树节点对应2，依次对应如下。
使用链表描述二叉树是常用的描述方式数据结构 完全二叉树，因为数组描述有些节点没有子树，造成浪费空间，除此之外使用二叉树常常动态插入和删除。
6、链表描述的完全二叉树
树节点定义：
package Structure;
//定义树节点
public class treeNode{
protected int element;//节点域
protected treeNode leftChild,//左子树指针和右子树指针
rightChild;
//无参构造函数，构建空树
public treeNode(){
leftChild=rightChild=null;
}
//新建节点，插入末尾
public treeNode(int theElement){
element=theElement;
leftChild=rightChild=null;
}
//赋值构造函数，替换节点
public treeNode(int theElement,treeNode theleftchild,
treeNode therightchild){
element=theElement;
leftChild=theleftchild;
rightChild=therightchild;}
};
二叉树类：
package Structure;
import java.util.LinkedList;
public class BinaryTree {
private treeNode root;
private int size;
//无参构造函数，构建空树
public BinaryTree(){
root=null;
size=0;
}
//返回根节点
public treeNode getRoot(){
return root;
}
//二叉树的大小
<p>![完全二叉树结点计算_完全二叉树的高度_数据结构 完全二叉树][4]
public int size(){
return size;
}
//插入函数
public void insert(int theElement) {
if (root == null) {
root = new treeNode(theElement);
size++;
} else {
int a = size + 1, i = 0;
int[] b = new int[20];
while (a > 1) {
i++;
b[i] = a % 2;
a = a / 2;
}
treeNode p = root;
while (i > 1) {
if (b[i] == 0)
p = p.leftChild;
else
p = p.rightChild;
i--;
}
if (b[1] == 0)
p.leftChild = new treeNode(theElement);
else
p.rightChild = new treeNode(theElement);
size++;
}
}
//打印访问特定节点域
public void visit(treeNode t) {
System.out.print(t.element + " ");
}
  ![数据结构 完全二叉树_完全二叉树的高度_完全二叉树结点计算][5]
//前序遍历
public void preOrder(treeNode t) {
if (t != null) {
visit(t);
preOrder(t.leftChild);
preOrder(t.rightChild);
}
}
//中序遍历
public void inOrder(treeNode t) {
if (t != null) {
inOrder(t.leftChild);
visit(t);
inOrder(t.rightChild);
}
}
//后序遍历
public void postOrder(treeNode t) {
if (t != null) {
postOrder(t.leftChild);
postOrder(t.rightChild);
visit(t);
}
}
//层次遍历
public void levelOrder(treeNode t){
LinkedList q=new LinkedList();
while(t!=null){
visit(t);
if(t.leftChild!=null)
q.add(t.leftChild);
if(t.rightChild!=null)
  ![完全二叉树的高度_数据结构 完全二叉树_完全二叉树结点计算][6]
q.add(t.rightChild);
if(q.size()!=0)
t=q.getFirst();
else
return;
q.removeFirst();
}
}
//高度函数
public int height(treeNode t){
if(t==null)
return 0;
int hl=height(t.leftChild);
int hr=height(t.rightChild);
if(hl>hr)
return ++hl;
else
return ++hr;
}
}</p>
测试代码：
package Test;
import Structure.BinaryTree;
import Structure.treeNode;
public class BinaryTreeTest {
public static void main(String[] args) {
BinaryTree tree=new BinaryTree();
<p>![完全二叉树的高度_完全二叉树结点计算_数据结构 完全二叉树][7]
tree.insert(1);
tree.insert(2);
tree.insert(3);
tree.insert(4);
tree.insert(5);
tree.insert(6);
tree.insert(7);
treeNode t=tree.getRoot();
System.out.print("前序遍历：");
tree.preOrder(t);
System.out.println();
System.out.print("中序遍历：");
tree.inOrder(t);
System.out.println();
System.out.print("后序遍历：");
tree.postOrder(t);
System.out.println();
System.out.print("层次遍历：");
tree.levelOrder(t);
System.out.println();
System.out.println("高度："+tree.height(t));
System.out.println("大小："+tree.size());
}
}</p>
输出：
前序遍历：1 2 4 5 3 6 7
中序遍历：4 2 5 1 6 3 7
后序遍历：4 5 2 6 7 3 1
层次遍历：1 2 3 4 5 6 7
高度：3
大小：7
文章来源:https://blog.csdn.net/vamesary/article/details/60476863