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

树的分类（按存储结构）

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

链式存储

一些特别的二叉根：

完全二叉树，平衡二叉树（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 < j) ? j + 1 : i + 1; } } public int Size() { // 求结点数 return Size(root); } public int Size(TreeNode subTree) { if (subTree == null) return 0; else { return 1 + Size(subTree.getLeftChild()) + Size(subTree.getRightChild()); } } 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.getLeftChild() == element || subTree.getRightChild() == element) //找到, 返回父结点地址 return subTree; TreeNode p; //先在左子树中找，如果左子树中没有找到，才到右子树去找 if ((p = Parent(subTree.getLeftChild(), element)) != null) //递归在左子树中搜索 return p; else //递归在左子树中搜索 return Parent(subTree.getRightChild(), element); } public TreeNode LeftChild(TreeNode element) { //返回左子树 return (element != null) ? element.getLeftChild() : null; } public TreeNode RightChild(TreeNode element) { //返回右子树 return (element != null) ? element.getRightChild() : null; } public TreeNode getRoot() { //取得根结点 return root; } public void destroy(TreeNode subTree) { //私有函数: 删除根为subTree的子树 if (subTree != null) { destroy(subTree.getLeftChild()); //删除左子树 destroy(subTree.getRightChild()); //删除右子树 //delete subTree; //删除根结点 subTree = null; } } public void Traverse(TreeNode subTree) { System.out.println("key:" + subTree.getKey() + "--name:" + subTree.getData()); Traverse(subTree.getLeftChild()); Traverse(subTree.getRightChild()); } public void PreOrder(TreeNode subTree) { //先根 if (subTree != null) { visted(subTree); PreOrder(subTree.getLeftChild()); PreOrder(subTree.getRightChild()); } } public void InOrder(TreeNode subTree) { //中根 if (subTree != null) { InOrder(subTree.getLeftChild()); visted(subTree); InOrder(subTree.getRightChild()); } } public void PostOrder(TreeNode subTree) { //后根 if (subTree != null) { PostOrder(subTree.getLeftChild()); PostOrder(subTree.getRightChild()); visted(subTree); } } public void LevelOrder(TreeNode subTree) { //水平遍边 } public boolean Insert(TreeNode element){ //插入 return true; } public boolean Find(TreeNode element){ //查找 return true; } public void visted(TreeNode subTree) { subTree.setVisted(true); System.out.println("key:" + subTree.getKey() + "--name:" + subTree.getData()); } public static void main(String[] args) { BinaryTree bt = new BinaryTree(); bt.createBinTree(bt.root); System.out.println("the size of the tree is " + bt.Size()); System.out.println("the height of the tree is " + bt.Height()); System.out.println("*******先根(前序)[ABDECF]遍历*****************"); bt.PreOrder(bt.root); System.out.println("*******中根(中序)[DBEACF]遍历*****************"); bt.InOrder(bt.root); System.out.println("*******后根(后序)[DEBFCA]遍历*****************"); bt.PostOrder(bt.root); } }

结果输出：

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)

希望本文对学习JAVA程序设计的同学有所帮助。