二叉树（二）-----基本代码实现

叁歲伎倆 2022-05-26 01:52 211阅读 0赞

现在我想用代码来实现关于二叉树的一些基础功能。由于二叉树的功能比较多，所以我想多分几篇博客来叙述二叉树的功能。

根据二叉树的结构和性质我们可以发现，二叉树的每个子节点都是其子节点的根节点，所以关于二叉树的很多功能实现都可以通过递归的方式来实现。关于我刚刚开始学习二叉树时，递归的思想让我十分头疼。递归的特点就是虽然代码看起来很简单，但是分析其具体内部实现过程却是十分复杂的。在我学习c++这本书时，遇到的汉诺塔问题，运用的就是递归思想。递归的应用就是栈中的出栈和入栈思想。最外层的方法先进栈，其中调用其本身，这个本身也是一个方法，可以看做方法的内部方法，这个内部方法再进栈。当然这样的进栈不是无休止的，否则就违反了程序的有限性原理。到了最底层满足跳出该方法的条件时，那么最底层的那个方法就会出栈，然后一层一层向上层方法出栈。所以在二叉树的各个方法实现中，我更愿意通过举例来深入详解二叉树所利用的递归思想。

在讲述二叉树的基本性质之前，我需要先对二叉树的整体框架进行一个搭建。

public class BinaryTree {
    	 private TreeNode root = null;
    	
    	 
    	 public BinaryTree(){
    		 root = new TreeNode(1,"A");

public class TreeNode{
    		
    		private int index;
    		
    		private String data;
    		
    		private TreeNode leftChild;
    		
    		private TreeNode rightchild;
    
    		public TreeNode() {
    			super();
    		}
    		public TreeNode(int index, String data) {
    			super();
    			this.index = index;
    			this.data = data;
    			this.leftChild = null;
    			this.rightchild = null;
    		}
    		public int getIndex() {
    			return index;
    		}
    		public void setIndex(int index) {
    			this.index = index;
    		}
    		
    		
    		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;
    		}
    		
    		
    	}

}
    	 }

一个内部类TreeNode以及一些简单的构造方法。

首先我想先来讲述一下二叉树是怎样实现的。首先是二叉树的建立。

在这里我以前序遍历的逆过程来实现二叉树生成。首先我们来看一棵二叉树。

![70][]

这棵二叉树的前序遍历结果为 ABDECF

但是，我们在构建这棵二叉树的同时无法直接这样去构建。我们知道二叉树不是线性结构，我们需要将这课非完全二叉树补全为一个满二叉树

![70 1][]

这样这棵二叉树的遍历结果就是ABD\#\#E\#\#C\#F\#\#。这样我们将这棵满二叉树进行构建即可。

下面是我的实现代码，我将慢慢解析我的代码

public TreeNode createBinaryTree(int size, List<String> list) {
    		if(list.size()==0){
    			return null;
    		}
    		String d = list.get(0);
    		TreeNode node;
    		int index = size - list.size();
    		if(d.equals("#")){
    			node = null;
    			list.remove(0);
    			return node;
    		}
    		node = new TreeNode(index,d);
    		if(index ==0){
    			root = node;
    		}
    		list.remove(0);
    		node.leftChild = createBinaryTree(size,list);//createLeft
    		node.rightchild =createBinaryTree(size,list);//createRight
    		return node;
    	}

首先来解释形参的含义，第一个size是指传入的链表的长度，第二个list是指二叉树的结点值的集合。

第一步如果list的大小为0。说明我们传入了一个空的list。这个时候返回null。终止二叉树的构造。

第二步，如果list的大小不为0.获取list的第一个元素的值，将其赋给d。之后我们声明一个结点，作为每次方法执行的用来定义为根节点的结点。

第三步，这里声明了一个index，这个index是用来定义插入的结点在list中的位置。

第四步，如果d的值为\#，说明这个位置原本的结点应该为空。这个时候我们让node为null，同时list将头元素进行删除并将这个结点返回。即这个createBinaryTree方法的本次执行结束(注意，是本次执行而不是整棵二叉树的构造)。

第五步， 如果d不为\#，那么对这个结点进行初始化。

第六步，如果index的值为0，说明这个结点是头结点。那么将root指向该结点。之后将该结点从list中删除（至于为什么每次都是list.remove(0)，很简单，因为每次插入的都是新的list的第一个结点，因为它前面的结点都在之前的插入中remove了）

第七步，之后就是很重要的递归创建二叉树了，首先递归创建左子树，然后是递归创建右子树。

看似很简单但是分析起来却十分复杂。

下面就是我对这个构建过程的分析过程，由于递归的思想是类似的，在接下来的深度计算和结点计算中就不在同样叙述。

![70 2][]

接下来我们来讨论一下怎样求出一棵树的深度

private int getDepth(TreeNode node) {
    		if(node ==null){
    			return 0;
    		}else{
    			int i = getDepth(node.leftChild);//lengthStatement1
    			int j = getDepth(node.rightchild);//lengthStatement2
    			return (i>j)?i+1:j+1;
    		}
    		
    	}

同样是递归的思想，我们知道深度其实求一棵子树的最大层次。所以现在我来讲述一下这个算法。形参是这棵树的根节点，如果根节点是null则返回0.

其次首先试求根节点的左子树的深度，这个递归会一直执行下去知道传入的参数为null返回0。同理对右子树的遍历也是如此。

至于return (i>j)?i+1:j+1;这条语句。我们来简要分析一下，首先肯定是选择i和j中较大的内个。那么为什么要+1呢？每一层向上递归时，实际上都是向更高层次的出栈。所以要+1.

接下来是求一棵树的所有结点数。

private int getSize(TreeNode node) {
    		if(node ==null){
    			return 0;
    		}
    		return 1+getSize(node.leftChild)+getSize(node.rightchild);
    	}

分析过程如上不再赘述。

下一篇专栏我将讲述关于树的三种遍历方式。

[70]: /images/20220526/4e5a90dba4b9429188df0d8058317b89.png
[70 1]: /images/20220526/3f7b394b0f4143619c18875c16d14e5e.png
[70 2]: /images/20220526/5b181651dfaa44faa80cefad9dc9e39e.png