JAVA 实现二叉树（链式存储结构）

本篇文章主要介绍用JAVA 实现二叉树,并提供实例.对二叉树数据结构很好的学习实践,有需要的朋友可以参考下

二叉树的分类（按存储结构）

树的分类（按存储结构）

　顺序存储（用数组表示（静态二叉树））
　　　　链式存储

一些特别的二叉根：

完全二叉树，平衡二叉树（AVL），线索二叉树，三叉的（带父亲的指针）
　　　　　　　　　二叉搜索树或者叫二叉　查找树（BST）

所用二叉树如下图所示：

二叉树的Java实现（链式存储结构）

 class TreeNode { private int key = 0; private String data = null; private boolean isVisted = false; private TreeNode leftChild = null; private TreeNode rightChild = null; public TreeNode(){ } public TreeNode(int key, String data){ this.key = key; this.data = data; this.leftChild = null; this.rightChild = null; } public int getKey() { return key; } public void setKey(int key) { this.key = key; } public String getData() { return data; } public void setData(String data) { this.data = data; } public TreeNode getLeftChild() { return leftChild; } public void setLeftChild(TreeNode leftChild) { this.leftChild = leftChild; } public TreeNode getRightChild() { return rightChild; } public void setRightChild(TreeNode rightChild) { this.rightChild = rightChild; } public boolean isVisted() { return isVisted; } public void setVisted(boolean isVisted) { this.isVisted = isVisted; } } public class BinaryTree { private TreeNode root = null; public BinaryTree() { root = new TreeNode(1, "rootNode(A)"); } 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.setLeftChild(newNodeB); root.setRightChild(newNodeC); root.getLeftChild().setLeftChild(newNodeD); root.getLeftChild().setRightChild(newNodeE); root.getRightChild().setRightChild(newNodeF); } public boolean IsEmpty() { // 判二叉树空否 return root == null; } public int Height() { // 求树高度 return Height(root); } public int Height(TreeNode subTree) { if (subTree == null) return 0; //递归结束：空树高度为0 else { int i = Height(subTree.getLeftChild()); int j = Height(subTree.getRightChild()); return (i

结果输出：
the size of the tree is 6
the height of the tree is 3
*******先根(前序)[ABDECF]遍历*****************
key:1--name:rootNode(A)
key:2--name:B
key:4--name:D
key:5--name:E
key:3--name:C
key:6--name:F
*******中根(中序)[DBEACF]遍历*****************
key:4--name:D
key:2--name:B
key:5--name:E
key:1--name:rootNode(A)
key:3--name:C
key:6--name:F
*******后根(后序)[DEBFCA]遍历*****************
key:4--name:D
key:5--name:E
key:2--name:B
key:6--name:F
key:3--name:C
key:1--name:rootNode(A)