Java实现二叉树

缺乏、安全感 2022-05-14 07:36 155阅读 0赞

这里创建二叉树是顺序结构存储二叉树原理，即一个节点 i 的左孩子为 i\*2+1,右孩子为 i\*2+2。程序创建的二叉树如图所示：

![70][]

Demo：

import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    
    public class CreateByArray<E> {
    	private Node<E> root;//根节点
    	private List<Node<E>> list=null;
    	class Node<E>{
    		Node<E> left=null;  //左孩子
    		Node<E> right=null; //右孩子
    		E data;             //数据域
    		/**
    		 * 初始化节点
    		 * @param data
    		 */
    		public Node(E data) {
    			this.data=data;
    			left=null;
    			right=null;
    		}
    
    		public Node() {
    		}
    	}
    
    	/**
    	 * 获取根节点
    	 * @return
    	 */
    	public Node<E> getRoot() {
    		return root;
    	}
    	/**
    	 * 用数组构建二叉树,依次为节点列表中节点的左右孩子赋值。左孩子为i*2+1,右孩子为i*2+2(参考顺序存储结构二叉树 )
    	 * @param array
    	 */
    	public CreateByArray(Object[] array) {
    		this.list=new ArrayList<CreateByArray<E>.Node<E>>();
    
    		for (int i = 0,len=array.length; i < len; i++) {
    			list.add(new Node<E>((E) array[i]));
    		}
    
    		this.root=list.get(0);
    
    		for (int i = 0,len=(list.size()/2); i < len; i++) {
    			try {
    				//为左子树赋值  j*2+1
    				list.get(i).left = list.get(i * 2 + 1);
    				//为右子树赋值 j*2+2
    				list.get(i).right = list.get(i * 2 + 2);
    			} catch (Exception e) {
    			}
    		}
    	}
    
    	/**
    	 * 前序遍历
    	 * @param root
    	 */
    	public void indorder(Node<E> root) {
    		if (root==null) {
    			return;
    		}
    		System.out.print(root.data+",");
    		indorder(root.left); //递归遍历左子树
    		indorder(root.right); //递归遍历右子树
    
    	}
    
    	/**
    	 * 中序遍历
    	 * 
    	 * @param root
    	 */
    	public void inOrderTraverse(Node<E> root) {
    		if (root==null) {
    			return;
    		}
    		inOrderTraverse(root.left); //递归遍历左子树
    		System.out.print(root.data+",");
    		inOrderTraverse(root.right);//递归遍历右子树
    	}
    	/**
    	 * 后序遍历
    	 * 
    	 * @param root
    	 */
    	public void postOrderTraverse(Node<E> root) {
    		if (root==null) {
    			return;
    		}
    		postOrderTraverse(root.left);  //遍历左子数节点
    		postOrderTraverse(root.right); //遍历右子树节点
    		System.out.print(root.data+","); //从下往上遍历
    	}
    	/**
    	 * 节点个数
    	 * @return
    	 */
    	public int size(Node<E> root){
    		if (root==null) {
    			return 0;
    		}else {
    			return 1+size(root.left)+size(root.right);
    		}
    
    	}
    
    	/**
    	 * 返回树的高度
    	 * @return
    	 */
    	public int height(Node<E> root){
    		if (root==null) {
    			return 0;
    		}else {
    			int i=height(root.left);  //递归左子树
    			int j=height(root.right); //递归右子树
    			return (i<j)?(j+1):(i+1); //到底部时选择高度最高的
    		}
    
    	}
    	/**
    	 * 释放树，通过后续遍历将节点释放
    	 * @param root
    	 */
    	public void destory(Node<E> root) {
    		if (root!=null) {
    			destory(root.left);  //递归删除左子树
    			destory(root.right); //递归删除右子树
    			root=null;    //删除
    		}
    	}
    
    	/**
    	 * 前序遍历非递归实现
    	 * @param args
    	 */
    	public void nonRecPreOrder(Node<E> p){
    		Stack<Node<E>> stack = new Stack<Node<E>>();
    		Node<E> node=p;
    		while (node!=null || stack.size()>0) {
    			while (node!=null) {
    				System.out.print(node.data+",");  //访问节点
    				stack.push(node);  //左子树入栈
    				node=node.left;   //遍历左子树
    			}
    			if (stack.size()>0) {
    				node=stack.pop(); //左子树访问完毕。出栈
    				node=node.right;  //访问该节点的右子树
    			}
    		}
    	}
    
    	/**
    	 * 中序遍历非递归实现
    	 * @param p
    	 */
    	public void nonRecInOrder(Node<E> p) {
    		Stack<Node<E>> stack =new Stack<Node<E>>();    
    		Node<E> node =p;    
    		while(node!=null ||stack.size()>0){    
    			//存在左子树    
    			while(node!=null){    
    				stack.push(node); //左子树入栈   
    				node=node.left;    
    			}    
    			//栈非空    
    			if(stack.size()>0){    
    				node=stack.pop(); //先进先出，访问左子树
    				System.out.print(node.data+",");    
    				node=node.right;    
    			}    
    		}    
    	}
    
    	/**
    	 * 后序遍历非递归实现
    	 * @param node
    	 */
    	public void posOrder1(Node<E> node)
    	{
    		Stack<Node<E>> stack1 = new Stack<>();//节点
    		Stack<Integer> stack2 = new Stack<>();//访问标志
    		int i = 1; //0代表第一次出栈，只遍历完左子树，不能被访问。   1 代表第二次出栈，遍历完右子树，可以访问
    		while(node != null || !stack1.empty())
    		{
    			while (node != null) //遍历左子树，将node,连同访问标志一起入栈
    			{
    				stack1.push(node);
    				stack2.push(0);
    				node = node.left;
    			}
    			while(!stack1.empty() && stack2.peek() == i) //不为空，并且标志为1时，输出节点
    			{
    				stack2.pop();
    				System.out.print(stack1.pop().data + ",");
    			}
    			if(!stack1.empty()) //如果栈非空，将栈顶元素标志改为2，准备遍历该节点的右子树
    			{
    				stack2.pop();
    				stack2.push(1);
    				node = stack1.peek();
    				node = node.right;
    			}
    		}
    	}
    
    	//测试    
    	public static void main(String[] args) {    
    		Object[] arrays = {new Integer(1),new Integer(2),new Integer(3),new Integer(4),5,6,7,8,9,10};
    		CreateByArray<Integer> createTreeByArray = new CreateByArray<Integer>(arrays);
    		System.out.println("....前序遍历....");
    		createTreeByArray.indorder(createTreeByArray.list.get(0));
    		System.out.println();
    		System.out.println("....中序遍历....");
    		createTreeByArray.inOrderTraverse(createTreeByArray.list.get(0));
    		System.out.println();
    		System.out.println("....前序遍历非递归....");
    		createTreeByArray.nonRecPreOrder(createTreeByArray.list.get(0));
    		System.out.println();
    		System.out.println("....中序遍历非递归....");
    		createTreeByArray.nonRecInOrder(createTreeByArray.list.get(0));
    	}   
    
    }

运行结果：

![70 1][]

[70]: /images/20220514/ab3e2cc05d284502a45999f13b2e9a08.png
[70 1]: /images/20220514/e04582b952404e58b080cf7e6ac8203e.png