数据结构之二叉树及其基本操作(java实现)

一、简介

二、代码展示

Node.java 用于表示二叉树的节点，存储数据值以及左右孩子的引用值

package BinaryTree;

//节点类
public class Node {

	int data;
	Node leftChild;
	Node rightChild;
	
	Node(int n){
		this.data=n;
	}
	
	public void Show() {
		System.out.println(this.data+"	");
	}
}

BinaryTree.java 用于存储构造展示遍历一颗二叉树，包含了二叉树操作的多种方法

package BinaryTree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;


public class BinaryTree {

	//二叉树的根节点
	Node root;

	BinaryTree(){
		
	}
	
	//指定根节点的值，构造一颗二叉树
	BinaryTree(int n) {
		root = new Node(n);
		root.leftChild = null;
		root.rightChild = null;
	}

	//构造一颗二叉树，其二叉树中的值于data数组中的值相对应
	public void CreateTree(int[] data) {
		
		if(data!=null)
			root=CreateTree(data,1);
	}
	
	public Node CreateTree(int[] data,int index) {
		
		Node tmp;
		
		if(index>data.length)
			return null;
		else {
			tmp=new Node(data[index-1]);
			tmp.leftChild=CreateTree(data,index*2);
			tmp.rightChild=CreateTree(data,index*2+1);
		}
		return tmp;
	}
	
	// 使用重载法，遍历整个二叉树
	// 中序遍历
	public void inOrderTraverse() {
		System.out.println("中序遍历法遍历一颗二叉树");

		inOrderTraverse(root);
	}

	public void inOrderTraverse(Node p) {
		Node tmp = p;

		if (tmp != null) {
			//递归遍历左子树
			inOrderTraverse(tmp.leftChild);
			//访问此节点的内容
			System.out.println(tmp.data);
			//递归遍历右子树
			inOrderTraverse(tmp.rightChild);
		}
	}

	// 前序遍历
	public void preOrderTraverse() {
		System.out.println("先序遍历法遍历一颗二叉树");

		preOrderTraverse(root);
	}

	public void preOrderTraverse(Node p) {
		Node tmp = p;

		if (tmp != null) {
			System.out.println(tmp.data);
			preOrderTraverse(tmp.leftChild);
			preOrderTraverse(tmp.rightChild);
		}
	}
	
	/*
	 * 树的非递归遍历算法[中序遍历]（此处只展示代码实现部分，不讲解算法原理部分）
	 * 利用栈
	 */
	public void inOrderTraverse2() {

		System.out.println("中序遍历法遍历一颗二叉树");
		Stack s = new Stack();
		Node p = root;
		
		s.push(p);
		p=p.leftChild;
		
		while(s.isEmpty()==false||p!=null) {
			while(p!=null) {
				s.push(p);
				p=p.leftChild;
			}
			
			p=(Node)s.pop();
			System.out.println(p.data);
			
			p=p.rightChild;
		}
	}
	
	/*
	 * 树的层次遍历（此处只展示代码实现部分，不讲解算法原理部分）
	 * 利用队列
	 */
	public void LevelOrder() {
		
		System.out.println("树的层次遍历");
		
		Queue queue=new LinkedList();
		Node tmp;
		
		queue.offer(root);
		
		while(queue.isEmpty()!=true) {
			tmp=(Node)queue.poll();
			System.out.println(tmp.data);
			
			if(tmp.leftChild!=null)
				queue.offer(tmp.leftChild);
			
			if(tmp.rightChild!=null)
				queue.offer(tmp.rightChild);
		}
	}

	//计算一颗二叉树的深度（分治法)
	public int DepthTree(Node p) {
		
		if(p==null)
			return 0;
		
		int len1=DepthTree(p.leftChild);
		int len2=DepthTree(p.rightChild);
		int len=len1>len2?len1:len2;
			
		return len+1;
	}
}

BinaryTreeDemo.java 用于测试二叉树的生成算法

package BinaryTree;

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTreeDemo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		BinaryTree root=new BinaryTree();
		int[] data=new int[] {5,8,9,13,10,7,12,18};
	
		root.CreateTree(data);
		root.inOrderTraverse();
		root.LevelOrder();
		
		
		System.out.println("该树的深度为"+root.DepthTree(root.root));
		
	}
}