二叉樹的分類（按存儲結(jié)構(gòu)）
樹的分類（按存儲結(jié)構(gòu)）
順序存儲（用數(shù)組表示（靜態(tài)二叉樹））
鏈式存儲
一些特別的二叉根：
完全二叉樹，平衡二叉樹（AVL），線索二叉樹，三叉的（帶父親的指針）
二叉搜索樹或者叫二叉 查找樹（BST）
所用二叉樹如下圖所示：
二叉樹的Java實現(xiàn)（鏈式存儲結(jié)構(gòu)）
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){ //手動的創(chuàng)建（結(jié)構(gòu)如圖所示） 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; //遞歸結(jié)束：空樹高度為0 else { int i = Height(subTree.getLeftChild()); int j = Height(subTree.getRightChild()); return (i < j) ? j + 1 : i + 1; } } public int Size() { // 求結(jié)點數(shù) 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) { //返回雙親結(jié)點 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) //找到, 返回父結(jié)點地址 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() { //取得根結(jié)點 return root; } public void destroy(TreeNode subTree) { //私有函數(shù): 刪除根為subTree的子樹 if (subTree != null) { destroy(subTree.getLeftChild()); //刪除左子樹 destroy(subTree.getRightChild()); //刪除右子樹 //delete subTree; //刪除根結(jié)點 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); }} 結(jié)果輸出：
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程序設(shè)計的同學有所幫助。
新聞熱點
疑難解答
