【阳哥专栏】技术分活动第7期

cyc52tjm · cyc52tjm

请多多指教。

yqj · yqj

先看看题目‘。。

Franklin · Franklin

先来学习一下

cyc52tjm · cyc52tjm

就业指导－王震阳老师发表于 2014-8-2 23:41
自定义一个类，用该类来模拟一个二叉树结构，同时实现二叉树的遍历功能。 ...

请问遍历的时候是利用二叉树本身特点进行递归遍历（属内部遍历）？还是用二叉树的非递归遍历呢（属外部遍历）？我在在学校没学好，只了解内部遍历= =

喜爱 · 喜爱

对这个有点不太熟悉，存在一个疑问！

X11 · X11

基本实现了二叉树的功能，Junit测试也通过。有些算法可能写的不是很好，希望老师批评指正。谢谢。

justin1258 · justin1258

本帖最后由 justin1258 于 2014-8-3 17:55 编辑

做好喽~~

ysdolls · ysdolls

终于弄完了。。急缺技术分

justin1258 · justin1258

刚没有设权限，重新传一下

王震阳老师 · 王震阳老师

cyc52tjm 发表于 2014-8-3 12:34
请问遍历的时候是利用二叉树本身特点进行递归遍历（属内部遍历）？还是用二叉树的非递归遍历呢（属外部遍 ...

内部遍历、外部遍历如果都会最好，但是至少得写一种。

龙飞九天 · 龙飞九天

回帖领题！

justin1258 · justin1258

阳哥下午上传的题目你看了吗？过了今天是不是没有技术分领了？俺急需技术分{:3_65:}

grkbeyond · grkbeyond

领题啊。。。

陈立凯 · 陈立凯

网站有视频教程，为何没有相配套的练习呢？

七年锦·旅行 · 七年锦·旅行

huangxuanheng 发表于 2014-8-2 23:16
对数据结构是理解了，但是如何使用Java语言来创建二叉树还不太懂，能不能给个提示？ ...

数据结构我也接触过，在学校时，听老师好像讲过，感觉和介绍没有区别，现在都已经忘得差不多了！请问数据结构要怎么学呢？

ssy1939 · ssy1939

参考参考

王震阳老师 · 王震阳老师

X11 发表于 2014-8-3 13:36
基本实现了二叉树的功能，Junit测试也通过。有些算法可能写的不是很好，希望老师批评指正。谢谢。 ...

答案很给力，请大家参考：
自定义二叉树类：

package io;
import java.util.LinkedList;
import java.util.List;
/**
* 二叉树实现
*
* @author x11
*
* @param <E>
* 实现了Comparable接口的对象。
*/
public class BinaryTree<E extends Comparable<E>> {
private Node<E> root; // 根节点
private int size; // Tree的大小
/**
* 往二叉树中添加数据
*
* @param e
*/
public void add(E e) {
// e为null,抛出非法参数异常
if (e == null) {
throw new IllegalArgumentException("data can't be null!");
}
// 如果不存在根节点,创建根节点
if (root == null) {
root = new Node<E>(null, e);
size++;
} else {
Node<E> current = root;
Node<E> parent;
while (true) {
parent = current;
if (e.compareTo(parent.getData()) == 0) {
// do nothing.
// 节点已经存在，不储存。
return;
}
// 节点的值比当前节点的值小，存储到当前节点的左子节点上。
else if (e.compareTo(parent.getData()) < 0) {
current = current.getLeftChild();
if (current == null) {
Node<E> newNode = new Node<E>(parent, e);
parent.setLeftChild(newNode);
size++;
return;
}
}
// 节点的值比当前节点的值大，存储到当前节点的右子节点上。
else {
current = current.getRightChild();
if (current == null) {
Node<E> newNode = new Node<E>(parent, e);
parent.setRightChild(newNode);
size++;
return;
}
}
}
}
}
public void add(E[] array) {
for (E e : array ) {
add(e);
}
}
/**
* 清空二叉树
*/
public void clear() {
root = null;
size = 0;
}
/**
* 二叉树中是否包含e元素
*
* @param e
* @return
*/
public boolean contains(E e) {
if (e == null || root == null) {
return false;
}
Node<E> retNode = get(e);
return !(retNode == null);
}
/**
* 删除节点node及以node为父节点的子二叉树
* @param node
*/
public void remove(Node<E> node) {
remove(node.getData());
}
public void remove(E e) {
Node<E> retNode = get(e);
if (retNode == root) { //如果要删除的节点是根节点，则清空整个二叉树
clear();
return;
}
if (retNode != null) {
if (e.compareTo(retNode.getParent().getData()) < 0 ) {
retNode.getParent().setLeftChild(null); // 该节点为父节点的左子节点，删除该左节点
} else {
retNode.getParent().setRightChild(null);
}
}
}
/**
* 查找二叉树中是否存在某元素
*
* @param e
* @return 如果节点存在，返回该节点，否则返回null.
*/
public Node<E> get(E e) {
if (root == null)
return null;
Node<E> current = root;
while (!e.equals(current.getData())) {
if (e.compareTo(current.getData()) < 0) {
current = current.getLeftChild();
} else {
current = current.getRightChild();
}
if (current == null) {
return null;
}
}
return current;
}
/**
*
* @return 二叉树的大小
*/
public int size() {
return this.size;
}
/**
* 中序遍历(LDR: leftChild->root->rightChild)
* @return
*/
public List<E> inOrder() {
if (root == null)
return null;
List<E> list = new LinkedList<E>();
inOrderTraverse(root.getLeftChild(),list);
list.add(root.getData());
inOrderTraverse(root.getRightChild(), list);
return list;
}
private void inOrderTraverse(Node<E> child, List<E> list) {
// TODO Auto-generated method stub
if (child != null) {
inOrderTraverse(child.getLeftChild(), list);
list.add(child.getData());
inOrderTraverse(child.getRightChild(), list);
}
}
/**
* 前序遍历(DRL)
* @return
*/
public List<E> preOrder() {
if (root == null)
return null;
List<E> list = new LinkedList<E>();
list.add(root.getData());
preOrderTraverse(root.getRightChild(), list);
preOrderTraverse(root.getLeftChild(),list);
return list;
}
private void preOrderTraverse(Node<E> child, List<E> list) {
// TODO Auto-generated method stub
if (child != null) {
list.add(child.getData());
preOrderTraverse(child.getRightChild(), list);
preOrderTraverse(child.getLeftChild(),list);
}
}
/**
* 后序遍历(LRD)
* @return
*/
public List<E> postOrder() {
if (root == null)
return null;
List<E> list = new LinkedList<E>();
postOrderTraverse(root.getLeftChild(),list);
postOrderTraverse(root.getRightChild(), list);
list.add(root.getData());
return list;
}
private void postOrderTraverse(Node<E> child, List<E> list) {
// TODO Auto-generated method stub
if (child != null) {
postOrderTraverse(child.getLeftChild(),list);
postOrderTraverse(child.getRightChild(), list);
list.add(child.getData());
}
}
public String printTree() {
if (inOrder() == null)
return null;
else
return inOrder().toString();
}
}
/**
* 二叉树节点
*
* @author x11
*
* @param <E>
* 实现了Comparable接口的对象。
*/
class Node<E> {
private Node<E> parent; // 父节点
private Node<E> leftChild; // 左子节点
private Node<E> rightChild; // 右子节点
private E data; // 节点内数据
public Node(Node<E> parent, E data) {
super();
this.parent = parent;
this.data = data;
}
public Node<E> getParent() {
return parent;
}
public void setParent(Node<E> parent) {
this.parent = parent;
}
public Node<E> getLeftChild() {
return leftChild;
}
public void setLeftChild(Node<E> leftChild) {
this.leftChild = leftChild;
}
public Node<E> getRightChild() {
return rightChild;
}
public void setRightChild(Node<E> rightChild) {
this.rightChild = rightChild;
}
public E getData() {
return data;
}
public void setData(E data) {
this.data = data;
}
@Override
public String toString() {
return "Node [data=" + data + "]";
}
}

复制代码

Test类：

package io;
import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;
public class BinaryTreeTest {
BinaryTree<Integer> intBTree = null;
BinaryTree<String> strBTree = null;
Integer[] intArray;
String[] strArray;
@Before
public void before() {
intBTree = new BinaryTree<Integer>();
strBTree = new BinaryTree<String>();
intArray = new Integer[] { 6, 2, 7, 11, 8, 9, 25 };
strArray = new String[] { "h", "f", "b", "c", "d", "a" };
intBTree.add(intArray);
strBTree.add(strArray);
}
@Test
public void testAdd() {
intBTree.add(2); // 元素相同，无法加入
strBTree.add("a"); // 元素相同，无法加入
System.out.println(intBTree.printTree());
System.out.println(strBTree.printTree());
}
@Test
public void testClear() {
// fail("Not yet implemented");
intBTree.clear();
strBTree.clear();
System.out.println(intBTree.printTree());
System.out.println(strBTree.printTree());
}
@Test
public void testContains() {
System.out.println(intBTree.contains(6));
System.out.println(intBTree.contains(1));
System.out.println(strBTree.contains("a"));
System.out.println(strBTree.contains("y"));
}
@Test
public void testRemoveNodeOfE() {
// fail("Not yet implemented");
intBTree.remove(2);
strBTree.remove("c");
System.out.println(intBTree.printTree());
System.out.println(strBTree.printTree());
}
@Test
public void testRemoveE() {
fail("Not yet implemented");
}
@Test
public void testGet() {
// fail("Not yet implemented");
Node<Integer> val1 = intBTree.get(1);
Node<Integer> val2 = intBTree.get(6);
Node<String> val3 = strBTree.get("a");
Node<String> val4 = strBTree.get("z");
System.out.println(val1);
System.out.println(val2);
System.out.println(val3);
System.out.println(val4);
}
@Test
public void testSize() {
// fail("Not yet implemented");
System.out.println(intBTree.size());
System.out.println(strBTree.size());
}
@Test
public void testInOrder() {
// fail("Not yet implemented");
System.out.println(intBTree.inOrder().toString());
System.out.println(strBTree.inOrder().toString());
}
@Test
public void testPreOrder() {
// fail("Not yet implemented");
System.out.println(intBTree.preOrder().toString());
System.out.println(strBTree.preOrder().toString());
}
@Test
public void testPostOrder() {
// fail("Not yet implemented");
System.out.println(intBTree.postOrder().toString());
System.out.println(strBTree.postOrder().toString());
}
@Test
public void testPrintTree() {
fail("Not yet implemented");
}
}

复制代码

Hello_U · Hello_U

就看看吧，自己做做试试

yqj · yqj

本帖最后由 yqj 于 2014-8-4 22:27 编辑

刚写完测试中，没想到结果已经公布了，学习中

王震阳老师 · 王震阳老师

cyc52tjm 发表于 2014-8-3 10:56
请多多指教。

挺好：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
/**
* ①用Java代码模拟实现一个二叉树结构②创建该二叉树③遍历该二叉树。
*
* @author Administrator TODO
*/
class DemoTree {
public static void main(String[] args) throws IOException {
int value;
// 创建树对象
Tree theTree = new Tree();
// 添加元素
theTree.insert(50);
theTree.insert(75);
theTree.insert(12);
theTree.insert(37);
theTree.insert(43);
theTree.insert(30);
theTree.insert(33);
theTree.insert(87);
theTree.insert(93);
theTree.insert(97);
theTree.insert(50);
while (true) {
System.out.println("a.查看树结构。");
System.out.println("b.遍历树。");
System.out.println("请输入a,b");
int choice = getChar();
switch (choice) {
// 查看树结构
case 'a':
theTree.displayTree();
break;
case 'b':
System.out.println("1.前序遍历:");
System.out.println("2，中序遍历");
System.out.println("3.后序遍历");
System.out.println("请选择1,2,3");
value = getInt();
theTree.traverse(value);
break;
default:
System.out.println("格式不正確\n");
}
}
}
public static char getChar() throws IOException {
String s = getString();
return s.charAt(0);
}
public static String getString() throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
public static int getInt() throws IOException {
String s = getString();
return Integer.parseInt(s);
}
}
//二叉树中每个节点对象
class Node {
//节点的数据
public int iData;
//节点左孩子
public Node leftChild;
//节点的右孩子
public Node rightChild;
public void displayNode(){
}
}
//二叉树的结构对象
class Tree {
//叉树的根节点
private Node root;
public Tree(){
root = null;
}
/**
* 添加元素
* @param id 节点的值
*/
public void insert(int id){
//创建新节点
Node newNode = new Node();
newNode.iData = id;
//如果树是空的，就将新节点作为根
if(root == null){
root = newNode;
}
//否则，作为根的孩子
else{
Node current = root;
Node parent;
while(true){
parent = current;
//如果节点的值小于父节点的值并父节点没有左孩子，它就作为父节点左孩子
if(id < current.iData){
current = current.leftChild;
if(current ==null){
parent.leftChild = newNode;
return;
}
}
//如果节点的值大于父节点的值并父节点没有右孩子，它就作为父节点右孩子
if(id > current.iData){
current = current.rightChild;
if(current == null){
parent.rightChild = newNode;
return;
}
}
//否则节点值等于父节点的值，直接返回
else{
return;
}
}
}
}
/**
* （内部）遍历树
* @param traverseType 输入的数字
*/
public void traverse(int traverseType){
switch(traverseType){
case 1:
System.out.println("\n前序遍历:");
preOrder(root);
break;
case 2:
System.out.println("\n中序遍历:");
inOrder(root);
break;
case 3:
System.out.println("\n后序遍历:");
postOrder(root);
break;
default:
System.out.println("输入不正确");
}
System.out.println();
}
//前序遍历
private void preOrder(Node localRoot){
if(localRoot!=null){
System.out.print(localRoot.iData+" ");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
//中序遍历
private void inOrder(Node localRoot){
if(localRoot!=null){
inOrder(localRoot.leftChild);
System.out.print(localRoot.iData+" ");
inOrder(localRoot.rightChild);
}
}
//后序遍历
private void postOrder(Node localRoot){
if(localRoot!=null){
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.print(localRoot.iData+" ");
}
}
/**
* 展示树结构的排列方式
*/
public void displayTree(){
//创建一个栈
Stack globalStack = new Stack();
//现将树压栈
globalStack.push(root);
//树中的节点数减1
int nBlanks = 32;
boolean isRowEmpty =false;
System.out.println("-------------------------------------------");
while(isRowEmpty == false){
Stack localStack = new Stack();
isRowEmpty = true;
for(int j=0;j<nBlanks;j++){
System.out.print(" ");
}
while(globalStack.isEmpty() == false){
Node temp = (Node)globalStack.pop();
if(temp!=null){
System.out.print(temp.iData);
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);
if(temp.leftChild !=null||temp.rightChild !=null)
isRowEmpty = false;
}
else{
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for(int j=0;j<nBlanks*2-2;j++)
System.out.print(" ");
}
System.out.println();
System.out.println();
nBlanks /= 2;
while(localStack.isEmpty()==false)
globalStack.push(localStack.pop());
}
System.out.println("-------------------------------------");
}
}

复制代码

帐号		自动登录	找回密码
密码			加入黑马

【阳哥专栏】技术分活动第7期

评分

评分

评分

评分

评分

黑马骑士勋章