鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > erlang > >

关于二叉树的常见题型

来源:互联网 作者:佚名 时间:2016-07-17 21:12
一、二叉树相关概念 1.1 基本术语 结点的度: 一个结点的子结点的个数称为结点的度。 树的度: 树中结点的最大度数为树的度 树的深度(高度): 树中结点的最大层数,从1 开始。 1.2 二叉树分类 满二叉树: 一颗高度为h ,并且含有 2^h-1 个结点的二叉树称为

一、二叉树相关概念

1.1 基本术语

  • 结点的度:一个结点的子结点的个数称为结点的度。
  • 树的度:树中结点的最大度数为树的度
  • 树的深度(高度):树中结点的最大层数,从1开始。

1.2 二叉树分类

  • 满二叉树:一颗高度为h,并且含有2^h-1个结点的二叉树称为满二叉树。即树中每一层都含有最多的节点。除叶子节点每个节点的度都为2
  • 完全二叉树:当高度为h具有n个结点的二叉树,与高度为h的满二叉树结点编号完全对应时,即为完全二叉树。(若存在度为1的节点,只能有一个,且只有左孩子无右孩子)
  • 二叉排序树:左子树上所有的结点的关键字均小于根节点的关键字,右子树上所有节点的关键字均大于根结点的关键字。(中序遍历可得到递增序列)
  • 平衡二叉树:树上任一结点的左子树和右子树深度之差不超过1
  • 哈夫曼树:在含有n个带权叶子节点的二叉树中,其中带权路径长度最小的二叉树为哈夫曼树(最优二叉树)—哈夫曼编码
  • 红黑树:红黑树是每个节点都带颜色的树,节点颜色或是红色或是黑色,红黑树是查找树。最重要的性质,从根节点到叶子节点的最长的路径不多于最短路径的长度的2倍。红黑树插入、查找、删除的时间复杂度都为O(logn)

1.3 二叉树的几条重要性质:

  1.  非空二叉树上叶子节点的个数等于度数为2的节点数+1   
  2. 结点i所在的层次(深度)为(logn)+1
  3. N个节点的二叉树的高度为(logn)+1或是log(n+1)

二、二叉树的常见面试题

注意事项:

  •  根节点是否为空(递归结点是否为null)
  • 是否只存在根节点(一个节点)
  • 二叉树通常使用递归,清楚递归结束的条件。例如找路径时是遇到叶子节点停止,大多数是当前结点为null
题目汇总

  1. 二叉树的遍历:前序遍历、中序遍历、后序遍历、层次遍历(队列)
  2. 根据中序遍历序列和前序遍历序列(或后序遍历)重建二叉树。
  3. 求二叉树的所有路径(根到叶子节点)
  4. 判断二叉树中是否存在一条路径使得节点之和为给定的值。
  5. 求二叉树的最大深度、最小深度
  6. 求二叉树第k的节点个数(层次遍历:队列)
  7. 求二叉树中叶子节点的个数
  8. 交换二叉树的左右孩子
  9. 判断两棵二叉树是否相同(结构和值都相等)
  10.  判断二叉树是否为完全二叉树
  11. 判断二叉树是否为平衡二叉树
  12. 求二叉树的镜像
  13. 输入两棵二叉树AB,判断B是否为A的子树
  14. 求二叉树中节点的最大距离
  15. 将二叉查找树变为有序的双向链表
  16. 求二叉树中两个节点的最低公共祖先节点
  17. 哈夫曼树的构建

详细代码
  1. 二叉树的遍历:前序遍历、中序遍历、后序遍历、层次遍历(队列)
前序遍历:
        //递归:前序遍历
	public void preOrder(Node node){
		if(node!=null){
			System.out.print(node.getPerson().getKey()+"\t");
			preOrder(node.getLeftChild());
			preOrder(node.getRightChild());
		}
	}
	
	//非递归:前序遍历
	private void preOrder_2(){
		Node curNode = rootNode;
		while(curNode!=null){
			//打印当前节点
			System.out.print(curNode.getPerson().getKey()+"\t");
			//入栈
			stack.push(curNode);
			//指向左子节点
			curNode = curNode.getLeftChild();
			//查找最左边的子节点
			while(curNode == null&&!stack.isEmpty()){
				curNode = stack.peek();//取栈顶元素
				stack.pop();//出栈
				curNode = curNode.getRightChild();
			}
		}
	}
中序遍历:
        //递归:中序遍历
	public void midOrder(Node node){
		if(node!=null){
			midOrder(node.getLeftChild());
			System.out.print(node.getPerson().getKey()+"\t");
			midOrder(node.getRightChild());
		}
	}
	//非递归:中序遍历(左根右)
	public void midOrder_2(){
		Node curNode = rootNode;
		while(curNode!=null||!stack.isEmpty()){
			if(curNode.getLeftChild()!=null){
				stack.push(curNode);
				curNode = curNode.getLeftChild();
			}else {
				//打印最左端的节点
				System.out.print(curNode.getPerson().getKey()+"\t");
				curNode = curNode.getRightChild();//指向右子节点
				while(curNode == null&&!stack.isEmpty()){
					curNode = stack.peek();
					System.out.print(curNode.getPerson().getKey()+"\t");
					stack.pop();
					curNode = curNode.getRightChild();
				}
			}
		}
	}
后序遍历:
        //递归:后序遍历
	public void behOrder(Node node){
		if (node!=null) {
			behOrder(node.getLeftChild());
			behOrder(node.getRightChild());
			System.out.print(node.getPerson().getKey()+"\t");
		}
	}
	//非递归:后序遍历(左根右)
	public void behOrder_2(){
		Node curNode = rootNode;
		Node preNode = null;
		//先将根入栈
		stack.push(curNode);
		while(!stack.isEmpty()){
			curNode = stack.peek();//当前节点设置为栈顶节点
			if(curNode.getLeftChild()==null&&curNode.getRightChild()==null
			||(preNode!=null&&(curNode.getLeftChild()==preNode||curNode.getRightChild()==preNode))){
				//当前节点无左右节点,或者有左节点或右节点,但已经被访问过
				//则直接输出该节点,将其出栈,将其设为上一个访问的节点
				System.out.print(curNode.getPerson().getKey()+"\t");
				stack.pop();
				preNode = curNode;//已被访问过
			}else {
				//如果不满足上面两种情况,则将其右孩子左孩子依次入栈(先右节点再左节点)
				if (curNode.getRightChild()!=null) {
					stack.push(curNode.getRightChild());
				}
				if(curNode.getLeftChild()!=null){
					stack.push(curNode.getLeftChild());
				}
			}
		}
	}
层次遍历:LeetCode中要求打印格式[[1],[2,3], [4,5,6]] 将每层结点分别存入List<Integer>中,需要两个队列,弹出queue1队头存入list<Integer>中,同时将左右子节点入队到queue2,当queue1为空时,该层遍历完毕,则将queue1 = queue2,重置List<Integer>,继续开始遍历
public List<List<Integer>> levelOrder(TreeNode root) {
		Queue  queue = new Queue(1024);
        List<List<Integer>> list = new ArrayList<List<Integer>>();
		if(root==null){
			return list;
		}
        
        queue.push(root);
        //每层节点集
        List<Integer> level = new ArrayList<Integer>();
        do{
        	Queue  queue2 = new Queue(1024);
        	while(!queue.isEmpty()){
            	//取队首节点
            	TreeNode head = queue.peek();
            	level.add(head.val);
            	
            	//弹出队头
            	queue.pop();
            	
            	if(head.left!=null){
            		queue2.push(head.left);
            	}
            	if(head.right!=null){
            		queue2.push(head.right);
            	}
            }
        	list.add(level);
        	level = new ArrayList<Integer>();
        	queue = queue2;
        }while(!queue.isEmpty());
        List<List<Integer>> list2 = new ArrayList<List<Integer>>();
        for(int i=list.size()-1;i>=0;i--){
        	list2.add(list.get(i));
        }
        return list; 
    }
	
	public class Queue {
		/**
		 * 实现队列
		 */
		int first,last,maxSize;
		TreeNode[] queue;
		public Queue(int size){
			first = last = -1;
			maxSize = size;
			queue = new TreeNode[maxSize];
		}
		public boolean isEmpty(){
			if(first==-1){
				return true;
			}else {
				return false;
			}
		}
		public boolean isFull(){
			if(first==(last+1)%maxSize){
				return true;
			}else {
				return false;
			}
		}
		//push
		public boolean push(TreeNode num){
			if(this.isFull()){
				System.out.println("queue is full!");
				return false;
			}if(this.isEmpty()){
				first = last = 0;
			}else{
				last = (last+1)%maxSize;
			}
			queue[last] = num;
			
			return true;
		}
		
		public TreeNode pop(){
			TreeNode num = queue[first];
			if(this.isEmpty()){
				queue = new TreeNode[maxSize];
				return null;
			}
			if(first==last){
				//到达队尾,清空数组
				queue = new TreeNode[maxSize];
				first = last = -1;
				return num;
			}
			
			first=(first+1)%maxSize;
			return num;	
		}
		
		public TreeNode peek(){
			if(first==-1) return null;
			else return queue[first];
		}
	}
2.根据中序遍历序列和前序遍历序列(或后序遍历)重建二叉树。 思路:(1)首先判断两个序列的长度,长度不同则return
           (2)前序遍历和中序遍历序列重建:
a.前序遍历的第一个节点是根节点,遍历中序序列找到根节点的位置
b.将序列分为 左孩子  右孩子,找到左孩子的长度,当左孩子的长度>0确定左孩子的 中序序列、前序序列的起始位置;同时右孩子的长度>0,确定右孩子的 中序序列、前序序列的起始位置。(递归调用)
c.递归结束条件:当中序序列和前序序列只有一个节点时,即起始位置相同。
          (3)后序序列和中序序列重建:同理。后序遍历的最后一个是根节点。
        public TreeNode buildTree(int[] inorder, int[] preorder) {//由前序序列和中序序列重建二叉树
		if(inorder.length<1||preorder.length<1||inorder.length!=preorder.length){
			return null;
		}
		return constructTree(inorder, 0, inorder.length-1, preorder, 0, preorder.length-1);
	}
	public TreeNode constructTree(int[] inorder,int inBegin,int inEnd,int[] preorder,int preBegin,int preEnd){
		int val = preorder[preBegin];
		TreeNode rootNode = new TreeNode(val);
		rootNode.left = rootNode.right = null;
		if(inBegin == inEnd){
			if(preBegin == preEnd&&inorder[inBegin] == preorder[preBegin]){
				return rootNode;
			}
		}
		//在中序遍历中找到根节点
		int rootIndex = inBegin;
		while(inorder[rootIndex]!=val&&rootIndex<=inEnd){
			rootIndex++;
		}
		
		//找到rootIndex,分左右子树。分别找到中序、前序的左子树的结尾,右子树的开始
		
		//左子树长度
		int leftLength = rootIndex-inBegin;
		//右子树长度
		int rightLength = inEnd-rootIndex;
		//中序
		int inLeftEnd = rootIndex-1;
		int inRightBegin = rootIndex+1;
		
		//前序
		int preLeftEnd = preBegin+leftLength;
		int preRightBegin = preLeftEnd+1;
		//构建左、右子树
		if(leftLength>0){
			rootNode.left = constructTree(inorder, inBegin, inLeftEnd, preorder, preBegin+1, preLeftEnd);
		}
		if(rightLength>0){
			rootNode.right = constructTree(inorder, inRightBegin, inEnd, preorder, preRightBegin, preEnd);
		}
		return rootNode;
	}

//根据中序遍历序列和后序遍历序列构造二叉树。
	public TreeNode buildTree(int[] inorder, int[] postorder) {
		if(inorder.length!=postorder.length||inorder.length==0||postorder.length==0){
    	    return null;
    	}
		return constructTreeNode(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
    }
	
	public TreeNode constructTreeNode(int[] inorder,int inBegin,int inEnd, 
			int[] postorder,int postBegin,int postEnd){
		int val = postorder[postEnd];
		TreeNode rootNode = new TreeNode(val);
		rootNode.left = rootNode.right = null;
		//中序遍历中有一个节点
		if(inBegin==inEnd){
			//再判断后序遍历中也只有一个节点,且中序和后序中两个节点相等,则返回
			if(postBegin==postEnd&&inorder[inEnd]==postorder[postEnd]){
				return rootNode;
			}//其他的情况就报错。说明输入序列非法
		}
		
		int rootIndex = inBegin;
        //先在中序遍历中找到根节点,分成左右子树
    	while(inorder[rootIndex]!=val&&rootIndex<=inEnd){
    		rootIndex++;
    	}
    	
    	//中序分为左右两子树
    	int leftLength = rootIndex-inBegin;
    	int inLeftEnd = rootIndex-1;
    	int inRightBegin = rootIndex+1;
    	
    	
    	int postLeftEnd = postBegin+leftLength-1;
    	int postRightBegin = postLeftEnd+1;
    	int rightLength = inEnd-rootIndex;
    	
    	
    	if(leftLength>0){
    		rootNode.left = constructTreeNode(inorder,inBegin,inLeftEnd,postorder,postBegin,postLeftEnd);
    	}
    	if(rightLength>0){
        	rootNode.right = constructTreeNode(inorder,inRightBegin,inEnd,postorder,postRightBegin,postEnd-1);
    	}
    	
    	return rootNode;
        
	}
3.求二叉树的所有路径
思路:(1)递归调用
   public List<String> binaryTreePaths(TreeNode root) {
        String path  = "";
        List<String> list = new ArrayList<String>();
        if(root==null){
            return list;
        }
        
        getPath(root,list,path);
        return list;
    }
    public void getPath(TreeNode node,List<String> list,String path){
	path +=node.val+"->";
	if(node.left==null&&node.right==null){
		list.add(path.substring(0,path.length()-2));
	}
	if(node.left!=null){
		getPath(node.left, list, path);
	}
	if(node.right!=null){
		getPath(node.right, list, path);
	}
    }
(2)栈+递归:见下一题《判断二叉树中是否存在一条路径使得节点之和为给定的值》
(3)定义一个node新结构,每个节点都存放(节点,根节点到其路径
/*用栈来实现,新建一个结构,每个节点存放从根节点开始的路径。*/
	
	private static class nodePath{
		public TreeNode node;
		public String path;
		public nodePath(TreeNode node,String path){
			this.node = node;
			this.path = path;
		}
	}
	public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<String>();
        Stack<nodePath> path = new Stack<nodePath>();
        if(root==null){
            return list;
        }
        path.push(new nodePath(root, root.val+"->"));
        while(!path.isEmpty()){
        	nodePath nodePath = path.peek();
        	TreeNode curNode = path.pop().node;
        	if(curNode.left==null&&curNode.right==null){
        		String result = nodePath.path;
        		list.add(result.substring(0,result.length()-2));
        	}
        	if(curNode.left!=null){
        		path.push(new nodePath(curNode.left, nodePath.path+curNode.left.val+"->"));
        	}
        	if(curNode.right!=null){
        		path.push(new nodePath(curNode.right, nodePath.path+curNode.right.val+"->"));
        	}
        }
        
        return list;
	}
4.判断二叉树中是否存在一条路径使得节点之和为给定的值。
思路:递归实现,找路径的时候,记录当前Sum和目标和,递归结束条件:当是叶子节点且当前sum=目标值。将path放入list中
public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null){
        	return false;
        }
        if(root.left==null&&root.right==null){
        	return root.val==sum;
        }
        List<String> list = new ArrayList<String>(); 
        Stack<TreeNode> stack = new Stack<TreeNode>();
        int curSum = 0;
        getAllPath(root, stack, curSum,sum,list);
        boolean result = false;
        if(list.size()>0){
        	return true;
        }
        return result;
    }
public void getAllPath(TreeNode rootNode,Stack<TreeNode> stack,int curSum, int expectedSum,List<String> list){
		stack.push(rootNode);
		curSum+=rootNode.val;
		
		boolean isLeaf = rootNode.left==null&&rootNode.right==null;
		if(isLeaf && curSum==expectedSum){
			//把栈中的元素拿出来,组成数字
			Iterator<TreeNode> iterator = stack.iterator();
			String path = "";
			while(iterator.hasNext()){
				path+=iterator.next().val+"->";
			}
			System.out.println(path);
			list.add(path.substring(0,path.length()-2));
		}
		
		if(rootNode.left!=null){
			getAllPath(rootNode.left, stack, curSum,expectedSum,list);
		}
		if(rootNode.right!=null){
			getAllPath(rootNode.right, stack,curSum,expectedSum,list);
		}
		//返回父节点之前要先弹出
		stack.pop();
	}
5、求二叉树的最大深度、最小深度
最大深度:分别求左右子树的深度,其最大值即为二叉树的最大深度。 最小深度:容易出错,必须是根到叶子节点的高度的最小值。所以归结为求二叉树所有路径中的最小值即为最小深度。
//求最大深度
	public int maxDepth(TreeNode root) {
        if(root==null){
        	return 0;
        }
        return maxDepthRecursion(root, 1);
        
    }
	
	public int maxDepthRecursion(TreeNode node,int depth){
		int leftDepth = depth;
		int rightDepth = depth;
		
		if(node.left!=null){
			leftDepth = maxDepthRecursion(node.left, leftDepth+1);
		}
		if(node.right!=null){
			rightDepth = maxDepthRecursion(node.right, rightDepth+1);
		}
		
		return Math.max(leftDepth, rightDepth);
	}
//树的最小深度
	public int minDepth(TreeNode root) {
        if(root==null){
        	return 0;
        }
        List<String> list = new ArrayList<String>();
        getAllPath(root, list, "");
        //将list中path按逗号查分
        String pathStr = list.get(0).trim();
        String[] pathArry = pathStr.split(",");
        int minDepth = pathArry.length;
        for(String path:list){
        	pathArry = path.split(",");
        	if(pathArry.length<minDepth){
        		minDepth = pathArry.length;
        	}
        }
        return minDepth;
    }
	
	public void getAllPath(TreeNode node,List<String> list,String path){
		path+=node.val+",";
		if(node.left==null&&node.right==null){
			list.add(path);
		}
		if(node.left!=null){
			getAllPath(node.left, list, path);
		}
		if(node.right!=null){
			getAllPath(node.right, list, path);
		}
	}
6、求二叉树第k的节点个数
思路1:层次遍历(队列)见题1解法,可求得k层的节点个数 思路2:   (1)当k<1时,返回0 (2)当k=1时返回1 (3)当k>1时,递归调用,返回(左子树的k-1层的节点数+右子树的k-1层节点数)
	public int getKLevelNum(<span style="font-family: Arial, Helvetica, sans-serif;">TreeNode </span><span style="font-family: Arial, Helvetica, sans-serif;">root,int k){</span>
		if(root==null||k<1){
			return 0;
		}
		if(k==1){
			return 1;
		}
		
		int leftNum = getKLevelNum(root.getLeftChild(), k-1);
		int rightNum = getKLevelNum(root.getRightChild(), k-1);
		return leftNum+rightNum;
	}
7、求二叉树中叶子节点的个数
思路    (1)当根节点为null时返回0 (2)当遇到叶子节点返回1, (3)递归返回左右子树的叶子节点,相加
	public int getLeafCount(Node root){
		if(root == null){
			return 0;
		}
		if(root.getLeftChild()==null&&root.getRightChild()==null){
			return 1;
		}
		int leftLeafNum = getLeafCount(root.getLeftChild());
		int rightLeafNum = getLeafCount(root.getRightChild());
		return leftLeafNum+rightLeafNum;
	}
8、求二叉树的镜像:交换二叉树的左右孩子
思路: (1)根节点为null,return (2)交换节点的左右孩子 swap (3)左、右子树分别递归实现
public TreeNode invertTree(TreeNode root) {
        if(root==null){
        	return null;
        }
        if(root.left==null&&root.right==null){
        	return root;
        }
        //交换左右子节点
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        if(root.left!=null){
        	invertTree(root.left);
        }
        if(root.right!=null){
        	invertTree(root.right);
        }
        return root;
    }
 9、判断两棵二叉树是否相同(结构和值都相等)
思路:相同包括:位置相同、值相同。 (1)根节点为空,return false. (2)只有根节点(左右节点均为null),return true, (3)左节点、右节点有一个null,return false; (4)左右节点不为空,值是否相同 (5)分别递归判断左、右子树
public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
        	return true;
        }else if(p==null||q==null){
        	return false;
        }
        if(p.val!=q.val){
			return false;
		}
		boolean left = true;
		boolean right = true;
        return traversalTree(p, q, left, right);
    }
	
	public boolean traversalTree(TreeNode p, TreeNode q,boolean left,boolean right){
		if(p==null&&q==null){
        	return true;
        }
		else if(p==null||q==null){
	    	return false;
	    }
	    if(p.val!=q.val){
			return false;
		}
		
		left = traversalTree(p.left, q.left, left, right);
	
		right = traversalTree(p.right, q.right, left, right);
		
	    
		return left&&right;
	}
 10、判断二叉树是否为完全二叉树

完全二叉树的特点:若设二叉树的深度为h,除第h层外,其它各层(1h-1)的结点数都达到最大个数,第h层所有的结点都连续集中在最左边

思路:层次遍历(从上到下,从左到右)当遇到一个节点的左子树为空,其右子树必须为空,且后面遍历的节点的左右子树都必须为空。

	public boolean isCompleteBinaryTree(TreeNode rootNode){
		if(rootNode==null){
			return false;
		}
		//层次遍历二叉树
		Queue queue = new Queue(1024);
		queue.push(rootNode);
		boolean haveNoChild = false;
		while(!queue.isEmpty()){
			TreeNode curNode = queue.pop();
			if(haveNoChild){
				//当出现空子树节点的时候,后面出现的必须为叶子节点
				if(curNode.getLeftChild()!=null||curNode.getRightChild()!=null){
					return false;
				}
			}
			if(curNode.getLeftChild()!=null&&curNode.getRightChild()!=null){
				queue.push(curNode.getLeftChild());
				queue.push(curNode.getRightChild());
			}else if(curNode.getLeftChild()!=null&&curNode.getRightChild()==null){
				//只有左节点时,后面的节点都应为叶子节点
				haveNoChild = true;
				queue.push(curNode.getLeftChild());
			}else if(curNode.getLeftChild()==null&&curNode.getRightChild()!=null){
				return false;
			}else {
				//此节点为叶子节点
				haveNoChild = true;
			}
		}
		return true;
	}
11、判断二叉树是否为平衡二叉树
思路: (1)如果二叉树为空,返回真
(2)如果二叉树不为空,如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1,返回真,其他返回假
	public boolean isAVLBTree(Node rootNode){
		if(rootNode==null){
			return false;
		}
		return isAVL(rootNode, 1);
	}
	public boolean isAVL(Node rootNode,int depth){
		int leftDepth = depth;
		int rightDepth = depth;
		
		if(rootNode==null){
			return true;
		}
		boolean	isAVL_left = isAVL(rootNode.getLeftChild(), leftDepth+1);//求深度
		boolean isAVL_right = isAVL(rootNode.getRightChild(), rightDepth+1);
		
		if(isAVL_left&&isAVL_right&&Math.abs(leftDepth - rightDepth)<=1){
			return true;
		}
		
		return false;
	}
12、判断二叉树是否关于根节点对称(类似镜子)          1
   /    \
  2     2
 / \    / \
3  4 4  3
思路:递归解法 (1)如果二叉树为空,返回空 (2)如果二叉树不为空,则递归判断节点的左右节点 a.同时为空,则return  true b某一个节点为空则 return false c.都不为空但值不等,则 return false
public boolean isSymmetric(TreeNode root) {
        if(root==null){
        	return true;
        }
        //只有根节点
        if(root.left==null&&root.right==null){
        	return true;
        }
        
        return isSymmetricChildTree(root.left,root.right);
    }
	
	public boolean isSymmetricChildTree(TreeNode left,TreeNode right){
		if(left==null&&right==null){
			return true;
		}
		if((left!=null&&right==null)||(left==null&&right!=null)){
			return false;
		}
		if(left.val!=right.val){
			return false;
		}
		return isSymmetricChildTree(left.left, right.right)&&isSymmetricChildTree(left.right, right.left);
		
	}
13、输入两棵二叉树AB,判断B是否为A的子树 思路:(1)如果两棵树都为空,则return true       (2)如果两棵树都不为空,则在A中找B节点(递归查看左右子树)       (3)在A中找到B根节点以后判断其两棵树的左右子树是否相同。
	//输入两棵二叉树A和B,判断B是否为A的子树
	//遍历首先看A中是否有B的根节点。有的话查看该节点下的左右子节点。如果没有继续查找直到叶子节点。
	//用递归遍历
	//二叉树遍历 访问每个地址时,都要考察是否为null,为null时如何处理

	public boolean HasSubTree(BinaryTreeNode aRoot,BinaryTreeNode bRoot){
		boolean isHas = false;
		if(aRoot!=null&&bRoot!=null){
			if(aRoot.getKey() == bRoot.getKey()){
				//开始比对左右子节点
				isHas = isEqualChildTree(aRoot,bRoot);
			}
			if(!isHas){
				isHas = HasSubTree(aRoot.getLeftNode(), bRoot);
			}
			if(!isHas){
				isHas = HasSubTree(aRoot.getRightNode(), bRoot);
			}
		}
		return isHas;
	}

	public boolean isEqualChildTree(BinaryTreeNode aRoot,BinaryTreeNode bRoot){
		
		if(bRoot == null){
			return true;
		}
		if(aRoot == null){
			return false;
		}
		if(aRoot.getKey()!=bRoot.getKey()){
			return false;
		}
		 
		return isEqualChildTree(aRoot.getLeftNode(), bRoot.getLeftNode())&&
		isEqualChildTree(aRoot.getRightNode(), bRoot.getRightNode());
	}
14、求二叉树中节点的最大距离 思路:即二叉树中相距最远的两个节点之间的距离。 递归解法:
(1)如果二叉树为空,返回0,同时记录左子树和右子树的深度,都为0
(2)如果二叉树不为空,最大距离要么是左子树中的最大距离,要么是右子树中的最大距离,要么是左子树节点中到根节点的最大距离+右子树节点中到根节点的最大距离,同时记录左子树和右子树节点中到根节点的最大距离。



15、将二叉查找树变为有序的双向链表 思路: 二分查找树特点:左节点的值总小于父节点的值,右子节点的值总大于父节点的值
有序链表:根据二分查找树的特点采用中序遍历,这样得到的是有序序列。
(1)当二叉查找树为空,则双向链表头和尾都为NULL
(2)当二叉查找树不为空,则按中序遍历方法遍历二叉树
当左子树为空时,根节点为链表的首部。 当左子树不为空时,按中序遍历的顺序,当遍历到根节点时,左子树已转换为有序的链表,并且处在链表尾部的是最大节点,所以应该将链表尾部与根节点相连,则链表尾节点变为根节点。 当右子树为空时,则根节点为尾节点, 当右子树不为空时,根节点与右子树链表中第一个相连。
//将搜索二叉树转换为双向链表
	public BinaryTreeNode convert(BinaryTreeNode rooTreeNode){
		BinaryTreeNode headNode = null;
		if(rooTreeNode==null){
			return null;
		}else {
			convertTree(rooTreeNode,lastNode);
			System.out.println("lastkey:"+lastNode.getKey());
			//得到双向链表的头节点。lastNode指向的是链表的尾,一直向前访问
			BinaryTreeNode curNode = lastNode;
			while(curNode!=null&&curNode.getLeftNode()!=null){
				curNode = curNode.getLeftNode();
			}
			headNode = curNode;
		}
		return headNode;
	}
	
	public void convertTree(BinaryTreeNode node,BinaryTreeNode lastNode){
		//中序遍历(左中右)
		this.lastNode = lastNode;
		if(node==null){
			return;
		}
		BinaryTreeNode curNode = node;
		//左
		if(node.getLeftNode()!=null){
			convertTree(node.getLeftNode(), this.lastNode);
		}
		//中
		curNode.setLeftNode(this.lastNode);
		if(this.lastNode!=null){
			this.lastNode.setRightNode(curNode);
		}
		this.lastNode = curNode;
		//右
		if(node.getRightNode()!=null){
			convertTree(node.getRightNode(), this.lastNode);
		}
	}
16、剑指Offer面试题50:求树中两个节点的最低公共祖先节点 思路:两个都不为空,分别找到根节点到两个节点的路径,遍历路径中最后一个相同的节点即为最低公共祖先节点。  
* 具体情况1:若此普通树是搜索二叉树,则比较容易遍历时找到介于两个节点的节点即为最低父节点。因为搜索二叉树的左节点总小于根节点,右节点总大于根节点
* 具体情况2:若普通树不是二叉树,若有指向父节点的指针,则可以转换为求从这个节点到根节点的两个链表的第一个父节点。
* 具体情况3:此普通树即不是二叉树,也没有指向父节点的指针,则考虑从根节点到两个节点的路径找到最后一个相同的节点

	Stack<BinaryTreeNode> path1 = new Stack<BinaryTreeNode>();
	Stack<BinaryTreeNode> path2 = new Stack<BinaryTreeNode>();
	public boolean getNodePath(BinaryTreeNode rootNode,BinaryTreeNode node,Stack<BinaryTreeNode> path){
		boolean found = false;
		if(rootNode==null){
			return false;
		}
		path.push(rootNode);
		if(rootNode.getValue()==node.getValue()){
			return true;
		}else {
			if(rootNode.getLeftNode()!=null){
				found = getNodePath(rootNode.getLeftNode(), node, path);
				if(found){
					return true;
				}
			}
			if(rootNode.getRightNode()!=null){
				found = getNodePath(rootNode.getRightNode(), node, path);
				if(found){
					return true;
				}
			}
		}
		if(!found){
			path.pop();
		}
		return found;
	}
	
	public BinaryTreeNode getLastNodeFromPath(Stack<BinaryTreeNode> path1,Stack<BinaryTreeNode> path2){
		if(path1.size()<0||path2.size()<0){
			return null;
		}
		BinaryTreeNode curNode = null;
		Iterator<BinaryTreeNode> iterator1 = path1.iterator();
		Iterator<BinaryTreeNode> iterator2 = path2.iterator();
		while(iterator1.hasNext()&&iterator2.hasNext()){
			BinaryTreeNode node1 = iterator1.next();
			BinaryTreeNode node2 = iterator2.next();
			System.out.println("node1:"+node1.getValue()+"node2:"+node2.getValue());
			if(node1==node2){
				//System.out.println("node1=node2:"+node1.getValue());
				curNode = node1;
			}
		}
		
		return curNode;
	}</span>
17、哈夫曼树的构建

哈夫曼树—最优二叉树,树的带权路径长度规定为所有叶子结点的带权路径长度之和,带权路径长度最短的树,即为最优二叉树。在最优二叉树中,权值较大的结点离根较近。

首先就需要构建一个哈夫曼树,一般利用优先级队列来构建哈夫曼树

以上面的消息为例,我们先来分析一下构建哈夫曼树的过程,下图中,if代表换行符,sp代表空格


首先,将字符按照频率插入一个优先级队列,频率越低越靠近队头,然后循环执行下面的操作:

1、取出队头的两个树

2、以它们为左右子节点构建一棵新树,新树的权值是两者之和

3、将这棵新树插入队列

直到队列中只有一棵树时,这棵树就是我们需要的哈夫曼树。

java 实现代码如下:

1.哈夫曼树的节点设计

public class Node {
	private Node leftNode;
	private Node rightNode;
	private Node nextNode;
	//关键字及其权重
	private String  key;
	private int frequence;
	
	public Node(int frequence,String key){
		this.key = key;
		this.frequence = frequence;
	}
	
	public Node getLeftNode() {
		return leftNode;
	}
	public void setLeftNode(Node leftNode) {
		this.leftNode = leftNode;
	}
	public Node getRightNode() {
		return rightNode;
	}
	public void setRightNode(Node rightNode) {
		this.rightNode = rightNode;
	}
	public Node getNextNode() {
		return nextNode;
	}
	public void setNextNode(Node nextNode) {
		this.nextNode = nextNode;
	}
	public String getKey() {
		return key;
	}
	public void setKey(String key) {
		this.key = key;
	}
	public int getFrequence() {
		return frequence;
	}
	public void setFrequence(int frequence) {
		this.frequence = frequence;
	}
	
}
2.创建哈夫曼树的辅助优先级队列

//优先级队列
public class PriorityQueue {
	private Node firstNode;
	private int length;
	
	public PriorityQueue(){
		firstNode = null;
		length = 0;
	}
	//构造优先级队列(插入元素)
	public void insert(Node node){
		if(firstNode == null){
			firstNode = node;
		}else {
			Node curNode = firstNode;
			Node preNode = null;
			//定位要插入节点的前一个和后一个
			while(curNode.getFrequence()<node.getFrequence()){
				preNode = curNode;
				if(curNode.getNextNode()==null){
					//到达队尾
					curNode = null;
					break;
				}else{
					//继续向下一个节点查找,直到找到
					curNode = curNode.getNextNode();
				}
			}
			
			if(preNode == null){
				//插入到firstNode之前
				node.setNextNode(firstNode);
				//设置指向新节点node
				firstNode = node;
			}else if(curNode == null){
				//到达队尾,放入preNode之后
				preNode.setNextNode(node);
			}else {
				//插入两个node之间
				preNode.setNextNode(node);
				node.setNextNode(curNode);
			}
		}
		length++;
	}
	//取队列头元素
	public Node getFirstNode(){
		Node tempNode  = firstNode;
		firstNode = firstNode.getNextNode();
		length--;
		return tempNode;
	} 
	//求队列深度
	public int getLength(){
		return length;
	}
	//按优先级打印队列
	public void PrintTree(){
		Node curNode = firstNode;
		System.out.print("优先级队列:\t");  
		while (curNode!=null) {
			System.out.print(curNode.getKey()+":"+curNode.getFrequence()+"\t");
			curNode = curNode.getNextNode();
		}
		System.out.println();
	}
	//构建哈夫曼树
	public HuffmanTree createHuffmanTree(){
		while(length>1){
			Node leftNode = getFirstNode();//得到左节点(从优先级队列中取第一个元素:最小权重的元素)
			Node rightNode = getFirstNode();//右节点(第二个小权重的元素)
			//新节点的权值=左右节点权值之和
			Node newNode = new Node((leftNode.getFrequence()+rightNode.getFrequence()),"");
			newNode.setLeftNode(leftNode);
			newNode.setRightNode(rightNode);
			insert(newNode);
		}
		return new HuffmanTree(firstNode);
	}
}
3.哈夫曼树实现类

private Node firstNode; 
	private Map treeMap = new HashMap();
	public HuffmanTree(Node firstNode){
		this.firstNode = firstNode; 
		createHuffmanTree(firstNode, "");
	}
	//创建哈夫曼编码
	private void createHuffmanTree(Node curNode,String curCode){
		if(curNode.getKey()!=null&&curNode.getKey()!=""){
			//因为哈弗曼树中新添加的节点是没有设置key的,所以一定为叶子节点,添加进去
			treeMap.put(curNode.getKey(),curCode);
		}else {
			//新添加的节点必定存在“左右节点”,
			//左右节点递归实现
			//转向左子节点需要将当前代码追加0  
			createHuffmanTree(curNode.getLeftNode(), curCode+"0");
			//转向右子节点需要将当前代码追加1
			createHuffmanTree(curNode.getRightNode(), curCode+"1");
		}
	}
	//对外提供访问权限
	public Map getTreeMap(){
		return treeMap;
	}




网友评论
<