数据结构之二叉树创建与遍历

男娘i 2022-08-11 08:00 179阅读 0赞

package com.zhiru;
    
    import java.util.Stack;
    
    public class BinaryTree1 {
    
    	private Stack<TreeNode> s;
    	private TreeNode root;// 根节点
    
    	public BinaryTree1() {
    		root = null;
    	}
    
    	public BinaryTree1(char[] x, char[] y) {
    		root = createBinTree(x, y, x.length);
    	}
    
    	public BinaryTree1(char ref) {
    		root = null;
    	}
    
    	public TreeNode getRoot() {
    		return root;
    	}
    
    	/*
    	 * 结点类 成员变量：结点中数据data,左孩子lChild,右孩子结点rChild.
    	 */
    	class TreeNode {
    		private char data;
    		private TreeNode lChild;
    		private TreeNode rChild;
    
    		public TreeNode(char d) {
    			data = d;
    			lChild = null;
    			rChild = null;
    		}
    
    		public TreeNode(char d, TreeNode l, TreeNode r) {
    			data = d;
    			lChild = l;
    			rChild = r;
    		}
    	}
    
    	/*
    	 * 计算以r为根的树的结点个数.
    	 */
    	public int size(TreeNode r) {
    		if (r == null)
    			return 0;
    		else
    			return 1 + size(r.lChild) + size(r.rChild);
    	}
    
    	/*
    	 * 计算以r为根的二叉树的深度.
    	 */
    	public int height(TreeNode r) {
    		if (r == null)
    			return 0;
    		else {
    			int ls = height(r.lChild);
    			int rs = height(r.rChild);
    			return ls < rs ? rs + 1 : ls + 1;
    		}
    	}
    
    	/*
    	 * 判断两颗二叉树是否相同
    	 */
    	public boolean isEquals(TreeNode a, TreeNode b) {
    		if (a == null && b == null)
    			return true;
    		if (a != null && b != null && a.data == b.data
    				&& isEquals(a.lChild, b.lChild) && isEquals(a.rChild, b.rChild))
    			return true;
    		else
    			return false;
    	}
    
    	// 前序遍历：根左右
    	public void preOrder(TreeNode r) {
    		if (r != null) {
    			System.out.print(r.data + " ");
    			preOrder(r.lChild);
    			preOrder(r.rChild);
    		}
    
    	}
    
    	/*
    	 * 中序遍历:左根右
    	 */
    	public void inOrder(TreeNode r) {
    		if (r != null) {
    			inOrder(r.lChild);
    			System.out.print(r.data + " ");
    			inOrder(r.rChild);
    		}
    	}
    
    	/*
    	 * 后序遍历:左右根
    	 */
    	public void afterOrder(TreeNode r) {
    		if (r != null) {
    			afterOrder(r.lChild);
    			afterOrder(r.rChild);
    			System.out.print(r.data + " ");
    		}
    	}
    
    	// 前序遍历的非递归实现要用到栈
    	/*
    	 * 实现原理就是：先访问当前根节点，然后判断当前结点的右结点是否为空 不为空压栈，为空在判断左子树是否为空，不为空将当前结点改变为它的左子树结点
    	 * 为空弹出栈中和它相邻的右结点。 要点就是要在栈中留下回退的结点，而前序遍历是按照“根左右”的顺序遍历的， 所以回退的结点就是右结点
    	 */
    	public void preOrderNonRecursion() {
    		s = new Stack<TreeNode>();
    		TreeNode p = root;
    		s.push(null);
    		while (p != null) {
    			System.out.print(p.data + " ");// 访问根结点
    			if (p.rChild != null)
    				s.push(p.rChild);// 将右子树结点预留栈中
    			if (p.lChild != null)
    				p = p.lChild;// 进左子树.
    			else
    				p = s.pop();
    			// System.out.print(s.pop()+" ");
    		}
    		s = null;
    	}
    
    	/*
    	 * 中序遍历非递归实现
    	 */
    	public void inOrderNonRecursion() {
    		/*
    		 * 一颗二叉子树遍历完毕的标志是它的右孩子为空
    		 */
    		s = new Stack<TreeNode>();
    		TreeNode p = root;
    		do {
    			// 压入栈中的是左结点以及该左结点的第一个右孩子，
    			// 如果这个右孩子还有右孩子，那它将被弹出,将它的右孩子压入栈中.
    			while (p != null) {
    				s.push(p);
    				p = p.lChild;
    			}
    			if (!s.empty()) {
    				p = s.pop();
    				System.out.print(p.data + " ");
    				p = p.rChild;
    			}
    		} while (p != null || !s.empty());// 当没有左子树且栈为空【没有右孩子】结束
    		s = null;
    	}
    
    	/*
    	 * 由前序序列和中序序列构造二叉树. x为前序序列， y为中序序列
    	 */
    	public char[] getChar(char[] m, int start) {
    		if (m.length < 1) {
    			return null;
    		} else {
    			if (start >= 1 && start < m.length) {
    				int j = start;
    				char[] x = new char[m.length - start];
    				for (int i = 0; i < x.length; i++) {
    					x[i] = m[j++];
    				}
    				return x;
    			}
    		}
    		return null;
    	}
    
    	public TreeNode createBinTree(char[] x, char[] y, int len) {
    		if (x != null && y != null) {
    			int n;
    			if ((n = len) == 0)
    				return null;
    			int k = 0;
    			while (x[0] != y[k])
    				k++;// 在中序序列中寻找根节点.
    			TreeNode t = new TreeNode(x[0]);// 创建根节点
    			t.lChild = createBinTree(getChar(x, 1), y, k);// 构造左子树
    			t.rChild = createBinTree(getChar(x, k + 1), getChar(y, k + 1), n
    					- k - 1);// 构造右子树
    			return t;
    		}
    		return null;
    	}
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    
    		char[] a = { 'A', 'B', 'H', 'F', 'D', 'E', 'C', 'K', 'G' };
    		char[] b = { 'H', 'B', 'D', 'F', 'A', 'E', 'K', 'C', 'G' };
    		BinaryTree1 bt = new BinaryTree1(a, b);
    		// char[]x=getChar(a,1);
    		// for(int i=0;i<x.length;i++){
    		// Print.print(" ");
    		// }
    		Print.print("二叉树节点个数" + bt.size(bt.getRoot()));
    		Print.print("二叉树的深度:" + bt.height(bt.getRoot()));
    		Print.print("前序遍历:");
    		bt.preOrder(bt.getRoot());
    		System.out.println();
    		Print.print("中序遍历:");
    		bt.inOrder(bt.getRoot());
    		System.out.println();
    		Print.print("后序遍历:");
    		bt.afterOrder(bt.getRoot());
    		System.out.println();
    		Print.print("前序遍历[非递归]:");
    		bt.preOrderNonRecursion();
    		Print.print("中序遍历非递归\n");
    		bt.inOrderNonRecursion();
    	}
    
    }

二叉树节点个数9  
二叉树的深度:4  
前序遍历:  
A B H F D E C K G   
中序遍历:  
H B D F A E K C G   
后序遍历:  
H D F B K G C E A   
前序遍历\[非递归\]:  
A B H F D E C K G 中序遍历非递归  
  
  
H B D F A E K C G