树的相关操作

最近很多大公司的笔试题都考到了树这个数据结构

 

淘宝武汉地区的笔试题倒数第二题是关于树中两个节点找父节点的

 

搜狗昨天又考到了，是找树中两个距离最远节点的题。

 

所以树被考到的概率很高啊，今天又java把树的基本操作都写了一遍，需要的童鞋果断分享吧

package com.gengu.树;

import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.ConcurrentLinkedQueue;

import org.junit.Test;

/**
 * 这里测试树的相关算法
 * 1：构造一个树
 * 2：先序遍历
 * 3：中序遍历
 * 4：后序遍历
 * 5：层次遍历
 * 6：打印某一层二叉树的所有节点
 * 7：求高度
 * 8：求最远的节点
 * 9：判断一个树是不是平衡二叉树
 * */
class Node{
	public int value;
	public Node left;
	public Node right;
	public Node(int value){
		this.value = value;
	}
}

public class TestTree {

	public static Node root = new Node(9);
	public static Node value1 ;
	public static Node value2 ;
	/**
	 * 创建一颗二叉树
	 * */
	public static void createTree(){
		Node node1 = new Node(8);
		Node node2 = new Node(7);
		Node node3 = new Node(6);
		Node node4 = new Node(5);
		Node node5 = new Node(4);
		Node node6 = new Node(3);
		Node node7 = new Node(2);
		Node node8 = new Node(1);
		Node node9 = new Node(0);
		Node node10 = new Node(11);
		Node node11 = new Node(12);
		value1 = node3;
		value2 = node9;
		
		root.left = node1;
		root.right = node2;
		
		node1.left = node3;
		node1.right = node4;
		
		node2.left = node5;
		node2.right = node6;
		
		node3.left = node7;
		node3.right = node8;
		node6.left = node10;
		node10.right = node11;
		node8.right = node9;
	}
	
	
	/**
	 * 先序遍历
	 * */
	public static void rootFirst(Node node){
		System.out.println(node.value);
		if(node.left != null){
			rootFirst(node.left);
		}
		if(node.right != null){
			rootFirst(node.right);
		}
	}
	
	/**
	 * 后序遍历
	 * */
	public static void rootLast(Node node){
		if(node.left != null){
			rootLast(node.left);
		}
		if(node.right != null){
			rootLast(node.right);
		}
		System.out.println(node.value);
		
	}
	
	/**
	 * 中序
	 */
	public static void rootMid(Node node){
		if(node.left != null){
			rootMid(node.left);
		}
		System.out.println(node.value);
		if(node.right != null){
			rootMid(node.right);
		}
	}

	/**
	 * 层次第n层的节点
	 * */
	public static void layer(Node node,int n){
		if(node == null){
			return ;
		}
		if(1 == n){
			System.out.println(node.value);
		}
		else {
			layer(node.left,n-1);
			layer(node.right, n-1);
		}
	}
	
	/**
	 * 求出树的高度
	 * */
	public static int getHeight(Node root){
		if(null == root){
			return 0;
		}else{
			int lh = getHeight(root.left);
			int rh = getHeight(root.right);
			return lh>rh?lh+1:rh+1;
		}
	}
	
	/**
	 * 层次序遍历
	 * */
	public static void layer1(Node root){
		Queue<Node> nodes = new ConcurrentLinkedQueue<Node>();
		//加入第一个节点
		nodes.add(root);
		
		while(true){
			if(nodes.isEmpty()){
				break;
			}
			Node node2 = nodes.poll();
			if(node2.left!=null){
				nodes.add(node2.left);
			}
			if(node2.right!=null){
				nodes.add(node2.right);
			}
			System.out.println(node2.value);
		}
	}
	
	/**
	 * 判断一颗树是不是平衡二叉树
	 * */
	public static boolean isAVL(Node root){
		if(root==null){
			return true;
		}else {
			//求左树的高度
			int left_depth = getHeight(root.left);
			//右子树的高度
			int right_depth = getHeight(root.right);
			System.out.println(left_depth);
			System.out.println(right_depth);
			//如果从这个点可以看出它不平衡那么就返回false
			if(left_depth-right_depth>1||right_depth-left_depth>1){
				return false;
			}
			//如果从这个节点往下看是平衡的不能就说它是平衡
			//还要看它的左右子树
			else {
				return isAVL(root.right)&&isAVL(root.right);
			}
		}
	}
	
	/**
	 * 中序遍历的非递归算法
	 * 要注意的是所有节点都要入栈
	 * */
	public static void inorder(Node root){
		Stack<Node> stack1 = new Stack<Node>();
		Node node = root;
		//stack1.push(root);
		//第一个节点的路径
		while(node!=null||!stack1.isEmpty()){
			if(node!=null){
				stack1.push(node);
				node = node.left;
			}else {
				node = stack1.pop();
				System.out.print(node.value);
				node = node.right;
			}
		}
		System.out.println();
	}
	
	/**
	 * 先序遍历
	 * 非递归算法
	 * */
	public static void preorder(Node root){
		Stack<Node> stack = new Stack<Node>();
		Node node = root;
		stack.push(root);
		while(!stack.isEmpty()){
			node = stack.pop();
			System.out.print(node.value);
			if(node.right!=null){
				stack.push(node.right);
			}
			if(node.left!=null){
				stack.push(node.left);
			}
		}
		System.out.println();
	}
	
	/**
	 * 寻找最近公共父节点
	 * */
	public static Node commanNode(Node root,Node value1,Node value2){
		if(root == null){
			return null;
		}
		else if(root==value1){
			//这里表示的是如果在其它地方没有找到value2
			//而找到了value1 那么表示value2在value1下面
			//所以返回value1
			return value1;
		}
		//同上
		else if(root==value2){
			return value2;
		}
		/**
		 * 这里是一个分治的思想
		 * 从它的左右子树分别去找两个节点
		 * 如果找到那么当前节点就是最近父节点
		 * 想不通的可以画图
		 */
		Node leftNode = commanNode(root.left, value1, value2);
		Node rightNode = commanNode(root.right, value1, value2);
		
		//如果在左右子树种分别找到就返回当前节点
		if(leftNode!=null&&rightNode!=null){
			return root;
		}
		/**
		 * 如果只有在左边找到这个节点 那么返回
		 * 因为在右边没找到所以另外那个顶点一定是这个节点的子节点
		 * 画个图就能看懂
		 */
		
		else if(leftNode!=null){
			return leftNode;
		}
		/**
		 * 如果只有在右边找到这个节点 那么返回
		 * 因为在左边没找到所以另外那个顶点一定是这个节点的子节点
		 * 画个图就能看懂
		 */
		else if(rightNode!=null){
			return rightNode;
		}
		else return null;
	}
	
	@Test
	public void test(){
		createTree();
		System.out.println(commanNode(root, value1, value2).value);
	}
	
}

 

还有几种情况我会再写了传上来

评论

2 楼 gengu 2011-11-08  

秦时明月黑 写道

淘宝笔试就吃树的亏

搜狗笔试遇到了树，我没搞出来，然后回来把大部分可能考到的关于树的都弄了一遍
亡羊补牢，为时未晚，后面的笔试帮了大忙

1 楼 秦时明月黑 2011-11-08  

淘宝笔试就吃树的亏