经典题集之树三

//1.将二叉树汇的根节点到每一个叶子结点的路径分别打印出来
	public void printfLeafToRootPath(Node root,int path[],int pathLen) {
		if(root == null) return ;
		path[pathLen] = root.data;
		pathLen++;
		if(root.leftchild == null && root.rightchild == null)
			Print(path,pathLen);
		else {
			printfLeafToRootPath(root.leftchild, path, pathLen);
			printfLeafToRootPath(root.rightchild, path, pathLen);
		}
	}
	public void Print(int path[],int pathLen) {
		for(int i=0;i<pathLen;i++)
			System.out.println(path[i]);
	}
	//2.判断树中有没有一条连接根节点与叶节点的路径，其中各节点的数据之和等于调用方法锁指定的总和。
	public boolean HasSumPath(Node root,int sum) {
		if(root == null) 
			return false;
		else {
			int remain = sum - root.data;
			if((root.leftchild != null && root.rightchild != null) 
				|| (root.leftchild == null && root.rightchild == null))
				return
						HasSumPath(root.leftchild, remain)
						|| HasSumPath(root.rightchild, remain);
			else if(root.leftchild != null)
				return 
						HasSumPath(root.leftchild, remain);
			else
				return 
						HasSumPath(root.rightchild,remain);
		}
	}
	//2.求二叉树的所有元素之和
	public int SumOfBinaryTreeUseRecursive(Node root) {
		if(root == null)
			return 0;
		else
			return (root.data + SumOfBinaryTreeUseRecursive(root.leftchild) + SumOfBinaryTreeUseRecursive(root.rightchild));
	}
	
	public int SumOfBinaryTreeNoUseRecursive(Node root) {
		Node temp;
		Queue<Node> queue = new ArrayDeque<Node>();
		int sum = 0;
		queue.add(root);
		while(!queue.isEmpty()) {
			temp = queue.poll();
			sum += temp.data;
			if(temp.leftchild != null)
				queue.add(temp.leftchild);
			if(temp.rightchild != null)
				queue.add(temp.rightchild);
		}
		return sum;
	}
	//3.求树的镜像
	public Node MirrorOfBinaryTree(Node root) {
		Node temp;
		if(root != null) {
			MirrorOfBinaryTree(root.leftchild);
			MirrorOfBinaryTree(root.rightchild);
			temp = root.leftchild;
			root.leftchild = root.rightchild;
			root.rightchild = temp;
		}
		return root;
	}
	//4.判断两颗树是否为镜像
	public boolean AreMirrorOfBinaryTree(Node root1,Node root2) {
		if(root1 == null && root2 == null)
			return true;
		if(root1 == null || root2 == null)
			return false;
		if(root1.data != root2.data)
			return false;
		else
			return
					AreMirrorOfBinaryTree(root1.leftchild, root2.rightchild)
				&&  
					AreMirrorOfBinaryTree(root2.leftchild, root1.rightchild);
	}
		//5.打印二叉树特定节点的所有祖先
	public boolean PrintAncestors(Node root,Node node) {
		if(root == null)
			return false;
		if(root.leftchild == node || root.rightchild == node ||
				PrintAncestors(root.leftchild, node) || PrintAncestors(root.rightchild, node)) {
			System.out.println(root.data);
			return true;
		}
		return false;
	}
	//6.曲折遍历
	public void ZigZagTraversal(Node root) {
		if(root == null) return ;
		Node temp;
		Stack<Node> tempStack ;
		Stack<Node> current =new Stack<Node>();
		Stack<Node> next = new Stack<Node>();
		boolean leftToRight = true;
		while(!current.isEmpty()) {
			temp = current.pop();
			if(temp != null) {
				System.out.println(temp.data);
				if(leftToRight) {
					if(temp.leftchild != null)
						next.push(temp.leftchild);
					if(temp.rightchild != null)
						next.push(temp.rightchild);
				}else {
					if(temp.rightchild != null)
						next.push(temp.rightchild);
					if(temp.leftchild != null)
						next.push(temp.leftchild);
				}
			}
			if(current.isEmpty()) {
				leftToRight = false;
				tempStack = current;
				current = next;
				next = tempStack;
			}
		}
	}
	//7.在二叉搜索树中查找元素
	public Node FindElementUseRecursive(Node root,int data) {
		if(root == null) return null;

		if(data < root.data) return FindElementUseRecursive(root.leftchild,data);
		else if( data > root.data) return FindElementUseRecursive(root.rightchild, data);
		else return root;
	}
	public Node FindElementNoRecursive(Node root ,int data) {
		if(root == null) return null;
		while(root != null) {
			if(root.data > data)
				root = root.leftchild;
			else if(root.data < data)
				root = root.rightchild;
			else
				return root;
		}
		return null;
	}
	//8.在二叉搜索树中寻找最小的元素
	public Node FindMinElementUseRecursive(Node root) {
		if(root == null) 
			return null;
		else {
			if(root.leftchild == null)
				return root;
			else 
				return FindMinElementUseRecursive(root.leftchild);
		}
	}
	public Node FindMinElementNoRecursive(Node root) {
		if(root == null) return null;
		while(root.leftchild != null) 
			root = root.leftchild;
		return root;
	}
	//9.在二叉搜索树中寻找最大的元素
	public Node FindMaxElementUseRecursive(Node root) {
		if(root == null)
			return null;
		else {
			if(root.rightchild == null)
				return root;
			else 
				return FindMaxElementUseRecursive(root.rightchild);
		}	
	}
	public Node FindMaxElementNoRecursive(Node root) {
		if(root == null)
			return null;
		while(root.rightchild != null)
			root = root.rightchild;
		return root;
	}
	//10.从二叉树中删除元素
	public Node DeleteNodeFromBinaryTree(Node root,int data) {
		Node temp;
		if(root == null)
			System.out.println("NO DATA");
		else if(data < root.data)
			root.leftchild = DeleteNodeFromBinaryTree(root.leftchild, data);
		else if(data> root.data)
			root.rightchild = DeleteNodeFromBinaryTree(root.rightchild, data);
		else {
			if(root.leftchild != null && root.rightchild != null) {
				temp = FindMaxElementNoRecursive(root.leftchild);
				root.data = temp.data;
				root.leftchild = DeleteNodeFromBinaryTree(root.leftchild, data);
			}else {
				temp= root;
				if(root.leftchild == null)
					root = root.rightchild;
				else if(root.rightchild == null)
					root = root.leftchild;
			}
		}
		return root;
	}