（一）、树型结构
1.树的定义:
树是一种数据结构，它是由n(n≥0)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个结点有零个或多个子结点(n>=0)；没有父结点的结点称为根节点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。（一对多的关系，。没有节点这一说）
2.树需要注意的地方
1.一个树只能有一个根结点，但可以有多个子结点。
2.子结点的个数没有限制，但是子结点一定不能相交互。
3.结点的分类:（树的度 节点的度）
树的结点包含一个数据元素及若干个指向其子树的分支。结点拥有的子树数称为结点的度（Degree）。度为0的结点称为叶结点（Leaf）或终端结点；度不为0的结点称为非终端结点或分支支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。
4.结点间的关系:
结点的子树的根称为该结点的孩子（Child），相应的，该结点称为孩子的双亲（Parent）（注意是双亲，不是单亲）。同一个双亲的孩子之间互称兄弟（Sibling）。结点的祖先是从根到该结点所经分支上的所有结点。以某结点为根的子树中的任一结点都称为该结点的子孙。
5.树的其他相关概念:
结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度（Depth）或高度。
如果将树中结点的各子树看成从左至右是有次序的，不能互换，则称该树为有序树，否则为无序树。
森林（Forest）是m（m>=0）棵互不相交的树的集合。
根结点没有父结点，其他的结点都有一个父结点， 子结点 ：父结点的下一层。 叶子结点：没有子结点的结点。 结点的度：结点的子结点数。 树的度：最多的叶结点的度。 结点的层：根结点为1，依次类推。 高度 ：树的最大层。 森林：
(二)、二叉树
二叉树的定义:
二叉树的每个结点的子结点最多只有两个子树的树结构。也就是说树的度为2
满二叉树的定义:
每一层的结点树都达到最大值。
完全二叉树的定义:
设二叉树的深度为k,除第k层外，其他各层(1~（k-1）)的结点数都达到最大值。第k层所有的结点都连续集中在最左边，这就是完全二叉树。
1.二叉树的创建:
创建结点:
public class Node{ //数值 Object item; //左右子结点 Node left; Node right; public Node(Object item){ this.item=item; } }
创建树:
public void CreateTree() { //创建根节点 root=new Node(1); //第二层 //创建左子结点 Node Left=new Node(2); //创建右子结点 Node Right=new Node(3); //进行关联 root.left=Left; root.right=Right; //第三层 Node Left2=new Node(4); //创建右子结点 Node Right2=new Node(5); //进行关联 root.left.left=Left2; root.left.right=Right2; //第三层 Node Left3=new Node(6); //创建右子结点 Node Right3=new Node(7); //进行关联 root.right.left=Left3; root.right.right=Right3; }
前序遍历:
public void ShowTree(Node node){ if(node==null){ return; } //遍历根节点 System.out.println(node.item); //遍历左子树 ShowTree(node.left); //遍历右子树 ShowTree(node.right); }
中序遍历:
public void MidShowTree(Node node){ if(node==null){ return; } //遍历左子树 MidShowTree(node.left); //遍历根节点 System.out.println(node.item); //遍历右子树 MidShowTree(node.right); }
后序遍历:
public void FinShowTree(Node node){ if(node==null){ return; } //遍历左子树 FinShowTree(node.left); //遍历右子树 FinShowTree(node.right); //遍历根节点 System.out.println(node.item); }
层次:
public void LeveTree(Node node){ //创建队列; ArrayDeque <Node> ad=new ArrayDeque<>(10); //加入根节点 ad.add(node); while (!ad.isEmpty()) { Node n=ad.poll(); System.out.println(n.item); //左子树放到队列 if(n.left!=null){ ad.add(n.left); } //将右子树放到队列中去 if(n.right!=null){ ad.add(n.right); } } }
全部代码:
1.1.全部代码:
import java.awt.event.KeyEvent; import java.awt.event.KeyListener; import java.sql.SQLOutput; import java.util.*; import java.awt.*; import java.lang.Math; public class hello { public static void main(String []avgs){ Tree t=new Tree(); t.CreateTree(); t.ShowTree(t.root); System.out.println("=============="); t.MidShowTree(t.root); System.out.println("=============="); t.FinShowTree(t.root); System.out.println("=============="); t.LeveTree(t.root); System.out.println("=============="); Tree.Node result=t.Select(t.root,13); if(result==null){ System.out.println("无相等的结果"); }else{ System.out.println("有相等的结果为:"+result.item); } System.out.println("==========="); t.Delete(t.root,1); t.LeveTree(t.root); } }
