JAVA 實(shí)現(xiàn)二叉樹(鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))
二叉樹的分類(按存儲(chǔ)結(jié)構(gòu))
樹的分類(按存儲(chǔ)結(jié)構(gòu))
順序存儲(chǔ)(用數(shù)組表示(靜態(tài)二叉樹))
鏈?zhǔn)酱鎯?chǔ)
一些特別的二叉根:
完全二叉樹,平衡二叉樹(AVL),線索二叉樹,三叉的(帶父親的指針)
二叉搜索樹或者叫二叉 查找樹(BST)
所用二叉樹如下圖所示:
二叉樹的Java實(shí)現(xiàn)(鏈?zhǔn)酱鎯?chǔ)結(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){ //手動(dòng)的創(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é)點(diǎn)數(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é)點(diǎn) 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é)點(diǎn)地址 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é)點(diǎn) return root; } public void destroy(TreeNode subTree) { //私有函數(shù): 刪除根為subTree的子樹 if (subTree != null) { destroy(subTree.getLeftChild()); //刪除左子樹 destroy(subTree.getRightChild()); //刪除右子樹 //delete subTree; //刪除根結(jié)點(diǎn) 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)
希望本文對(duì)學(xué)習(xí)JAVA程序設(shè)計(jì)的同學(xué)有所幫助。
相關(guān)文章
AsyncHttpClient的ConnectionSemaphore方法源碼流程解讀
這篇文章主要為大家介紹了AsyncHttpClient的ConnectionSemaphore方法源碼流程解讀,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-12-12Jersey Restful接口如何獲取參數(shù)的問題
這篇文章主要介紹了Jersey Restful接口如何獲取參數(shù)的操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-06-06java web SpringMVC后端傳json數(shù)據(jù)到前端頁(yè)面實(shí)例代碼
本篇文章主要介紹了java web SpringMVC后端傳json數(shù)據(jù)到前端頁(yè)面實(shí)例代碼,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下。2017-03-03Java實(shí)現(xiàn)代碼塊耗時(shí)測(cè)算工具類
這篇文章主要為大家介紹了如何利用Java語(yǔ)言編寫一個(gè)工具類,用來(lái)測(cè)算代碼塊的耗時(shí),同時(shí)還能顯示進(jìn)度,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-05-05Java模擬棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)的基本示例講解
這篇文章主要介紹了Java模擬棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)的基本示例,棧的后進(jìn)先出和隊(duì)列的先進(jìn)先出是數(shù)據(jù)結(jié)構(gòu)中最基礎(chǔ)的知識(shí),本文則又對(duì)Java實(shí)現(xiàn)棧和隊(duì)列結(jié)構(gòu)的方法進(jìn)行了細(xì)分,需要的朋友可以參考下2016-04-04Spring多數(shù)據(jù)源導(dǎo)致配置失效的解決
這篇文章主要介紹了Spring多數(shù)據(jù)源導(dǎo)致配置失效的解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-01-01jar命令修改jar包中的application.yml配置文件
本文主要介紹了jar命令修改jar包中的application.yml配置文件,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-08-08使用Feign設(shè)置Token鑒權(quán)調(diào)用接口
這篇文章主要介紹了使用Feign設(shè)置Token鑒權(quán)調(diào)用接口,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-03-03