Java数据结构与算法

Java数据结构与算法

目录

树结构基础部分

数组存储方式的分析

链式存储方式的分析

树存储方式的分析

二叉树

常用术语

概念

说明

代码实现

运行效果

---

树结构基础部分

为什么需要树这种数据结构?

数组存储方式的分析

 优点:通过下标方式访问元素，速度快，对于有序数组，还可使用二分查找提高检索速度

缺点:如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低

链式存储方式的分析

 

优点:在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好)。

缺点:在进行检索时，效率仍然很低，比如(检索某个值，需要从头节点开始遍历)

树存储方式的分析

能提高数据存储，读取的效率，比如利用二叉排序树，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。

 分析一把以二叉排序树来存储数据的效率

（1）查找12，经过两次比较就找到12结点

（2）添加13，很快

（3）删除1结点

二叉树 常用术语

1)节点

2）根节点

3）父节点

4）子节点

5）叶子节点（没有子节点的节点）

6）节点的权（节点值）

7）路径（从root节点找到该节点的路线）

8）层

9）子树

10）树的高度(最大层数)

11）森林：多颗子树构成森林

概念

1）树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树

2）二叉树的子节点分为左节点和右节点

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

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

说明

使用前序，中序和后序对下面的二叉树进行遍历。

分析二叉树的前序，中序和后序的遍历步骤

1.创建一棵二叉树

2.前序遍历

2.1先输出当前节点

2.2如果右子节点不为空，则递归继续前序遍历

3.中序遍历

3.1如果当前节点的左子节点不为空，则递归中序遍历

3.2输出当前节点

3.2如果当前节点的右子节点不为空，则递归中序遍历

3.3如果右子节点不为空，则递归继续前序遍历

4.后序遍历

3.1如果当前节点的左子节点不为空，则递归后序遍历

3.2如果当前节点的右子节点不为空，则递归后序遍历

3.3输出当前节点

代码实现

package tree;

public class BinaryTreeDemo {

	public static void main(String[] args) {
		//先需要创建一棵二叉树
		BinaryTree binaryTree=new BinaryTree();
		//创建需要的结点
		Heronode root=new Heronode(1, "宋江");
		Heronode node2=new Heronode(2, "吴用");
		Heronode node3=new Heronode(3, "卢俊义");
		Heronode node4=new Heronode(4, "林冲");
		Heronode node5=new Heronode(5, "关胜");
		
		//说明我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树
		root.setLeft(node2);
		root.setRight(node3);
		node3.setRight(node4);
		node3.setLeft(node5);
		binaryTree.setRoot(root);
		
		//测试
		System.out.println("前序遍历");//1,2,3,5,4
		binaryTree.preOrder();
		
		System.out.println("中序遍历");//2,1,5,3,4
		binaryTree.infixOrder();
		
		System.out.println("后序遍历");//2,5,4,3,1
		binaryTree.postOrder();
		
	}

}

//定义BinaryTree二叉树
class BinaryTree{
	private Heronode root;
	
	public void setRoot(Heronode root) {
		this.root=root;
	}
	//前序遍历
	public void preOrder() {
		if (this.root!=null) {
			this.root.preOrder();
		}else {
			System.out.println("二叉树为空，无法遍历");
		}
	}
	//中序遍历
	public void infixOrder() {
		if (this.root!=null) {
			this.root.infixOrder();
		}else {
			System.out.println("二叉树为空，无法遍历");
		}
	}
	//后序遍历
	public void postOrder() {
		if (this.root!=null) {
			this.root.postOrder();
		}else {
			System.out.println("二叉树为空，无法遍历");
		}
	}
}
//先创建HeroNode结点
class HeroNode{
	private int no;
	private String name;
	private Heronode left;//默认null
	private Heronode right;//默认null
	public Heronode(int no,String name) {
		this.no=no;
		this.name=name;		
	}
	public int getNo() {
		return no;
	}
	public void setNo(int no) {
		this.no = no;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public Heronode getLeft() {
		return left;
	}
	public void setLeft(Heronode left) {
		this.left = left;
	}
	public Heronode getRight() {
		return right;
	}
	public void setRight(Heronode right) {
		this.right = right;
	}
	@Override
	public String toString() {
		return "Heronode [no=" + no + ", name=" + name + "]";
	}
	//编写前序遍历的方法
	public void preOrder() {
		System.out.println(this);//先输出父节点
		//递归向左子树前序遍历
		if (this.left!=null) {
			this.left.preOrder();
		}
		//递归向右子树前序遍历
		if (this.right!=null) {
			this.right.preOrder();
		}
	}
	//中序遍历
	public void infixOrder() {
		//递归向左子树中序遍历
		if (this.left!=null) {
			this.left.infixOrder();
		}
		//输出父节点
		System.out.println(this);
		//递归向右子树中序遍历
		if (this.right!=null) {
			this.right.infixOrder();
		}
	}
	//后序遍历
	public void postOrder() {
		if (this.left!=null) {
			this.right.postOrder();
		}
		if (this.right!=null) {
			this.right.postOrder();
		}
		System.out.println(this);
	}
}

运行效果