数据结构Java实现04---树及其相关操作

时间:2022-04-23 11:57:36

首先什么是树结构?

树是一种描述非线性层次关系的数据结构,树是n个数据结点的集合,这些集结点包含一个根节点,根节点下有着互相不交叉的子集合,这些子集合便是根节点的子树。

树的特点

  • 在一个树结构中,有且仅有一个结点没有直接前驱,它就是根节点。
  • 除了根节点,其他结点有且只有一个直接前驱
  • 每个结点可以有任意多个直接后继

树的名词解释

  • 结点的度:一个结点包含子树的数量。
  • 树的度:该树所有结点中最大的度。
  • 兄弟结点:具有同一父结点的结点称为兄弟结点。
  • 树的深度(高度):叶子结点的深度(高度)为1,根节点深度(高度)最高;
  • 层数:从树根开始算,树根是第一层,以此类推。
  • 森林:由多个树组成

只说干货,现在直接复习最重要的——二叉树

二叉树

二叉树是一种超级超级超级重要的数据结构!也是树表家族最为基础的结构
先看看定义:二叉树嘛,每个结点最多只能有二棵子树,二叉树的子树有左右之分,次序不能颠倒
再看看完全二叉树的性质:

  • 第i层至多有 2的i次方减一 个结点
  • 深度为k的二叉树至多有2k-1个结点
  • 任意二叉树,度为0的节点数=度为2的节点数+1;
  • 如果i为父亲的编号,则孩子的编号为2i和2i+1;
  • 如果孩子编号为n,父亲结点编号为k/2,向下取整

关于树的度:
二叉树中连接节点和节点的线就是度
上面说过——度为0的节点数为度为2的节点数加1,即n0=n2+1
这个公式的推理方法如下:
设:
k:总度数
k+1:总节点数
n0:度为0的节点
n1:度为1的节点
n2:度为二的节点
根据二叉树中度和节点的守衡原理,可列出以下一组方程:
k=n2*2+n1;
k+1=n2+n1+n0;
根据方程可以求出n0=n2+1

基本概念不说,研究一下二叉树的遍历

二叉树的遍历

首先,我们看看前序、中序、后序遍历的特性:
前序遍历: (根——左——右)
1.访问根节点
2.前序遍历左子树
3.前序遍历右子树
中序遍历: (左——根——右)
1.中序遍历左子树
2.访问根节点
3.中序遍历右子树
后序遍历: (左——右——根)
1.后序遍历左子树
2.后序遍历右子树
3.访问根节点

要知道:
中序遍历是很重要的一个判断参照!如果只给我们前序遍历和后序遍历的结果,我们将无法推导出唯一的树。
给我们前序遍历和中序遍历,我们可以推出中序
给我们后序遍历和中序遍历,我们可以推出中序


好了,已经写了很多但是并没有拿出来什么真干货,接下来用代码写一下关于树的操作,这里先讲好——对于“树”这个运行结构,最重要的概念是“递归”,要想把树的概念理解好,必须先培养递归的思想。我向这篇文章:写递归函数的正确思想学习了一下,真的写的很棒,条理清晰而且有详有略。在这之后我就希望通过自己亲手敲代码的方式去学习,但是研究了两天,依然进展比较一般,最后通过研究各方博客的C代码,从而找到了思路。不再说废话了,这东西,必须通过自己动手敲才能有收获,好的接下来就要拿代码出来了。这里感谢这片文章二叉树题目实现
以下则是用java代码去写的,注解已经很详细,没有分开写,时不时有新体会也会去添加或修改:


二叉树类:

相关操作:
 * 1.获取节点数
 * 2.求深度
 * 3. 前序遍历,中序遍历,后序遍历
 * 4.分层遍历二叉树(按层次从上往下,从左往右)
 * 5.求二叉树第K层的节点个数
 * 6.求二叉树中叶子节点的个数
 * 7. 判断两棵二叉树是否结构相同

 

实现:

  1 package com.myutil.tree1;
  2 
  3 /*
  4  * 1.获取节点数
  5  * 2.求深度
  6  * 3. 前序遍历,中序遍历,后序遍历
  7  * 4.分层遍历二叉树(按层次从上往下,从左往右)
  8  * 5.求二叉树第K层的节点个数
  9  * 6.求二叉树中叶子节点的个数
 10  * 7. 判断两棵二叉树是否结构相同
 11  */
 12 import java.util.LinkedList;
 13 import java.util.Queue;
 14 
 15 class TreeNode{
 16     int key=0;
 17     String data=null;
 18     boolean isVisited=false;
 19     
 20     TreeNode leftChild=null;
 21     TreeNode rightChild=null;
 22     
 23     public TreeNode(int key,String data) {
 24         this.key=key;
 25         this.data=data;
 26         this.isVisited=false;
 27         this.leftChild=null;
 28         this.rightChild=null;
 29     }
 30 }
 31 
 32 
 33 
 34 public class BinaryTree {
 35     
 36     TreeNode root=null;
 37     
 38     public BinaryTree() {
 39         root=new TreeNode(1, "A");
 40     }
 41     
 42     //创建二叉树bt,树由节点构成
 43     public void createBinTree(TreeNode root) {
 44         TreeNode newNodeB=new TreeNode(2, "B");
 45         TreeNode newNodeC=new TreeNode(3, "C");
 46         TreeNode newNodeD=new TreeNode(4, "D");
 47         TreeNode newNodeE=new TreeNode(5, "E");
 48         TreeNode newNodeF=new TreeNode(6, "F");
 49         
 50         root.leftChild=newNodeB;
 51         root.rightChild=newNodeC;
 52         root.leftChild.leftChild=newNodeD;
 53         root.leftChild.rightChild=newNodeE;
 54         root.rightChild.rightChild=newNodeF;
 55     }
 56     
 57     //创建二叉树bt2,树由结点构成
 58     public void createBinTree2(TreeNode root){
 59         TreeNode newNodeB = new TreeNode(2,"B");
 60         TreeNode newNodeC = new TreeNode(3,"C");
 61         TreeNode newNodeD = new TreeNode(4,"D");
 62         TreeNode newNodeE = new TreeNode(5,"E");
 63         //填充它
 64         root.leftChild = newNodeB;
 65         root.rightChild = newNodeC;
 66         root.leftChild.leftChild = newNodeD;
 67         root.leftChild.rightChild = newNodeE;
 68     }
 69 
 70     
 71     //访问节点,输出节点,便于我们查看效果
 72     public void visitNode(TreeNode node) {
 73         System.out.println(node.data+" ");
 74     }
 75     
 76     
 77     //1.获取节点数
 78     //递归解法:
 79     //(1)如果二叉树为空,节点个数为0
 80     //(2)如果二叉树不为空,二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1
 81     public int size() {
 82         return size(root);
 83     }
 84     
 85     //通过递归求size
 86     public int size(TreeNode subtree) {
 87         if (subtree==null) {
 88             return 0;
 89         }else {
 90             return 1+size(subtree.leftChild)+size(subtree.rightChild);
 91         }
 92     }
 93     
 94     //2.求深度
 95     //递归解法:
 96     //(1)如果二叉树为空,二叉树的深度为0
 97     //(2)如果二叉树不为空,二叉树的深度 = max(左子树深度, 右子树深度) + 1
 98     public int getDepth(TreeNode root) {
 99         if (root==null) {
100             return 0;
101         }else {
102             int depthLeft=getDepth(root.leftChild);
103             int depthRight=getDepth(root.rightChild);
104             return depthLeft>depthRight?(depthLeft+1):(depthRight+1);
105         }
106     }
107     
108     //3. 前序遍历,中序遍历,后序遍历
109     //a.前序遍历
110     //前序遍历递归解法:
111     //(1)如果二叉树为空,空操作
112     //(2)如果二叉树不为空,访问根节点,前序遍历左子树,前序遍历右子树
113     public void preOrderTraverse(TreeNode root) {
114         if (root!=null) {
115             visitNode(root);
116             preOrderTraverse(root.leftChild);
117             preOrderTraverse(root.rightChild);
118         }
119     }
120     
121     //b.中序遍历
122     //中序遍历递归解法
123     //(1)如果二叉树为空,空操作。
124     //(2)如果二叉树不为空,中序遍历左子树,访问根节点,中序遍历右子树
125     
126     public void inOrderTraverse(TreeNode root) {
127         if (root!=null) {
128             inOrderTraverse(root.leftChild);
129             visitNode(root);
130             inOrderTraverse(root.rightChild);
131         }
132     }
133     
134     //c.后序遍历
135     //后序遍历递归解法
136     //(1)如果二叉树为空,空操作。
137     //(2)如果二叉树不p为空,后序遍历左子树,后序遍历右子树,访问根节点,
138     public void postOrderTraverse(TreeNode root) {
139         if (root!=null) {
140             postOrderTraverse(root.leftChild);
141             postOrderTraverse(root.rightChild);
142             visitNode(root);
143         }
144     }
145     
146     //4.分层遍历二叉树(按层次从上往下,从左往右)
147     //相当于广度优先搜索,使用队列实现。队列初始化,将根节点压入队列。
148     //当队列不为空,进行如下操作:弹出一个节点,访问,若左子节点或右子节点不为空,将其压入队列。
149     public void levelTraverse(TreeNode root) {
150         if (root==null) {
151             return;
152         }
153         Queue<TreeNode> queue=new LinkedList<>();
154         //让根节点入队(队列:先进先出)
155         queue.offer(root);
156         while (!queue.isEmpty()) {
157             //让元素出队
158             TreeNode node=queue.poll();
159              //访问它 这里就是用visit方法输出看效果~~
160             visitNode(node);
161             if (node.leftChild!=null) {
162                 queue.offer(node.leftChild);
163             }
164             if (node.rightChild!=null) {
165                 queue.offer(node.rightChild);
166             }
167         }
168         return;
169     }
170     
171     //5.求二叉树第K层的节点个数
172     //递归解法:
173     //(1)如果二叉树为空或者k<1返回0
174     //(2)如果二叉树不为空并且k==1,返回1
175     //(3)如果二叉树不为空且k>1,返回左子树中k-1层的节点个数与右子树k-1层节点个数之和
176     public int getNodeNumKthLevel(TreeNode root,int k) {
177         if (root==null||k<1) {
178             return 0;
179         }else if (k==1) {
180             return 1;
181         }else {
182             int leftNum=getNodeNumKthLevel(root.leftChild, k-1);
183             int rightNum=getNodeNumKthLevel(root.rightChild, k-1);
184             return leftNum+rightNum;
185         }
186     }
187     
188     //6.求二叉树中叶子节点的个数
189     // 递归解法:
190     //(1)如果二叉树为空,返回0
191     //(2)如果二叉树不为空且左右子树为空,返回1
192     //(3)如果二叉树不为空,且左右子树不同时为空,返回左子树中叶子节点个数加上右子树中叶子节点个数
193     public int getLeafNodeNum(TreeNode root) {
194         if (root==null) {
195             return 0;
196         }else if (root.leftChild==null&&root.rightChild==null) {
197             return 1;
198         }else {
199             int leftNum=getLeafNodeNum(root.leftChild);
200             int rightNum=getLeafNodeNum(root.rightChild);
201             return leftNum+rightNum;
202         }
203     }
204     
205     
206     //7. 判断两棵二叉树是否结构相同
207     //不考虑数据内容。结构相同意味着对应的左子树和对应的右子树都结构相同。
208     //递归解法:
209     //(1)如果两棵二叉树都为空,返回真
210     //(2)如果两棵二叉树一棵为空,另一棵不为空,返回假
211     //(3)如果两棵二叉树都不为空,如果对应的左子树和右子树都同构返回真,其他返回假
212     public boolean StructureCmp(TreeNode root1,TreeNode root2) {
213         if (root1==null&&root2==null) {
214             return true;
215         }else if (root1==null||root2==null) {
216             return false;
217         }else {
218             boolean leftResult=StructureCmp(root1.leftChild, root2.leftChild);
219             boolean rightResult=StructureCmp(root1.rightChild, root2.rightChild);
220             return leftResult&&rightResult;
221         }
222     }
223 }

 

 

测试类:

 

 1 package com.myutil.tree1;
 2 
 3 public class Main {
 4     public static void main(String[] args) {
 5         BinaryTree bt = new BinaryTree();
 6         BinaryTree bt2 = new BinaryTree();
 7         /*
 8             由初始化的时候可知:我创建了一个这样的树,供查看写的方法是否正确
 9             这棵树起名为bt:           这棵树起名为bt2 供比较
10                       A                 A
11                     /  \               / \
12                    B   C              B  C
13                   /\    \            /\
14                  D E     F          D  E
15         */
16         bt.createBinTree(bt.root);
17         bt2.createBinTree2(bt2.root);
18 
19         //1.看结点数
20         System.out.println("1.树的结点个数为:" + bt.size(bt.root));
21         //2.看深度
22         System.out.println("2.树的深度为:"+bt.getDepth(bt.root));
23         //3. 前序遍历,中序遍历,后序遍历
24         System.out.print("3-1.先序遍历:");
25         bt.preOrderTraverse(bt.root);
26         System.out.println();
27         
28 
29         System.out.print("3-2.中序遍历:");
30         bt.inOrderTraverse(bt.root);
31         System.out.println();
32 
33         System.out.print("3-3.后序遍历:");
34         bt.postOrderTraverse(bt.root);
35         System.out.println();
36 
37         //4.将二叉树用层次遍历
38         System.out.print("4.二叉树层次遍历:");
39         bt.levelTraverse(bt.root);
40         System.out.println();
41 
42         //5.二叉树K层有多少个结点:由上图绘制可知:0层没有,1层有一个根节点,第二层有俩,第三次有仨
43         System.out.println("5.二叉树K层结点个数:");
44         System.out.println("    当K=0时有"+bt.getNodeNumKthLevel(bt.root,0)+"个结点");
45         System.out.println("    当K=1时有"+bt.getNodeNumKthLevel(bt.root,1)+"个结点");
46         System.out.println("    当K=2时有"+bt.getNodeNumKthLevel(bt.root,2)+"个结点");
47         System.out.println("    当K=3时有"+bt.getNodeNumKthLevel(bt.root,3)+"个结点");
48 
49         //6.求二叉树中叶子节点的个数
50         System.out.print("6.二叉树叶子节点个数:");
51         System.out.println(bt.getLeafNodeNum(bt.root));
52 
53         //7.比较两个二叉树相不相同
54         System.out.println("7.测试两树结构是否相同:");
55         System.out.println("    b1和b1:"+bt.StructureCmp(bt.root,bt.root));
56         System.out.println("    b1和b2:"+bt.StructureCmp(bt.root,bt2.root));
57     }
58 }

 

相关连接:轻松搞定面试中的二叉树题目

     java数据结构与算法之树基本概念及二叉树(BinaryTree)的设计与实现