devbox
羊村懒王
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

java数据结构----树的实现_java树形结构实现

作者：羊村懒王 | 2024-04-20 12:02:29

赞

踩

java树形结构实现

目录

一、树结构存在的原因

二、树的示意图

三、树的种类

 四、二叉树的代码实现

4.1、节点类

4.2、有序二叉树的遍历

 4.3、构建有序二叉树

 4.4、递归实现二叉树

4.5、递归遍历二叉树

4.6、有序二叉树的删除

 4.6.1、叶子结点的删除

 4.6.2、删除只有一个子树的节点

 4.6.3、删除有两个子树的节点

 4.6.4、节点删除代码实现

一、树结构存在的原因

1、数组存储方式分析
优点：通过下表方式访问元素，速度快。对于有序数组没还可以使用二分查找提高检索速度。
缺点：如果要检索某一个具体值，效率比较低下
2、链式存储方式分析
优点：在一定程度上对数组存储方式进行优化（比如插入一个节点，只需要将插入节点，链接到链表当中可删除的效率也很好）。
缺点：在进行检索时，效率仍然比较低，比如（检索某个数值，需要从头结点开始遍历）
3、树存储方式分析
能提高数据存储，读取的效率，比如利用二叉排序树，既可以保证数据的检索速度。同时也可以保证数据的插入，删除，修改的速度。

二、树的示意图

三、树的种类

 1.树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树
2.二叉树的子节点分为左节点和右节点

 3.如果二叉树的所有叶子节点都在最后一层并且总结点数 = 2^n-1，(n为层数)，则我们称为满二叉数。

 4.如果二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。

 四、二叉树的代码实现

4.1、节点类

  1. public class TreeNode {
  2.     private TreeNode leftTreeNode;
  3.     private TreeNode rightTreeNode;
  4.     private Integer value;
  5.  
  6.     public Integer getValue() {
  7.         return value;
  8.     }
  9.  
  10.     public void setValue(Integer value) {
  11.         this.value = value;
  12.     }
  13.  
  14.     public TreeNode(Integer value){
  15.         this.value = value;
  16.     }
  17.  
  18.     public TreeNode getLeftTreeNode() {
  19.         return leftTreeNode;
  20.     }
  21.  
  22.     public void setLeftTreeNode(TreeNode leftTreeNode) {
  23.         this.leftTreeNode = leftTreeNode;
  24.     }
  25.  
  26.     public TreeNode getRightTreeNode() {
  27.         return rightTreeNode;
  28.     }
  29.  
  30.     public void setRightTreeNode(TreeNode rightTreeNode) {
  31.         this.rightTreeNode = rightTreeNode;
  32.     }
  33.  
  34.     @Override
  35.     public String toString() {
  36.         return "TreeNode{" +
  37.                 "leftTreeNode=" + leftTreeNode +
  38.                 ", rightTreeNode=" + rightTreeNode +
  39.                 ", value=" + value +
  40.                 '}';
  41.     }
  42. }

4.2、有序二叉树的遍历

 4.3、构建有序二叉树

  1. //树管理类
  2. public class BinaryTree {
  3. 	//构建有序二叉树
  4. 	TreeNode root;
  5. 	public void insert(int value) {
  6. 		//新建节点
  7. 		TreeNode newNode=new TreeNode(value);
  8. 		if(root==null) {
  9. 			root=newNode;
  10. 		}else {
  11. 			//定义游标来遍历树
  12. 			TreeNode currentNode=root;
  13. 			//定义一个游标指向currentNode的前一个
  14. 			TreeNode parentNode=null;
  15. 			while(true) {
  16. 				parentNode=currentNode;
  17. 				if(newNode.getValue()>currentNode.getValue()) {
  18. 					currentNode=currentNode.getRightTreeNode();
  19. 					if(currentNode==null) {
  20. 						//数据插入
  21. 						parentNode.setRightTreeNode(newNode);
  22. 						return;
  23. 					}
  24. 				}else {
  25. 					currentNode=currentNode.getLeftTreeNode();
  26. 					if(currentNode==null) {
  27. 						//数据插入
  28. 						parentNode.setLeftTreeNode(newNode);
  29. 						return;
  30. 					}
  31. 				}
  32. 			}
  33. 		}
  34. 		
  35. 	}

 4.4、递归实现二叉树

  1. //递归插入二叉树节点
  2. 	// 递归出口和递归表达式
  3.     // f(node,value) = f(node.left,value)     node.getLeftTreeNode == null;
  4.     // = f(node.right,value)    node.getRightTreeNode == null;
  5. 	public void insertDiGui(TreeNode node,int value) {
  6. 		//创建节点
  7. 		TreeNode newNode=new TreeNode(value);
  8. 		if(root==null) {
  9. 			root=newNode;
  10. 			return;
  11. 		}
  12. 		if(node.getValue()>newNode.getValue()) {
  13. 			if(node.getLeftTreeNode()!=null) {
  14. 				insertDiGui(node.getLeftTreeNode(), value);
  15. 			}else {
  16. 				node.setLeftTreeNode(newNode);
  17. 			}
  18. 		}else {
  19. 			if(node.getRightTreeNode()!=null) {
  20. 				insertDiGui(node.getRightTreeNode(), value);
  21. 			}else {
  22. 				node.setRightTreeNode(newNode);
  23. 			}
  24. 		}
  25. 	}

4.5、递归遍历二叉树

先中后序遍历：

  1. //二叉树的遍历-----深度优先遍历------前中后序遍历
  2. 	//先序遍历
  3. 	public void beforeOrder(TreeNode treeNode) {
  4. 		if(treeNode==null) {
  5. 			return;
  6. 		}
  7. 		System.out.println(" "+treeNode.getValue()+" ");
  8. 		beforeOrder(treeNode.getLeftTreeNode());
  9. 		beforeOrder(treeNode.getRightTreeNode());
  10. 	}
  11. 	//中序遍历
  12. 	public void midOrder(TreeNode treeNode) {
  13. 		if(treeNode==null) {
  14. 			return;
  15. 		}
  16. 		afterOrder(treeNode.getLeftTreeNode());
  17. 		System.out.println(" "+treeNode.getValue()+" ");
  18. 		afterOrder(treeNode.getRightTreeNode());
  19. 	}
  20. 	//后序遍历
  21. 	public void afterOrder(TreeNode treeNode) {
  22. 		if(treeNode==null) {
  23. 			return;
  24. 		}
  25. 		afterOrder(treeNode.getLeftTreeNode());
  26. 		afterOrder(treeNode.getRightTreeNode());
  27. 		System.out.println(" "+treeNode.getValue()+" ");
  28. 	}

4.6、有序二叉树的删除

 4.6.1、叶子结点的删除

 4.6.2、删除只有一个子树的节点

 4.6.3、删除有两个子树的节点

 4.6.4、节点删除代码实现

  1. /**
  2.          * 删除节点
  3.      * @param node  删的的树
  4.      * @param value 删除的值
  5.      */
  6. 	public void delNode(TreeNode node,int value) {
  7. 		if(node==null) {
  8. 			System.out.println("这是一颗空树");
  9. 			return;
  10. 		}
  11. 		//找到要删除的节点
  12. 		TreeNode targetNode=search(node, value);
  13. 		if(targetNode==null) {
  14. 			return;
  15. 		}
  16. 		//判断这棵树是不是只有一个节点
  17. 		if(node.getLeftTreeNode()==null&&node.getRightTreeNode()==null) {
  18. 			root=null;
  19. 			return;
  20. 		}
  21. 		//找到要删除节点的父节点
  22. 		TreeNode parent=SearchParent(node, value);
  23. 		//删除叶子节点
  24. 		if(targetNode.getLeftTreeNode()==null&&targetNode.getRightTreeNode()==null) {
  25. 			// 确定targetNode是parentNode的左子树还是右子树
  26. 			if(parent.getLeftTreeNode()!=null&&parent.getLeftTreeNode().getValue()==value) {
  27. 				parent.setLeftTreeNode(null);
  28. 			}else if(parent.getRightTreeNode()!=null && parent.getRightTreeNode().getValue() == value){ //右子节点
  29.                 parent.setRightTreeNode(null);
  30.             }
  31. 		//删除两个子树的节点
  32. 		}else if(targetNode.getLeftTreeNode()!= null && targetNode.getRightTreeNode()!=null){   
  33.             int minValue = delRightTreeMin(targetNode.getRightTreeNode());
  34.             targetNode.setValue(minValue);
  35. 			
  36. 		}else {//删除只有一个子树的节点
  37.             //要删除的节点有左孩子
  38.             if(targetNode.getLeftTreeNode()!=null){
  39.                 if(parent.getLeftTreeNode()!=null && parent.getLeftTreeNode().getValue() == value){
  40.                     //targetNode是parent节点的左子树
  41.                     parent.setLeftTreeNode(targetNode.getLeftTreeNode());
  42.                 }else {
  43.                     //targetNode是parent节点的右子树
  44.                     parent.setRightTreeNode(targetNode.getLeftTreeNode());
  45.                 }
  46.             }else {//要删除的节点有右孩子
  47.                 if(parent.getRightTreeNode()!=null && parent.getRightTreeNode().getValue() == value){
  48.                     //targetNode是parent节点的左子树
  49.                     parent.setLeftTreeNode(targetNode.getRightTreeNode());
  50.                 }else {
  51.                     //targetNode是parent节点的右子树
  52.                     parent.setRightTreeNode(targetNode.getRightTreeNode());
  53.                 }
  54.             }
  55.         }
  56. 	}
  57. 	/**
  58.      * 查找要删除的节点
  59.      * @param node
  60.      * @param value
  61.      * @return
  62.      */
  63. 	//找到要删除的节点
  64. 	public TreeNode search(TreeNode node,int value) {
  65. 		if(value==node.getValue()) {
  66. 			return node;
  67. 		}else if(value<node.getValue()) {
  68. 			if(node.getLeftTreeNode()==null) {
  69. 				return null;
  70. 			}
  71. 			return search(node.getLeftTreeNode(), value);
  72. 		}else {
  73. 			if(node.getRightTreeNode()==null) {
  74. 				return null;
  75. 			}
  76. 			return search(node.getRightTreeNode(), value);
  77. 		}
  78. 	}
  79. 	/**
  80.      * 找到要删除节点的父节点
  81.      * @param node
  82.      * @param value
  83.      * @return
  84.      */
  85. 	public TreeNode SearchParent(TreeNode node,int value) {
  86. 		if(node.getLeftTreeNode()!=null&&node.getLeftTreeNode().getValue()==value||
  87.           (node.getRightTreeNode()!=null && node.getRightTreeNode().getValue() == value)) {
  88. 			return node;
  89. 		}else {
  90. 			if(node.getLeftTreeNode()!=null&&value<node.getValue()) {
  91. 				return SearchParent(node.getLeftTreeNode(), value);
  92. 			}else if(node.getRightTreeNode()!=null&&value>node.getValue()) {
  93. 				return SearchParent(node.getRightTreeNode(), value);
  94. 			}else {
  95. 				return null;
  96. 			}
  97. 		}
  98. 	}
  99. 	/**
  100.      * 右子树的最小值
  101.      * @param node
  102.      * @return
  103.      */
  104. 	public int delRightTreeMin(TreeNode node) {
  105. 		//定义指针
  106. 		TreeNode current=node;
  107. 		while(current.getLeftTreeNode()!=null) {
  108. 			current=current.getLeftTreeNode();
  109. 		}
  110. 		delNode(root, current.getValue());
  111. 		return current.getValue();
  112. 	}
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/457210
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号