树的基本概念简介
一般树 ： 任意一个结点的子节点的个数不受限制，则称为一般树，子节点可以有多个。
二叉树：任意一个节点的子节点的个数最多有两个，且子节点的个数不能更改。
树由结点和边组成
树中除根节点外，每一个节点都有一个父结点，但是可以有多个子节点。
根结点没有父结点
二叉树.png
专业术语
节点 ： 父节点 子节点
度： 结点拥有子树的个数
叶子节点：没有子节点的节点
边 : 一个节点到另一个节点的距离
树的深度：节点的层数， 根节点默认为第一层。
有序 ：树的左右位置不能改变。
二叉树的排序
二叉树的遍历分为四种，分别是先序遍历，中序遍历，后序遍历和按层遍历。
- 先序遍历：根节点---左子树---右子树 （NLR）
- 中序遍历：左子树---根节点--右子树 （LNR）
- 后序遍历：左子树---右子树---根节点 (LRN)
- 按层遍历：从上到下，从左到右，依次排序
上图经过排序后的顺序：
先序遍历：A-B-D-E-C-F-G
中序遍历：D-B-E-A-F-C-G
后序遍历：D-E-B-F-G-C-A
二叉树2.png
先序遍历：G-D-A-F-E-M-H-Z
中序遍历：A-D-E-F-G-H-M-Z
后序遍历：A-E-F-D-H-Z-M-G
按层遍历：G-D-M-A-F-H-Z-E
代码实现
/**
* 二叉树排序
* Created by zhangshuliang on 2017/9/15.
*/
public class BinaryTreeSort {
// 承载跟节点的集合
public static List nodeList = new LinkedList();
public static int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
/**
* 节点类
*/
static class Node {
int data; // 父节点
Node leftNode; // 左子节点
Node rightNode; // 右子节点
public Node(int newData) {
leftNode = null;
rightNode = null;
data = newData;
}
}
/**
* 创建二叉树
*/
public static void createBinTree() {
for (int i = 0; i < array.length; i++) {
nodeList.add(new Node(array[i]));
}
for (int i = 0; i < array.length / 2 - 1; i++) {
// 左右子节点赋值
((Node) nodeList.get(i)).leftNode = (Node) nodeList.get(i * 2 + 1);
((Node) nodeList.get(i)).rightNode = (Node) nodeList.get(i * 2 + 2);
}
// 最后一个跟节点可能没有右子节点，所以单独拿出来处理
int lastParentPoint = array.length / 2 - 1;
((Node) nodeList.get(lastParentPoint)).leftNode = (Node) nodeList.get(lastParentPoint * 2 + 1);
if (lastParentPoint % 2 == 1) {
((Node) nodeList.get(lastParentPoint)).rightNode = (Node) nodeList.get(lastParentPoint * 2 + 2);
}
}
/**
* 先序遍历
*/
public static void preBinOrder(Node node) {
Log.e("TAG",node.data+"");
if (node.leftNode!=null){
preBinOrder(node.leftNode);
}
if (node.rightNode!=null){
preBinOrder(node.rightNode);
}
}
/**
* 中序遍历
*/
public static void midleBinOrder(Node node) {
if (node.leftNode!=null){
midleBinOrder(node.leftNode);
}
Log.e("TAG",node.data+"");
if (node.rightNode!=null){
midleBinOrder(node.rightNode);
}
}
/**
* 后序遍历
*/
public static void lastBinOrder(Node node) {
if (node.leftNode!=null){
lastBinOrder(node.leftNode);
}
if (node.rightNode!=null){
lastBinOrder(node.rightNode);
}
Log.e("TAG",node.data+"");
}
}
Activity中调用：
BinaryTreeSort.createBinTree();
BinaryTreeSort.preBinOrder((BinaryTreeSort.Node) BinaryTreeSort.nodeList.get(0));
BinaryTreeSort.midleBinOrder((BinaryTreeSort.Node) BinaryTreeSort.nodeList.get(0));
BinaryTreeSort.lastBinOrder((BinaryTreeSort.Node) BinaryTreeSort.nodeList.get(0));
输出结果：
排序结果.png
public class BinaryTree {
/**
* 二叉树的链式存储
*
* @author WWX
*/
private TreeNode root = null;
public BinaryTree() {
root = new TreeNode(1, "rootNode(A)");
}
/**
* 创建一棵二叉树
* @param root
* @author WWX
*/
public void createBinTree(TreeNode root) {
TreeNode newNodeB = new TreeNode(2, "B");
TreeNode newNodeC = new TreeNode(3, "C");
TreeNode newNodeD = new TreeNode(4, "D");
TreeNode newNodeE = new TreeNode(5, "E");
TreeNode newNodeF = new TreeNode(6, "F");
root.leftChild = newNodeB;
root.rightChild = newNodeC;
root.leftChild.leftChild = newNodeD;
root.leftChild.rightChild = newNodeE;
root.rightChild.rightChild = newNodeF;
}
//树的高度
public int height() {
return height(root);
}
//节点个数
public int size() {
return size(root);
}
private int height(TreeNode subTree) {
if (subTree == null)
return 0;//递归结束：空树高度为0
else {
int i = height(subTree.leftChild);
int j = height(subTree.rightChild);
return (i < j) ? (j + 1) : (i + 1);
}
}
private int size(TreeNode subTree) {
if (subTree == null) {
return 0;
} else {
return 1 + size(subTree.leftChild) + size(subTree.rightChild);
}
}
//返回双亲结点
public TreeNode parent(TreeNode element) {
return (root == null || root == element) ? null : parent(root, element);
}
public TreeNode parent(TreeNode subTree, TreeNode element) {
if (subTree == null)
return null;
if (subTree.leftChild == element || subTree.rightChild == element)
//返回父结点地址
return subTree;
TreeNode p;
//现在左子树中找，如果左子树中没有找到，才到右子树去找
if ((p = parent(subTree.leftChild, element)) != null)
//递归在左子树中搜索
return p;
else
//递归在右子树中搜索
return parent(subTree.rightChild, element);
}
public TreeNode getLeftChildNode(TreeNode element) {
return (element != null) ? element.leftChild : null;
}
public TreeNode getRightChildNode(TreeNode element) {
return (element != null) ? element.rightChild : null;
}
public TreeNode getRoot() {
return root;
}
//在释放某个结点时，该结点的左右子树都已经释放，
//所以应该采用后续遍历，当访问某个结点时将该结点的存储空间释放
public void destroy(TreeNode subTree) {
//删除根为subTree的子树
if (subTree != null) {
//删除左子树
destroy(subTree.leftChild);
//删除右子树
destroy(subTree.rightChild);
//删除根结点
subTree = null;
}
}
public void traverse(TreeNode subTree) {
System.out.println("key:" + subTree.key + "--name:" + subTree.data);
traverse(subTree.leftChild);
traverse(subTree.rightChild);
}
//前序遍历
public void preOrder(TreeNode subTree) {
if (subTree != null) {
visted(subTree);
preOrder(subTree.leftChild);
preOrder(subTree.rightChild);
}
}
//中序遍历
public void inOrder(TreeNode subTree) {
if (subTree != null) {
inOrder(subTree.leftChild);
visted(subTree);
inOrder(subTree.rightChild);
}
}
//后续遍历
public void postOrder(TreeNode subTree) {
if (subTree != null) {
postOrder(subTree.leftChild);
postOrder(subTree.rightChild);
visted(subTree);
}
}
//前序遍历的非递归实现
public void nonRecPreOrder(TreeNode p) {
Stack stack = new Stack();
TreeNode node = p;
while (node != null || stack.size() > 0) {
while (node != null) {
visted(node);
stack.push(node);
node = node.leftChild;
}
while (stack.size() > 0) {
node = (TreeNode) stack.pop();
node = node.rightChild;
}
}
}
//中序遍历的非递归实现
public void nonRecInOrder(TreeNode p) {
Stack stack = new Stack();
TreeNode node = p;
while (node != null || stack.size() > 0) {
//存在左子树
while (node != null) {
stack.push(node);
node = node.leftChild;
}
//栈非空
if (stack.size() > 0) {
node = (TreeNode) stack.pop();
visted(node);
node = node.rightChild;
}
}
}
//后序遍历的非递归实现
public void noRecPostOrder(TreeNode p) {
Stack stack = new Stack();
TreeNode node = p;
while (p != null) {
//左子树入栈
for (; p.leftChild != null; p = p.leftChild) {
stack.push(p);
}
//当前结点无右子树或右子树已经输出
while (p != null && (p.rightChild == null || p.rightChild == node)) {
visted(p);
//纪录上一个已输出结点
node = p;
if (stack.empty())
return;
p = (TreeNode) stack.pop();
}
//处理右子树
stack.push(p);
p = p.rightChild;
}
}
public void visted(TreeNode subTree) {
subTree.isVisted = true;
System.out.println("key:" + subTree.key + "--name:" + subTree.data);
}
/**
* 二叉树的节点数据结构
*/
private class TreeNode {
private int key = 0;
private String data = null;
private boolean isVisted = false;
private TreeNode leftChild = null;
private TreeNode rightChild = null;
/**
* @param key 层序编码
* @param data 数据域
*/
public TreeNode(int key, String data) {
this.key = key;
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
}
}
