0815-二叉树

第一题：

 

在一棵一般的二叉树中找到指定的元素，如果有重复出现的元素，要求元素为深度最深的任何一个。
指定元素找不到时返回EMPTY_NODE，请用C语言实现，相关数据结构与函数声明如下：
struct Node
{
int iValue;
int id;
Node *pLeft;
Node *pRight;
};

const Node EMPTY_NODE = {0, 0, NULL, NULL};
Node findDeepest(Node *pRoot, int iWanted); //pRoot为根节点，wanted为指定元素的iValue

 

-----------------------------------------------------------------------------------------------------------------

第二题：

（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。

（3）判断是否为满二叉树
完全二叉树定义为：深度为K，具有N 个结点的二叉树的每个结点都与深度为K 的满二叉树中编号从
1 至N 的结点一一对应。此题以此定义为准。

--------------------------------------------------------------------------------------------------------------------

第三题：求二叉树节点的最大距离

 

 

package org.jyjiao;

import java.util.LinkedList;

class BiTreeNode {
	char data;
	BiTreeNode leftChild, rightChild;

	public BiTreeNode() {
	}

	public BiTreeNode(char data, BiTreeNode leftChild, BiTreeNode rightChild) {
		this.data = data;
		this.leftChild = leftChild;
		this.rightChild = rightChild;
	}

	public char getData() {
		return data;
	}

	public void setData(char data) {
		this.data = data;
	}

	public BiTreeNode getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(BiTreeNode leftChild) {
		this.leftChild = leftChild;
	}

	public BiTreeNode getRightChild() {
		return rightChild;
	}

	public void setRightChild(BiTreeNode rightChild) {
		this.rightChild = rightChild;
	}

}

class BiTree {
	BiTreeNode root;

	public BiTree() {
		root = null;
	}

	/*
	 * 创建一棵二叉树
	 */
	public BiTreeNode createTree() {
		BiTreeNode root = null;
		BiTreeNode nodeD = new BiTreeNode('d', null, null);
		BiTreeNode nodeE = new BiTreeNode('e', null, null);
		BiTreeNode nodeF = new BiTreeNode('f', null, null);
		BiTreeNode nodeG = new BiTreeNode('g', null, null);
		BiTreeNode nodeB = new BiTreeNode('b', nodeD, nodeE);
		BiTreeNode nodeC = new BiTreeNode('c', nodeB, nodeG);
		BiTreeNode nodeA = new BiTreeNode('a', nodeB, nodeC);
		root = nodeA;
		return root;

	}

	/* 获得二叉树的节点个数 */
	public int getTreeSize(BiTreeNode root) {
		if (root == null) {
			return 0;
		} else {
			return (1 + getTreeSize(root.getLeftChild()) + getTreeSize(root
					.getRightChild()));

		}
	}

	/* 获得树的高度 */
	public int getTreeHeight(BiTreeNode root) {
		if (root == null) {
			return -1;
		} else {
			return 1 + (getTreeHeight(root.getLeftChild()) > getTreeHeight(root
					.getRightChild()) ? getTreeHeight(root.getLeftChild())
					: getTreeHeight(root.getRightChild()));
		}
	}


	/*
	 * 判断是否为满二叉树 满二叉树的元素个数为n，高度为h，那么n=2^h-1 (h从1开始计数)
	 * 层次遍历二叉树，计算元素的个数和高度，最后利用满二叉树的性质判断即可
	 */
	public boolean isFull(BiTreeNode root) {
		boolean ret = false;

		int size = this.getTreeSize(root);
		System.out.println("size=" + size);
		int height = this.getTreeHeight(root);
		System.out.println("height=" + height);
		if (size == (Math.pow(2, height) - 1)) {
			return true;
		}
		return ret;
	}

	/*
	 * 判断是否为完全二叉树 层次遍历二叉树，如果遇到第一个子节点为null后，再有节点的子节点不为null，则不是完全二叉树；否则是完全二叉树。
	 */
	public boolean isComplete(BiTreeNode root) {
		boolean ret = true;
		int tag = 0;
		int front = 0, rear = 0;
		LinkedList<BiTreeNode> biQueue = new LinkedList<BiTreeNode>();
		biQueue.add(root);
		rear++;
		while (front != rear) {
			BiTreeNode delNode = biQueue.get(front++);
			if (delNode.getLeftChild() != null) {
				if (tag == 1) {
					return false;
				} else {
					biQueue.add(delNode.getLeftChild());
					rear++;
				}
			} else {
				tag = 1;
			}

			if (delNode.getRightChild() != null) {
				if (tag == 1) {
					return false;
				}
				biQueue.add(delNode.getRightChild());
				rear++;
			} else {
				tag = 1;
			}

		}

		return ret;

	}

	/* 递归：判断一个节点是否在树中，如果在树中，求该节点在树中的最深的层次；如果不在返回 -1
	 * 算法缺点：如果要找的节点为根节点，并且下面还有和根节点值相同的节点，只会返回1（根节点所在高度） 
	 */
	public int findDeapestNode(BiTreeNode fNode, BiTreeNode root) {
		int leftHeight=-1,rightHeight=-1;
		if (root == null) {
			return -1;
		}
		if(root.getData() == fNode.getData()) {
			return 1;
		}
		
		if(root.getLeftChild()!=null){
			leftHeight=this.findDeapestNode(fNode, root.getLeftChild());
		}
		if(root.getRightChild()!=null){
			rightHeight=this.findDeapestNode(fNode, root.getRightChild());
		}
		
		if(leftHeight<0 && rightHeight<0){
			return -1;
		}
		int height=leftHeight<rightHeight?rightHeight:leftHeight;
		return 1+height;

	}

	/* 层次遍历：判断一个节点是否在树中，如果在树中，求该节点在树中的最深的层次；如果不在返回 -1 */
	public int findDeapestNode2(BiTreeNode fNode, BiTreeNode root) {
		int height=1,maxHight=0,front=0,rear=0,last=0;
		
		LinkedList<BiTreeNode> queue=new LinkedList<BiTreeNode>();
		queue.add(root);
		rear++;
		
		while(front!=rear){
			BiTreeNode delNode=queue.get(front++);
			if(delNode.getData()==fNode.getData()){
				maxHight=height;
			}
			if(delNode.getLeftChild()!=null){
				queue.add(delNode.getLeftChild());
				rear++;
			}
			if(delNode.getRightChild()!=null){
				queue.add(delNode.getRightChild());
				rear++;
			}
			if(front>last){
				last=rear;
				height++;
			}	
		}
		if(maxHight==0){
			return -1;
		}
		
		return maxHight;
				
		
	}
	
	
	/*
	 * 创建一棵节点为n的二叉树
	 */
	public BiTreeNode createTree(int n) {
		BiTreeNode[] queue = new BiTreeNode[n];
		int front = 0, rear = 0;
		int count = 0;
		try {
			char c = (char) System.in.read();
			BiTreeNode node = new BiTreeNode();
			node.setData(c);
			node.setLeftChild(null);
			node.setRightChild(null);
			queue[rear++] = node;
			root = node;
			count++;

			while ((count < n) && (front < rear)) {
				BiTreeNode parNode = queue[front++];

				if ((count + 1) < n) {
					c = (char) System.in.read();
					if (c != '#') {
						count++;
						BiTreeNode leftNode = new BiTreeNode();
						leftNode.setData(c);
						leftNode.setLeftChild(null);
						leftNode.setRightChild(null);
						parNode.setLeftChild(leftNode);
						queue[rear++] = leftNode;
					}
				}

				if ((count + 1) < n) {
					c = (char) System.in.read();
					if (c != '#') {
						count++;
						BiTreeNode rightNode = new BiTreeNode();
						rightNode.setData(c);
						rightNode.setLeftChild(null);
						rightNode.setRightChild(null);
						parNode.setRightChild(rightNode);
						queue[rear++] = rightNode;
					}
				}
			}
		} catch (Exception ex) {
			ex.printStackTrace();
		}

		int i = 0;
		while (queue[i] != null) {
			System.out.print(queue[i].getData() + ",");
			i++;
		}

		return root;
	}
}

public class TreeJudge {

	public static void main(String[] args) {
		BiTree tree = new BiTree();
		BiTreeNode root = tree.createTree();

		if (tree.isFull(root)) {
			System.out.println("the tree is full");
		} else {
			System.out.println("the tree is not full");
		}

		if (tree.isComplete(root)) {
			System.out.println("the tree is complete");
		} else {
			System.out.println("the tree is not complete");
		}
		
		System.out.println("deapest="+tree.findDeapestNode2(new BiTreeNode('b',null,null), root));

	}

}

// 另：参考：http://www.docin.com/p-62909092.html