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

王震阳老师 · 王震阳老师

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("-------------------------------------");
}
}

复制代码

王震阳老师 · 王震阳老师

bbdeyouxang 发表于 2014-8-2 16:00
交题！！！

挺好：

package com.itheima.TechnologyScore;
/**
* Description: 创建二叉树，并遍历,按下面的样子建二叉树
* 1
* 2 3
* 4 5 6 7
*8 9 10 11 12 13 14 15
* @author hzChen
* @date 2014-8-2
*/
public class BinaryTreeTest
{
public static void main(String[] args) {
Integer[] intArray = new Integer[15];
for (int i = 0; i < 15; i++) {
intArray[i] = i + 1;
}
//写的二叉树构造不限制顺序，不过为了看起来方便，构造数组从1到15
//创建一个二叉树
BinaryTree bt = new BinaryTree(intArray);
String result = null;
//前序遍历一个二叉树
result = bt.preAllBinaryTree(bt.getRootNode(), new StringBuilder()).toString();
System.err.println(result);
//中序遍历一个二叉树
result = bt.middleAllBinaryTree(bt.getRootNode(), new StringBuilder()).toString();
System.err.println(result);
//后序遍历一个二叉树
result = bt.lastAllBinaryTree(bt.getRootNode(), new StringBuilder()).toString();
System.err.println(result);
}
}
/**
*
* <p>定义一个二叉树</p>
*/
class BinaryTree
{
/** 根节点 */
private Node rootNode = new Node();
/**构造方法,通过传入的数组创建二叉树*/
BinaryTree(Integer[] intArray){
createTree(rootNode, intArray, 0);
}
/**
* 功能描述：递归构建二叉树
* @param parent 父节点
* @param intArray 完整数组
* @param index 父节点在数组中的索引值
*/
private void createTree(Node parent, Integer[] intArray, Integer index){
parent.setNodeValue(intArray[index]);
if(2 * index + 1 < intArray.length){//存在左叶子
Node leftNode = new Node(intArray[2 * index + 1]);
parent.setLeftNode(leftNode);
createTree(leftNode, intArray, 2 * index + 1);
}
if(2 * index + 2 < intArray.length){//存在右叶子
Node rightNode = new Node(intArray[2 * index + 2]);
parent.setRightNode(rightNode);
createTree(rightNode, intArray, 2 * index + 2);
}
}
/** 递归遍历而二叉树前序根左右 */
public StringBuilder preAllBinaryTree(Node parent, StringBuilder sb){
if(null != parent){//到叶子节点停止递归
sb.append(parent.getNodeValue()+" ");
preAllBinaryTree(parent.getLeftNode(), sb);
preAllBinaryTree(parent.getRightNode(), sb);
}
return sb;
}
/** 递归遍历而二叉树中序左根右 */
public StringBuilder middleAllBinaryTree(Node parent, StringBuilder sb) {
if(null != parent){//到叶子节点停止递归
preAllBinaryTree(parent.getLeftNode(), sb);
sb.append(parent.getNodeValue()+" ");
preAllBinaryTree(parent.getRightNode(), sb);
}
return sb;
}
/** 递归遍历而二叉树后序左右根 */
public StringBuilder lastAllBinaryTree(Node parent, StringBuilder sb) {
if(null != parent){//到叶子节点停止递归
preAllBinaryTree(parent.getLeftNode(), sb);
preAllBinaryTree(parent.getRightNode(), sb);
sb.append(parent.getNodeValue()+" ");
}
return sb;
}
public Node getRootNode() {
return rootNode;
}
public void setRootNode(Node rootNode) {
this.rootNode = rootNode;
}
}
/**
* <p>定义节点</p>
*/
class Node
{
private Node leftNode;
private Node rightNode;
private Integer nodeValue;
Node(){
}
// 构造方法
Node(Integer nodeValue)
{
this.leftNode = null;
this.rightNode = null;
this.nodeValue = nodeValue;
}
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 Integer getNodeValue() {
return nodeValue;
}
public void setNodeValue(Integer nodeValue) {
this.nodeValue = nodeValue;
}
}

复制代码

王震阳老师 · 王震阳老师

执笔梦发表于 2014-8-2 20:22
学习，学习，以前学过，不过差不多都还给老师了，感觉最麻烦的就是泛型了 ...

挺好：

package cc.tree.domain;
/**
* 二叉树只有一个根节点，每个节点最多有两个子树的树结构.分为左，右子树.
* 对于二叉树的遍历方式一般分为三种先序、中序、后序三种方式
* 1.先序(根左右）
* 若二叉树为空，则不进行任何操作：否则
1、访问根结点。
2、先序方式遍历左子树。
3、先序遍历右子树。
2.中序(左根右)
若二叉树为空，则不进行任何操作：否则
1、中序遍历左子树。
2、访问根结点。
3、中序遍历右子树。
3.后序(左右根)
若二叉树为空，则不进行任何操作：否则
1、后序遍历左子树。
2、后序遍历右子树。
3、放问根结点。
* */
/**
* 二叉树类型
* */
public class BinaryTree<T>{
/**
*节点也应该是个类型,而且节点类型应该是包含在二叉树类型中
* */
class Node{
//左节点
private Node leftNode;
//右节点
private Node rigthNode;
//节点的值
private T value;
/*
* 提供一个空的构造方法
* */
public Node(){
super();
}
/*
* 构造一个节点的值为value.
* */
public Node(T value){
this.value = value;
leftNode = null;
rigthNode = null;
}
/*
* 根据值，左右节点构造一个节点.
* */
public Node(T value,Node leftNode,Node rithtNode){
this.value = value;
this.leftNode = leftNode;
this.rigthNode = rithtNode;
}
public Node getLeftNode() {
return leftNode;
}
public Node getRigthNode() {
return rigthNode;
}
public T getValue() {
return value;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
public void setRigthNode(Node rigthNode) {
this.rigthNode = rigthNode;
}
public void setValue(T value) {
this.value = value;
}
}
/*
* 测试
* */
public static void main(String[] args) {
BinaryTree<String> tree = new BinaryTree<String>();
tree.infoTree(tree);
// tree.CenterIteration(tree.root);
tree.beforeIteration(tree.root);
// tree.afterIteration(tree.root);
}
private Node root;
public BinaryTree(){
root =null;
}
/*
*后序
* */
public void afterIteration(Node targetNode){
//如果target为null,则结束方法
if(targetNode == null){
return;
}
Node leftNode = targetNode.getLeftNode();
Node rightNode = targetNode.getRigthNode();
if( leftNode != null){
this.beforeIteration(leftNode);
}
if(rightNode != null){
this.beforeIteration(rightNode);
}
this.getNodeValue(targetNode);
}
/*
* 前遍历
* */
public void beforeIteration(Node targetNode){
//如果target为null,则结束方法
if(targetNode == null){
return;
}
//打印根节点和获取当前节点的左右子树的根节点
this.getNodeValue(targetNode);
Node leftNode = targetNode.getLeftNode();
Node rightNode = targetNode.getRigthNode();
if( leftNode != null){
this.beforeIteration(leftNode);
}
if(rightNode != null){
this.beforeIteration(rightNode);
}
}
/*
* 中序
* */
public void CenterIteration(Node targetNode){
//如果target为null,则结束方法
if(targetNode == null){
return;
}
Node leftNode = targetNode.getLeftNode();
Node rightNode = targetNode.getRigthNode();
if( leftNode != null){
this.beforeIteration(leftNode);
}
this.getNodeValue(targetNode);
if(rightNode != null){
this.beforeIteration(rightNode);
}
}
/*
* 输出当前节点值
* */
public void getNodeValue(Node node){
if(node == null){
return;
}
System.out.println(node.getValue());
}
public Node getRoot() {
return root;
}
/*
* 构造一个BinaryTree,返回根节点
* */
public Node infoTree(BinaryTree<String> tree){
BinaryTree<String>.Node G = tree.new Node("G", null, null);
BinaryTree<String>.Node F = tree.new Node("F", null, null);
BinaryTree<String>.Node E = tree.new Node("E", null, G);
BinaryTree<String>.Node D = tree.new Node("D", E, F);
BinaryTree<String>.Node C = tree.new Node("C", null, null);
BinaryTree<String>.Node B = tree.new Node("B", C, D);
tree.root = tree.new Node("root", B, null);
return root;
}
public void setRoot(Node root) {
this.root = root;
}
}

复制代码

王震阳老师 · 王震阳老师

晏敏发表于 2014-8-2 21:25
答案如下

挺好：

package com.ymocean;
import java.util.Comparator;
public class BinaryTree<T> {
private BinaryNode<T> root;
// 二叉树节点
private class BinaryNode<T> {
private T element;
private BinaryNode<T> left;
private BinaryNode<T> right;
public BinaryNode(T theElement) {
element = theElement;
left = null;
right = null;
}
public BinaryNode(T theElement, BinaryNode<T> lt, BinaryNode<T> rt) {
element = theElement;
left = lt;
right = rt;
}
}
private Comparator<? super T> cmp;
public BinaryTree() {
this(null);
}
public BinaryTree(Comparator<? super T> c) {
root = null;
cmp = c;
}
// 比较
private int myCompare(T left, T right) {
if (cmp != null) {
return cmp.compare(left, right);
} else {
return ((Comparable) left).compareTo(right);
}
}
// 创建二叉树
public void buildTree(T x, BinaryNode<T> t) {
if (root == null) {
root = new BinaryNode(x);
} else {
if (myCompare(x, t.element) < 0) {
if (t.left == null) {
t.left = new BinaryNode(x);
} else {
buildTree(x, t.left);
}
} else {
if (t.right == null) {
t.right = new BinaryNode(x);
} else {
buildTree(x, t.right);
}
}
}
}
// 前序遍历
public void preOrder(BinaryNode<T> t) {
if (t != null) {
System.out.print(t.element + " ");
preOrder(t.left);
preOrder(t.right);
}
}
// 中序遍历
public void inOrder(BinaryNode<T> t) {
if (t != null) {
inOrder(t.left);
System.out.print(t.element + " ");
inOrder(t.right);
}
}
// 后序遍历
public void postOrder(BinaryNode<T> t) {
if (t != null) {
postOrder(t.left);
postOrder(t.right);
System.out.print(t.element + " ");
}
}
public static void main(String[] args) {
int[] a = { 1, 14, 77, 23, 58, 102, 86, 4 };
BinaryTree bTree = new BinaryTree();
for (int i = 0; i < a.length; i++) {
bTree.buildTree(a[i], bTree.root);
}
System.out.println("前序遍历:");
bTree.preOrder(bTree.root);
System.out.println("\n");
System.out.println("中序遍历:");
bTree.inOrder(bTree.root);
System.out.println("\n");
System.out.println("后序遍历:");
bTree.postOrder(bTree.root);
}
}

复制代码

王震阳老师 · 王震阳老师

沟门大杏发表于 2014-8-2 21:57
忘了设管理员权限。再提交一次

挺好：

package asd;
public class Test {
public static void main(String[] args) {
}
}
class Node {
private int value;
private Node left;
private Node right;
// 存储节点
public void store(int value) {
if (this.value > value) {
if (left == null) {
left = new Node();
left.value = value;
} else {
left.store(value);
}
} else {
if (right == null) {
right = new Node();
right.value = value;
} else {
/*right.value = value;*/
right.store(value);
}
}
}
// 查找节点
public boolean find(int value) {
if (this.value == value) {
return true;
} else if (this.value > value) {
if (right == null)
return false;
return right.find(value);
} else {
if (left == null)
return false;
return left.find(value);
}
}
// 前序遍历
public void preList() {
System.out.print(this.value + ">>");
if (left != null)
left.preList();
if (right != null)
right.preList();
}
// 中序遍历
public void middleList() {
if (left != null)
left.middleList();
System.out.print(this.value + ">>");
if (right != null)
right.middleList();
}
// 后序遍历
public void afterList() {
if (left != null)
left.afterList();
if (right != null)
right.afterList();
System.out.print(this.value + ">>");
}
/**
* @return the value
*/
public int getValue() {
return value;
}
/**
* @param value the value to set
*/
public void setValue(int value) {
this.value = value;
}
}

复制代码

王震阳老师 · 王震阳老师

ddewym123 发表于 2014-8-1 19:50
请查收！

挺好：

import java.util.LinkedList;
/*
* ①用Java代码模拟实现一个二叉树结构
* ②创建该二叉树
* ③遍历该二叉树。
*/
public class TreeTest {
public static void main(String[] args)throws Exception {
int[] arr={4,8,6,9,5,2,7,1,3};
//使用数组构建二叉树
BinaryTree tree=new BinaryTree(arr);
//遍历二叉树
//tree.preOrderTraverse();//先序遍历
//tree.inOrderTraverse();//中序遍历
//tree.postOrderTraverse();//后序遍历
tree.levelTraverse();//按层次遍历
}
}
//自定义二叉树类
class BinaryTree{
//根节点成员变量
private Node root;
//无参构造方法
public BinaryTree(){
root=null;
}
//使用一个数组来构造二叉树
public BinaryTree(int[] arr){
for (int i:arr) {
root=insertNode(root,i);
}
}
/*插入节点，并且根据节点的值来判断插入方向。
当值小于或等于当前节点的值，则插入当前节点的左侧；
否则，插入当前节点的右侧。
每次从根节点开始递归比较。*/
private Node insertNode(Node node,int value){
if(node==null)
node=new Node(value);
else{
if(value <= node.getValue())
node.setLeft(insertNode(node.getLeft(),value));
else
node.setRight(insertNode(node.getRight(),value));
}
return node;
}
//遍历二叉树
//先序遍历
public void preOrderTraverse(){
preOrderTraverse1(root);
}
//中序遍历
public void inOrderTraverse(){
inOrderTraverse1(root);
}
//后序遍历
public void postOrderTraverse(){
postOrderTraverse1(root);
}
//按层次遍历
public void levelTraverse(){
levelTraverse1(root);
}
//先序遍历的具体实现
private void preOrderTraverse1(Node node){
if(node!=null){
System.out.println(node.getValue());
preOrderTraverse1(node.getLeft());
preOrderTraverse1(node.getRight());
}
}
//中序遍历的具体实现
private void inOrderTraverse1(Node node){
if(node!=null){
inOrderTraverse1(node.getLeft());
System.out.println(node.getValue());
inOrderTraverse1(node.getRight());
}
}
//后序遍历的具体实现
private void postOrderTraverse1(Node node){
if(node!=null){
postOrderTraverse1(node.getLeft());
postOrderTraverse1(node.getRight());
System.out.println(node.getValue());
}
}
//按层次遍历的具体实现
private void levelTraverse1(Node node){
LinkedList<Node> queue=new LinkedList<Node>();
queue.offerLast(node);
while(!queue.isEmpty()){
Node temp=queue.pollFirst();
if(temp!=null){
System.out.println(temp.getValue());
queue.offerLast(temp.getLeft());
queue.offerLast(temp.getRight());
}
}
}
}
//节点类
class Node{
//每个节点有三个属性：节点值、左子节点、右子节点
private Node left;
private Node right;
private int value;
//无参构造方法
public Node(){}
//通过构造方法初始化节点值
public Node(int value){
this(null,null,value);
}
//通过构造方法初始化节点值、左子节点、右子节点
public Node(Node left,Node right,int value){
this.left=left;
this.right=right;
this.value=value;
}
//获取、设置左子节点
public Node getLeft(){
return left;
}
public void setLeft(Node left){
this.left=left;
}
//获取、设置右子节点
public Node getRight(){
return right;
}
public void setRight(Node right){
this.right=right;
}
//获取、设置节点值
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}

复制代码

王震阳老师 · 王震阳老师

止询初衷发表于 2014-8-2 00:17
不好意思，理解错了。。

挺好：

package a.TreeSetD;
import java.util.Stack;
public class BinaryTree {
private TreeNode root=null;
public BinaryTree(){
root=new TreeNode(1,"rootNode(A)");
}
/**
* 创建一棵二叉树
* <pre>
* A
* B C
* D E F
* </pre>
* @param root
* @author WWX
*/
public void createBinTree(TreeNode root){
TreeNode newNodeB = new TreeNode(2,"B");
TreeNode newNodeC = new TreeNode(3,"C");
TreeNode newNodeD = new TreeNode(4,"D");
TreeNode newNodeE = new TreeNode(5,"E");
TreeNode newNodeF = new TreeNode(6,"F");
root.leftChild=newNodeB;
root.rightChild=newNodeC;
root.leftChild.leftChild=newNodeD;
root.leftChild.rightChild=newNodeE;
root.rightChild.rightChild=newNodeF;
}
public boolean isEmpty(){
return root==null;
}
//树的高度
public int height(){
return height(root);
}
//节点个数
public int size(){
return size(root);
}
private int height(TreeNode subTree){
if(subTree==null)
return 0;//递归结束：空树高度为0
else{
int i=height(subTree.leftChild);
int j=height(subTree.rightChild);
return (i<j)?(j+1):(i+1);
}
}
private int size(TreeNode subTree){
if(subTree==null){
return 0;
}else{
return 1+size(subTree.leftChild)
+size(subTree.rightChild);
}
}
//返回双亲结点
public TreeNode parent(TreeNode element){
return (root==null|| root==element)?null:parent(root, element);
}
public TreeNode parent(TreeNode subTree,TreeNode element){
if(subTree==null)
return null;
if(subTree.leftChild==element||subTree.rightChild==element)
//返回父结点地址
return subTree;
TreeNode p;
//现在左子树中找，如果左子树中没有找到，才到右子树去找
if((p=parent(subTree.leftChild, element))!=null)
//递归在左子树中搜索
return p;
else
//递归在右子树中搜索
return parent(subTree.rightChild, element);
}
public TreeNode getLeftChildNode(TreeNode element){
return (element!=null)?element.leftChild:null;
}
public TreeNode getRightChildNode(TreeNode element){
return (element!=null)?element.rightChild:null;
}
public TreeNode getRoot(){
return root;
}
//在释放某个结点时，该结点的左右子树都已经释放，
//所以应该采用后续遍历，当访问某个结点时将该结点的存储空间释放
public void destroy(TreeNode subTree){
//删除根为subTree的子树
if(subTree!=null){
//删除左子树
destroy(subTree.leftChild);
//删除右子树
destroy(subTree.rightChild);
//删除根结点
subTree=null;
}
}
public void traverse(TreeNode subTree){
System.out.println("key:"+subTree.key+"--name:"+subTree.data);;
traverse(subTree.leftChild);
traverse(subTree.rightChild);
}
//前序遍历
public void preOrder(TreeNode subTree){
if(subTree!=null){
visted(subTree);
preOrder(subTree.leftChild);
preOrder(subTree.rightChild);
}
}
//中序遍历
public void inOrder(TreeNode subTree){
if(subTree!=null){
inOrder(subTree.leftChild);
visted(subTree);
inOrder(subTree.rightChild);
}
}
//后续遍历
public void postOrder(TreeNode subTree) {
if (subTree != null) {
postOrder(subTree.leftChild);
postOrder(subTree.rightChild);
visted(subTree);
}
}
//前序遍历的非递归实现
public void nonRecPreOrder(TreeNode p){
Stack<TreeNode> stack=new Stack<TreeNode>();
TreeNode node=p;
while(node!=null||stack.size()>0){
while(node!=null){
visted(node);
stack.push(node);
node=node.leftChild;
}
while(stack.size()>0){
node=stack.pop();
node=node.rightChild;
}
}
}
//中序遍历的非递归实现
public void nonRecInOrder(TreeNode p){
Stack<TreeNode> stack =new Stack<BinaryTree.TreeNode>();
TreeNode node =p;
while(node!=null||stack.size()>0){
//存在左子树
while(node!=null){
stack.push(node);
node=node.leftChild;
}
//栈非空
if(stack.size()>0){
node=stack.pop();
visted(node);
node=node.rightChild;
}
}
}
//后序遍历的非递归实现
public void noRecPostOrder(TreeNode p){
Stack<TreeNode> stack=new Stack<BinaryTree.TreeNode>();
TreeNode node =p;
while(p!=null){
//左子树入栈
for(;p.leftChild!=null;p=p.leftChild){
stack.push(p);
}
//当前结点无右子树或右子树已经输出
while(p!=null&&(p.rightChild==null||p.rightChild==node)){
visted(p);
//纪录上一个已输出结点
node =p;
if(stack.empty())
return;
p=stack.pop();
}
//处理右子树
stack.push(p);
p=p.rightChild;
}
}
public void visted(TreeNode subTree){
subTree.isVisted=true;
System.out.println("key:"+subTree.key+"--name:"+subTree.data);;
}
/**
* 二叉树的节点数据结构
* @author WWX
*/
private class TreeNode{
private int key=0;
private String data=null;
private boolean isVisted=false;
private TreeNode leftChild=null;
private TreeNode rightChild=null;
public TreeNode(){}
/**
* @param key 层序编码
* @param data 数据域
*/
public TreeNode(int key,String data){
this.key=key;
this.data=data;
this.leftChild=null;
this.rightChild=null;
}
}
//测试
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
bt.createBinTree(bt.root);
System.out.println("the size of the tree is " + bt.size());
System.out.println("the height of the tree is " + bt.height());
System.out.println("*******(前序遍历)[ABDECF]遍历*****************");
bt.preOrder(bt.root);
System.out.println("*******(中序遍历)[DBEACF]遍历*****************");
bt.inOrder(bt.root);
System.out.println("*******(后序遍历)[DEBFCA]遍历*****************");
bt.postOrder(bt.root);
System.out.println("***非递归实现****(前序遍历)[ABDECF]遍历*****************");
bt.nonRecPreOrder(bt.root);
System.out.println("***非递归实现****(中序遍历)[DBEACF]遍历*****************");
bt.nonRecInOrder(bt.root);
System.out.println("***非递归实现****(后序遍历)[DEBFCA]遍历*****************");
bt.noRecPostOrder(bt.root);
}
}

复制代码

刘小印 · 刘小印

刘小印发表于 2014-8-1 21:27
注意查收哈阳哥

哦哦。采学习完集合，想的有点简单，我会继续努力的

王震阳老师 · 王震阳老师

.Mч┞尛__洋发表于 2014-8-2 10:52
阳哥抱拳了！！！！！

挺好：

public class CreatBiTree {
/*
* 题目：①用Java代码模拟实现一个二叉树结构②创建该二叉树③遍历该二叉树。
*
* 思路：二叉树：一种树状结构，一棵二叉树的“结点”（Node）最多只能拥有2个子结点，也就是度小于或等于2。
* 1）二叉树的结点个数是有限，而且可以没有结点。
* 2）一棵二叉树的树根下可以分为两个子树称为“左子树”(Left Subtree)和“右子树”(Right Subtree)
* 3）前、中、后序遍历。
*/
private Node root;
/*
* 创建二叉树节点，利用内部类方式。
* @author lhy
*/
private class Node{
private Node left;//定义左节点
private Node right;//定义右节点
private int value;//节点值。
public Node(int value){
this.left = null;
this.right = null;
this.value = value;
}
}
public CreatBiTree(){
root = null;
}
/*
* 递归创建二叉树，不过多解释了，直接上代码。
*/
public void buildTree(Node node,int value){
if(root == null){
root = new Node(value);
}else{
if(value < node.value){
if(node.left == null){
node.left = new Node(value);
}else{
buildTree(node.left,value);
}
}else{
if(node.right == null){
node.right = new Node(value);
}else{
buildTree(node.right,value);
}
}
}
}
/*
* 前序遍历也称先序遍历。
*/
public void preOrder(Node node){
if(node != null){
System.out.print(node.value+" ");
preOrder(node.left);
preOrder(node.right);
}
}
/*
* 中序遍历
*/
public void inOrder(Node node){
if(node != null){
inOrder(node.left);
System.out.print(node.value+" ");
inOrder(node.right);
}
}
/*
* 后序遍历
*/
public void postOrder(Node node){
if(node != null){
postOrder(node.left);
postOrder(node.right);
System.out.print(node.value+" ");
}
}
public static void main(String[] args) {
int[] a = {1,2,3,4,5,6,7,8,9,10,11,12,13,14};
CreatBiTree bTree = new CreatBiTree();
for (int i = 0; i < a.length; i++) {
bTree.buildTree(bTree.root, a[i]);
}
System.out.println("先序遍历的结果是：");
bTree.preOrder(bTree.root);
System.out.println("\n中序遍历的结果是：");
bTree.inOrder(bTree.root);
System.out.println("\n后序遍历的结果是：");
bTree.postOrder(bTree.root);
}
}

复制代码

执笔梦 · 执笔梦

就业指导－王震阳老师发表于 2014-8-4 22:08
答案很给力，请大家参考：
自定义二叉树类：

学习了，想到添加的数据要实现Comparable,也想到根据节点值大小添加到左右子树，不过最后还是败给泛型了，就没有实现出来，

Без_тебя · Без_тебя

来试试看看

阿温 · 阿温

没想到没有上榜...伤心了

阿温 · 阿温

阳哥要求实现添加和遍历你们都干了什么!!!!呜呜呜~~~太不公平了

郭可 · 郭可

额黑马不能上网来次论坛不容易啊

狂飙的yellow.co · 狂飙的yellow.co

呵呵！！貌似都挺牛掰的样子

yqj · yqj

虽然答案都有了，我也发一个我写的

—Jimmy— · —Jimmy—

领取题目!!!

十指紧扣 · 十指紧扣

又来看一遍！

十指紧扣 · 十指紧扣

管理滔哥给我说我连续刷帖，减了50黑马币，可是我没有，好伤心！！！！

会飞De石头 · 会飞De石头

来看看什么类型的

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

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

评分

黑马骑士勋章

黑马土豪金