Question

java二叉树前序方法增加一个新的节点，然后把另一个节点的数据插入到这个新节点

用java写的组织树，需求是里面添加一个新的节点，同时用插入的方法将随意的一个节点(包括数据)放到这个节点里面。如何实现这个功能？高手指教！最好前台和后端的代码都有





Answer 1

叶子节点：没有孩子节点的节点也就是说，当我们明白了叶子节点的定义后，只需要遍历一遍二叉树，把符合这种条件（左孩子节点和右孩子节点都为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 [data=" + data + "]";}}

追问

代码看的蒙圈了。。 能私信你嘛？