递归调用

题目描述：

 要求：写一个函数void count(char* input,int len)，此函数的功能是计算出一个字符串中每个字符的个数，不区分 大小写，输出结果时按字符在字符串中出现的先后顺序。使用程序语言不限。

例如：input="abCcbdfe"，输出结果是a:1 b:2 c:2 d:1 f:1 e:1 *

思路 ：构造一颗完全2叉树，每个结点储存1个value和此value出现的次数

难点：如何添加新结点

总结：对递归理解不深刻，2叉树理解不深刻

未解决：显示顺序不正确

代码

 

package com.ysb;
/*
 *  要求：写一个函数void count(char* input,int len)，此函数的功能是计算出一个字符串中每个字符的个数，不区分大小写，输出结果时按字符在字符串中出现的先后顺序。使用程序语言不限。
	例如：input="abCcbdfe"，输出结果是a:1 b:2 c:2 d:1 f:1 e:1 *
	
	使用2叉树实现 例子中的对应的2叉树
				   a1
			b2	        c2
		d1      f1   e1   g1
	 h1	  i1  		
	 
 */
public class Main {
	
	public static void main(String[] args) {
		
		new Main().start();
	}
	public void start() {
		String input = "abcabcdeabcfgghfghswrwer";
		Tree tree = new Tree();
		Node rootNode = new Node();
		rootNode.setValue(input.charAt(0));
		rootNode.setCount(1);
		rootNode.setParentNode(null);
		tree.setRootNode(rootNode);
		tree.setDeep(1);
		tree.setCount(1);
		//构建2叉数
		for(int i = 1;i<input.length();i++) {
			char c = input.charAt(i);
			//如果找不到该字符，则创建新节点，这里是难点啊
			Node node = listTree(tree.getRootNode(), c);
			if(node == null) {
				Node newNode = new Node();
				newNode.setCount(1);
				newNode.setValue(c);
				//增加1个结点
				addNewNode( tree, newNode);
			}
			else {
				node.setCount(node.getCount()+1);
			}
		}
		showResult(tree);
	}
	private void addNewNode(Tree tree, Node newNode) {
		Node rootNode = tree.getRootNode();
		Node parentNode = findParentNode(rootNode);
		if(parentNode.getLeftNode() == null)
			parentNode.setLeftNode(newNode);
		else
			parentNode.setRightNode(newNode);
		tree.setCount(tree.getCount()+1);
		int count = 1;
		for(int i=1;i<=tree.getDeep();i++)
			count = 2*count;
		count = count -1;
		if(tree.getCount() > count)
			tree.setDeep(tree.getDeep()+1);
		
	}
    /*
     * 返回第一个缺少子树的节点
     */
	private Node findParentNode(Node node) {
		
		Node testNode;
		if(node.getLeftNode() == null || node.getRightNode()==null)
			return node;
		else {
			Node leftNode = node.getLeftNode();
			testNode = 	findParentNode(leftNode);
			if(testNode!=null)
				return testNode;
			Node rightNode = node.getRightNode();
			testNode =findParentNode(rightNode);
			if(testNode!=null)
				return testNode;
		}
		return null;
	}
	/**
	 * @param node   传入的根节点
	 * @param value  比较的char值
	 * @return 如果有节点的value值与传入的value值相同，则返回该节点
	 *         否则返回null
	 */
	public  Node listTree(Node node,char value) {	
		Node testNode;
		if(node!=null) {
			char c = node.getValue();
			if(c == value)
					return node;
			testNode = listTree(node.getLeftNode(),value);
			if(testNode!=null) {
				return testNode;
			}
			testNode = listTree(node.getRightNode(),value);
			if(testNode!=null) {
				return testNode;
			}
		}
		return null;
	}
	public void visitNode(Node node) {
		if(node!=null) {
			System.out.println(node.getValue()+":"+node.getCount());
			visitNode(node.getLeftNode());
			visitNode(node.getRightNode());
		}
	}
	//显示结果有问题，并没有按照字符出现的顺序，而是按照树的遍历顺序，这个再说
	public void showResult(Tree tree) {
		Node rootNode = tree.getRootNode();
		visitNode(rootNode);
	}
}

Tree的数据结构

package com.ysb;

public class Tree {
	//树的深度，从1开始
	private int deep;
	//树的根结点
	private Node rootNode;
	//树的结点数
	private int count;
	public int getCount() {
		return count;
	}
	public void setCount(int count) {
		this.count = count;
	}
	public int getDeep() {
		return deep;
	}
	public void setDeep(int deep) {
		this.deep = deep;
	}
	public Node getRootNode() {
		return rootNode;
	}
	public void setRootNode(Node rootNode) {
		this.rootNode = rootNode;
	}
	
}

   Node的数据结构

package com.ysb;

public class Node {
	private Node leftNode;
	private Node rightNode;
	private Node parentNode;
	private char value;
	private int count;
	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 char getValue() {
		return value;
	}
	public void setValue(char value) {
		this.value = value;
	}
	public int getCount() {
		return count;
	}
	public void setCount(int count) {
		this.count = count;
	}
	public Node getParentNode() {
		return parentNode;
	}
	public void setParentNode(Node parentNode) {
		this.parentNode = parentNode;
	}
	

}

 

评论

2 楼 sambean 2010-11-27  

chinpom 写道

这个题目，用得着写这么多代码用二叉树吗？是不是LZ把问题搞复杂了，还是必须得用递归？

不是啊，我只是试试二叉树咯。。

1 楼 chinpom 2010-11-05  

这个题目，用得着写这么多代码用二叉树吗？是不是LZ把问题搞复杂了，还是必须得用递归？