二叉树的分类
满二叉树：二叉树的所有叶子节点都在最后一层，并且节点总数为2^n-1，n为二叉树的层数。
完全二叉树：二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续。
顺序存储二叉树：从数据存储来看，数组存储方式和树的存储方式可以互相转换。把树结构的元素用数组存储，使其依旧可以按照树的前、中、后序遍历的顺序遍历此数组。 顺序存储二叉树的特点： 1.顺序存储二叉树通常只考虑完全二叉树。 2.数组中下标为n的元素的左子节点下标为2n+1。 3.数组中下标为n的元素的右子节点下标为2n+2。 4.数组中下标为n的元素的父节点下标为(n-1)/2。
线索化二叉树：n个节点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向该节点在某种遍历次序下的前驱和后继节点的指针，这种附加的指针称为线索。这种加上线索的二叉链表称为线索链表，加上线索的二叉树称为线索二叉树，根据线索性质不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树。
二叉树的前、中、后序遍历
package tree.binaryTree
;
public class BinaryTree
{
//根节点
private Node root
;
public BinaryTree
(Node root
) {
this.root
= root
;
}
//前序遍历对外提供的方法
public void preOrderTraversal
(){
if
(root
!=null
)
preOrder
(root
);
else
System.out.println
("树为空！");
}
//中序遍历对外提供的方法
public void midOrderTraversal
(){
if
(root
!=null
)
midOrder
(root
);
else
System.out.println
("树为空！");
}
//后序遍历对外提供的方法
public void postOrderTraversal
(){
if
(root
!=null
)
postOrder
(root
);
else
System.out.println
("树为空！");
}
//前序遍历的实现
private void preOrder
(Node node
){
//输出节点内容
System.out.println
(node.toString
());
if
(node.getLeft
()!=null
){
//左子树不为空，递归前序遍历左子树
preOrder
(node.getLeft
());
}
if
(node.getRight
()!=null
) {
//右子树不为空，递归前序遍历右子树
preOrder
(node.getRight
());
}
}
//中序遍历的实现
private void midOrder
(Node node
){
if
(node.getLeft
()!=null
){
//左子树不为空，递归前序遍历左子树
midOrder
(node.getLeft
());
}
//输出节点内容
System.out.println
(node.toString
());
if
(node.getRight
()!=null
) {
//右子树不为空，递归前序遍历右子树
midOrder
(node.getRight
());
}
}
//后序遍历的实现
private void postOrder
(Node node
){
if
(node.getLeft
()!=null
){
//左子树不为空，递归前序遍历左子树
postOrder
(node.getLeft
());
}
if
(node.getRight
()!=null
) {
//右子树不为空，递归前序遍历右子树
postOrder
(node.getRight
());
}
//输出节点内容
System.out.println
(node.toString
());
}
}
