`

java二叉树1

 
阅读更多
树是有穷节点的组,其中有一个节点作为根,根下面的其余节点以层次化方式组织。引用其下节点的节点是父节点,类似,由上层节点引用的节点是孩子节点。没有孩子的节点是叶子节点。一个节点可能同时是父节点和子节点。
一个父节点可以引用所需的多个孩子节点。在很多情况下,父节点至多只能引用两个孩子节点,基于这种节点的树称为二叉树。图13给出了一棵以字母表顺序存储了七个String单词的二叉树。
在二叉树或其他类型的树中都是使用递归来插入,删除和遍历节点的。出于简短的目的,我们并不深入研究递归的节点插入,节点删除和树的遍历算法。我们改为用清单19中的一个单词计数程序的源代码来说明递归节点插入和树的遍历。代码中使用节点插入来创建一棵二叉树,其中每个节点包括一个单词和词出现的计数,然后藉由树的中序遍历算法以字母表顺序显示单词及其计数。
Listing 19. WC.java

// WC.java

import java.io.*;

class TreeNode
{
String word; // Word being stored.
int count = 1; // Count of words seen in text.
TreeNode left; // Left subtree reference.
TreeNode right; // Right subtree reference.

public TreeNode (String word)
{
this.word = word;
left = right = null;
}

public void insert (String word)
{
int status = this.word.compareTo (word);

if (status > 0) // word argument precedes current word
{
// If left-most leaf node reached, then insert new node as
// its left-most leaf node. Otherwise, keep searching left.

if (left == null)
left = new TreeNode (word);
else
left.insert (word);
}
else
if (status < 0) // word argument follows current word
{
// If right-most leaf node reached, then insert new node as
// its right-most leaf node. Otherwise, keep searching right.

if (right == null)
right = new TreeNode (word);
else
right.insert (word);
}
else
this.count++;
}
}

class WC
{
public static void main (String [] args) throws IOException
{
int ch;

TreeNode root = null;

// Read each character from standard input until a letter
// is read. This letter indicates the start of a word.

while ((ch = System.in.read ()) != -1)
{
// If character is a letter then start of word detected.

if (Character.isLetter ((char) ch))
{
// Create StringBuffer object to hold word letters.

StringBuffer sb = new StringBuffer ();

// Place first letter character into StringBuffer object.

sb.append ((char) ch);

// Place all subsequent letter characters into StringBuffer
// object.

do
{
ch = System.in.read ();

if (Character.isLetter ((char) ch))
sb.append ((char) ch);
else
break;
}
while (true);

// Insert word into tree.

if (root == null)
root = new TreeNode (sb.toString ());
else
root.insert (sb.toString ());
}
}

display (root);
}

static void display (TreeNode root)
{
// If either the root node or the current node is null,
// signifying that a leaf node has been reached, return.

if (root == null)
return;

// Display all left-most nodes (i.e., nodes whose words
// precede words in the current node).

display (root.left);

// Display current node''s word and count.

System.out.println ("Word = " + root.word + ", Count = " +
root.count);

// Display all right-most nodes (i.e., nodes whose words
// follow words in the current node).

display (root.right);
}
}
因为已经有很多注释了,在这儿我们就不讨论代码了。代之,建议你如下运行这个应用程序:要计数文件中的单词数,打开一个包括重定位符<的命令行。例如,发出java WC <WC.java命令来计数文件WC.java中的单词数。那个命令的输出如下:
Word = Character, Count = 2
Word = Count, Count = 2
Word = Create, Count = 1
Word = Display, Count = 3
Word = IOException, Count = 1
Word = If, Count = 4
Word = Insert, Count = 1
Word = Left, Count = 1
Word = Otherwise, Count = 2
Word = Place, Count = 2
Word = Read, Count = 1
Word = Right, Count = 1
Word = String, Count = 4
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics