本文目录
- 写一个java层次遍历二叉树,简单点就可以,我要的是代码,不是纯文字说明
- java二叉树中序遍历 的递归算法没有看懂search(data.getLeft());之后不就回到最左边的一个
- java二叉树前序方法增加一个新的节点，然后把另一个节点的数据插入到这个新节点
- java中的遍历是什么意思
- java如何将二叉树中序遍历的结果存入一个数组
- java实现二叉树的问题
写一个java层次遍历二叉树,简单点就可以,我要的是代码,不是纯文字说明
public class BinaryNode { Object element; BinaryNode left; BinaryNode right;}import java.util.*;public class Queue { protected LinkedList list; // Postcondition: this Queue object has been initialized. public Queue() { list = new LinkedList(); } // default constructor // Postcondition: the number of elements in this Queue object has been // returned. public int size() { return list.size(); } // method size // Postcondition: true has been returned if this Queue object has no // elements. Otherwise, false has been returned. public boolean isEmpty() { return list.isEmpty(); } // method isEmpty // Postconditon: A copy of element has been inserted at the back of this // Queue object. The averageTime (n) is constant and // worstTime (n) is O (n). public void enqueue(Object element) { list.addLast(element); } // method enqueue // Precondition: this Queue object is not empty. Otherwise, // NoSuchElementException will be thrown. // Postcondition: The element that was at the front of this Queue object - // just before this method was called -- has been removed // from this Queue object and returned. public Object dequeue() { return list.removeFirst(); } // method dequeue // Precondition: this Queue object is not empty. Otherwise, // NoSuchElementException will be thrown. // Postcondition: the element at index 0 in this Queue object has been // returned. public Object front() { return list.getFirst(); } // method front} // Queue classimport java.io.IOException;public class BinaryTree { BinaryNode root;public BinaryTree() { super(); // TODO 自动生成构造函数存根 root=this.createPre(); } public BinaryNode createPre() //按照先序遍历的输入方法，建立二叉树 { BinaryNode t=null; char ch; try { ch = (char)System.in.read(); if(ch==’ ’) t=null; else { t=new BinaryNode(); t.element=(Object)ch; t.left=createPre(); t.right=createPre(); } } catch (IOException e) { // TODO 自动生成 catch 块 e.printStackTrace(); } return t; } public void inOrder() { this.inOrder(root); } public void inOrder(BinaryNode t) //中序遍历二叉树 { if(t!=null) { inOrder(t.left); System.out.print(t.element); inOrder(t.right); } } public void postOrder() { this.postOrder(root); } public void postOrder(BinaryNode t) //后序遍历二叉树 { if(t!=null) { postOrder(t.left); System.out.print(t.element); postOrder(t.right); } } public void preOrder() { this.preOrder(root); } public void preOrder(BinaryNode t) //前序遍历二叉树 { if(t!=null) { System.out.print(t.element); preOrder(t.left); preOrder(t.right); } } public void breadthFirst() { Queue treeQueue=new Queue(); BinaryNode p; if(root!=null) treeQueue.enqueue(root); while(!treeQueue.isEmpty()) { System.out.print(((BinaryNode)(treeQueue.front())).element); p=(BinaryNode)treeQueue.dequeue(); if(p.left!=null) treeQueue.enqueue(p.left); if(p.right!=null) treeQueue.enqueue(p.right); } }}public class BinaryTreeTest { /** * @param args */ public static void main(String args) { // TODO 自动生成方法存根 BinaryTree tree = new BinaryTree(); System.out.println("先序遍历："); tree.preOrder(); System.out.println(); System.out.println("中序遍历："); tree.inOrder(); System.out.println(); System.out.println("后序遍历："); tree.postOrder(); System.out.println(); System.out.println("层次遍历："); tree.breadthFirst(); System.out.println(); }}
java二叉树中序遍历 的递归算法没有看懂search(data.getLeft());之后不就回到最左边的一个
最左边的节点是没有左子树和右子树的。if(data.getLeft()!=null){ // 这里getLetf()为nullsearch(data.getLeft());}System.out.print(data.getObj()+","); //只有这句是执行的！if(data.getRight()!=null){ // 这里getRight()为nullsearch(data.getRight());}然后就会退到上一个节点的遍历函数了。
java二叉树前序方法增加一个新的节点，然后把另一个节点的数据插入到这个新节点
叶子节点：没有孩子节点的节点也就是说，当我们明白了叶子节点的定义后，只需要遍历一遍二叉树，把符合这种条件（左孩子节点和右孩子节点都为NULL的节点）的节点统计出来就可以了。于是，实际上这个问题也就转化成了如何遍历二叉树？很显然，遍历二叉树是可以有多种方式的，如：前序遍历（递归/非递归）、中序遍历（递归/非递归）、后序遍历（递归/非递归）、层次遍历等等。下面我将给出使用递归前序遍历以及层次遍历两种思路实现的求解叶子节点的示例代码吧，仅供参考。其他几种实现方式思路类似，可自行尝试。示例代码如下：package cn.zifangsky.tree.questions;import org.junit.Test;import cn.zifangsky.queue.LinkQueue;import cn.zifangsky.tree.BinaryTreeNode;/** * 求二叉树中叶子节点的个数 * @author Administrator * */public class Question2 {/** * 通过递归前序遍历获取叶子节点个数 * @param root * @return */public int getNumberOfLeavesByPreOrder(BinaryTreeNode root){if(root == null){return 0;}else{if(root.getLeft() == null && root.getRight() == null){ //叶子节点return 1;}else{return getNumberOfLeavesByPreOrder(root.getLeft()) + getNumberOfLeavesByPreOrder(root.getRight());}}}/** * 使用层次遍历获取二叉树叶子节点个数 * * @时间复杂度 O(n) * @param root */public int getNumberOfLeavesByQueue(BinaryTreeNode root){int count = 0; //叶子节点总数LinkQueue queue = new LinkQueue();if(root != null){queue.enQueue(root);}while (!queue.isEmpty()) {BinaryTreeNode temp = (BinaryTreeNode) queue.deQueue();//叶子节点：左孩子节点和右孩子节点都为NULL的节点if(temp.getLeft() == null && temp.getRight() == null){count++;}else{if(temp.getLeft() != null){queue.enQueue(temp.getLeft());}if(temp.getRight() != null){queue.enQueue(temp.getRight());}}}return count;}/** * 测试用例 */@Testpublic void testMethods(){/** * 使用队列构造一个供测试使用的二叉树 * 1 * 2 3 * 4 5 6 7 * 8 9 */LinkQueue queue = new LinkQueue();BinaryTreeNode root = new BinaryTreeNode(1); //根节点queue.enQueue(root);BinaryTreeNode temp = null;for(int i=2;i */public class LinkQueue{private SinglyNode frontNode; //队首节点private SinglyNode rearNode; //队尾节点public LinkQueue() {frontNode = null;rearNode = null;}/** * 返回队列是否为空 * @时间复杂度 O(1) * @return */public boolean isEmpty(){return (frontNode == null);}/** * 返回存储在队列的元素个数 * @时间复杂度 O(n) * @return */public int size(){int length = 0;SinglyNode currentNode = frontNode;while (currentNode != null) {length++;currentNode = currentNode.getNext();}return length;}/** * 入队：在链表表尾插入数据 * @时间复杂度 O(1) * @param data */public void enQueue(K data){SinglyNode newNode = new SinglyNode(data);if(rearNode != null){rearNode.setNext(newNode);}rearNode = newNode;if(frontNode == null){frontNode = rearNode;}}/** * 出队：删除表头节点 * @时间复杂度 O(1) * @return */public Object deQueue(){if(isEmpty()){throw new RuntimeException("Queue Empty!");}else{Object result = frontNode.getData();if(frontNode == rearNode){frontNode = null;rearNode = null;}else{frontNode = frontNode.getNext();}return result;}}}单链表节点SinglyNode的定义：package cn.zifangsky.linkedlist;/** * 单链表的定义 * @author zifangsky * @param */public class SinglyNode {private K data; // 数据private SinglyNode next; // 该节点的下个节点public SinglyNode(K data) {this.data = data;}public SinglyNode(K data, SinglyNode next) {this.data = data;this.next = next;}public K getData() {return data;}public void setData(K data) {this.data = data;}public SinglyNode getNext() {return next;}public void setNext(SinglyNode next) {this.next = next;}@Overridepublic String toString() {return "SinglyNode ";}}
java中的遍历是什么意思
遍历就是把每个元素都访问一次.比如一个二叉树,遍历二叉树意思就是把二叉树中的每个元素都访问一次
java如何将二叉树中序遍历的结果存入一个数组
Set set=new TreeSet();String;Iterator it=set.iterator();for(int j=0;it.hasNext();j++){other=(String)it.next();}
java实现二叉树的问题
/** * 二叉树测试二叉树顺序存储在treeLine中，递归前序创建二叉树。另外还有能 * 够前序、中序、后序、按层遍历二叉树的方法以及一个返回遍历结果asString的 * 方法。 */ public class BitTree { public static Node2 root; public static String asString; //事先存入的数组,符号#表示二叉树结束。 public static final char treeLine = {’a’,’b’,’c’,’d’,’e’,’f’,’g’,’ ’,’ ’,’j’,’ ’,’ ’,’i’,’#’}; //用于标志二叉树节点在数组中的存储位置，以便在创建二叉树时能够找到节点对应的数据。 static int index; //构造函数 public BitTree() { System.out.print("测试二叉树的顺序表示为："); System.out.println(treeLine); this.index = 0; root = this.setup(root); } //创建二叉树的递归程序 private Node2 setup(Node2 current) { if (index 》= treeLine.length) return current; if (treeLine == ’#’) return current; if (treeLine == ’ ’) return current; current = new Node2(treeLine); index = index * 2 + 1; current.left = setup(current.left); index ++; current.right = setup(current.right); index = index / 2 - 1; return current; } //二叉树是否为空。 public boolean isEmpty() { if (root == null) return true; return false; } //返回遍历二叉树所得到的字符串。 public String toString(int type) { if (type == 0) { asString = "前序遍历：\t"; this.front(root); } if (type == 1) { asString = "中序遍历：\t"; this.middle(root); } if (type == 2) { asString = "后序遍历：\t"; this.rear(root); } if (type == 3) { asString = "按层遍历：\t"; this.level(root); } return asString; } //前序遍历二叉树的循环算法，每到一个结点先输出，再压栈，然后访问它的左子树， //出栈，访问其右子树，然后该次循环结束。 private void front(Node2 current) { StackL stack = new StackL((Object)current); do { if (current == null) { current = (Node2)stack.pop(); current = current.right; } else { asString += current.ch; current = current.left; } if (!(current == null)) stack.push((Object)current); } while (!(stack.isEmpty())); } //中序遍历二叉树 private void middle(Node2 current) { if (current == null) return; middle(current.left); asString += current.ch; middle(current.right); } //后序遍历二叉树的递归算法 private void rear(Node2 current) { if (current == null) return; rear(current.left); rear(current.right); asString += current.ch; }}/** * 二叉树所使用的节点类。包括一个值域两个链域 */ public class Node2 { char ch; Node2 left; Node2 right; //构造函数 public Node2(char c) { this.ch = c; this.left = null; this.right = null; } //设置节点的值 public void setChar(char c) { this.ch = c; } //返回节点的值 public char getChar() { return ch; } //设置节点的左孩子 public void setLeft(Node2 left) { this.left = left; } //设置节点的右孩子 public void setRight (Node2 right) { this.right = right; } //如果是叶节点返回true public boolean isLeaf() { if ((this.left == null) && (this.right == null)) return true; return false; }}一个作业题，里面有你要的东西。主函数自己写吧。当然其它地方也有要改的。
