...试设计一个计算二叉树叶子结点树的递归算 法 要求用递归算法啊...
发布网友
发布时间：2024-09-27 00:50
共3个回答
热心网友
时间：4分钟前
1、首先要定义两个类：结点类和二叉树类。
2、二叉树类的组成：建立树的函数、遍历函数、删除函数。求结点数函数。
3、采用递归的思想，遇到标识符表示该结点为空，否则开辟空间创建新结点，同时调用递归开辟左结点和右结点。
4、前序遍历函数。
5、删除函数的思路：如果当前结点不为空，采用递归访问左结点和右结点、回收当前结点的空间。
6、求结点数函数的思路：如果当前结点为空，返回0、如果当前结点的左右孩子都为空，放回1。
7、求树高函数的思路：如果当前结点为空，返回0、递归访问左孩子和右孩子、比较左右孩子的高度，返回 较大值+1。
热心网友
时间：8分钟前
叶子节点：没有孩子节点的节点
下面我给出两种求解思路，其中就包括你要的递归求解。Java版的示例代码如下：
import org.junit.Test;
import cn.zifangsky.queue.LinkQueue;
import cn.zifangsky.tree.binarytree.BinaryTreeNode;
/**
* 求二叉树中叶子节点的个数
* @author zifangsky
*
*/
public class Question2 {
/**
* 通过递归遍历获取叶子节点个数
*
* @时间复杂度 O(n)
* @param root
* @return
*/
public int getNumberOfLeavesByPreOrder(BinaryTreeNode<Integer> 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<Integer> root){
int count = 0; //叶子节点总数
LinkQueue<BinaryTreeNode<Integer>> queue = new LinkQueue<>();
if(root != null){
queue.enQueue(root);
}
while (!queue.isEmpty()) {
BinaryTreeNode<Integer> temp = 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;
}
/**
* 测试用例
*/
@Test
public void testMethods(){
/**
* 使用队列构造一个供测试使用的二叉树
* 1
* 2 3
* 4 5 6 7
* 8 9
*/
LinkQueue<BinaryTreeNode<Integer>> queue = new LinkQueue<BinaryTreeNode<Integer>>();
BinaryTreeNode<Integer> root = new BinaryTreeNode<>(1); //根节点
queue.enQueue(root);
BinaryTreeNode<Integer> temp = null;
for(int i=2;i<10;i=i+2){
BinaryTreeNode<Integer> tmpNode1 = new BinaryTreeNode<>(i);
BinaryTreeNode<Integer> tmpNode2 = new BinaryTreeNode<>(i+1);
temp = queue.deQueue();
temp.setLeft(tmpNode1);
temp.setRight(tmpNode2);
if(i != 4)
queue.enQueue(tmpNode1);
queue.enQueue(tmpNode2);
}
System.out.println("叶子节点个数是：" + getNumberOfLeavesByPreOrder(root));
System.out.println("叶子节点个数是：" + getNumberOfLeavesByQueue(root));
}
}
输出如下：
叶子节点个数是：5
附：上面代码中用到的两个类的定义：
i）BinaryTreeNode.java：
package cn.zifangsky.tree.binarytree;/**
* 二叉树的单个节点定义
* @author zifangsky
*
* @param <K>
*/
public class BinaryTreeNode<K extends Object> {
private K data; // 数据
private BinaryTreeNode<K> left; //左孩子节点
private BinaryTreeNode<K> right; //右孩子节点
public BinaryTreeNode(K data) {
this.data = data;
}
public BinaryTreeNode(K data, BinaryTreeNode<K> left, BinaryTreeNode<K> right) {
this.data = data;
this.left = left;
this.right = right;
}
public K getData() {
return data;
}
public void setData(K data) {
this.data = data;
}
public BinaryTreeNode<K> getLeft() {
return left;
}
public void setLeft(BinaryTreeNode<K> left) {
this.left = left;
}
public BinaryTreeNode<K> getRight() {
return right;
}
public void setRight(BinaryTreeNode<K> right) {
this.right = right;
}
}
ii）LinkQueue.java：
package cn.zifangsky.queue;import cn.zifangsky.linkedlist.SinglyNode;
/**
* 基于单链表实现的队列
* @author zifangsky
* @param <K>
*/
public class LinkQueue<K extends Object> implements Queue<K>{
private SinglyNode<K> frontNode; //队首节点
private SinglyNode<K> rearNode; //队尾节点
public LinkQueue() {
frontNode = null;
rearNode = null;
}
/**
* 返回队列是否为空
* @时间复杂度 O(1)
* @return
*/
@Override
public boolean isEmpty(){
return (frontNode == null);
}
/**
* 返回存储在队列的元素个数
* @时间复杂度 O(n)
* @return
*/
@Override
public int size(){
int length = 0;
SinglyNode<K> currentNode = frontNode;
while (currentNode != null) {
length++;
currentNode = currentNode.getNext();
}
return length;
}
/**
* 入队：在链表表尾插入数据
* @时间复杂度 O(1)
* @param data
*/
@Override
public void enQueue(K data){
SinglyNode<K> newNode = new SinglyNode<K>(data);
if(rearNode != null){
rearNode.setNext(newNode);
}
rearNode = newNode;
if(frontNode == null){
frontNode = rearNode;
}
}
/**
* 出队：删除表头节点
* @时间复杂度 O(1)
* @return
*/
@Override
public K deQueue(){
if(isEmpty()){
throw new RuntimeException("Queue Empty!");
}else{
K result = frontNode.getData();
if(frontNode == rearNode){
frontNode = null;
rearNode = null;
}else{
frontNode = frontNode.getNext();
}
return result;
}
}
/**
* 返回队首的元素，但不删除
* @时间复杂度 O(1)
*/
@Override
public K front() {
if(isEmpty()){
throw new RuntimeException("Queue Empty!");
}else{
return frontNode.getData();
}
}
/**
* 遍历队列
* @时间复杂度 O(n)
* @return
*/
@Override
public void print() {
SinglyNode<K> tmpNode = frontNode;
while (tmpNode != null) {
System.out.print(tmpNode.getData() + " ");
tmpNode = tmpNode.getNext();
}
}
/**
* 删除整个队列
* @时间复杂度 O(1)
* @return
*/
@Override
public void deleteQueue() {
frontNode = null;
rearNode = null;
}
}
iii）SinglyNode.java：
package cn.zifangsky.linkedlist;/**
* 单链表的定义
*
* @author zifangsky
* @param <K>
*/
public class SinglyNode<K extends Object> {
private K data; // 数据
private SinglyNode<K> next; // 该节点的下个节点
public SinglyNode(K data) {
this.data = data;
}
public SinglyNode(K data, SinglyNode<K> next) {
this.data = data;
this.next = next;
}
public K getData() {
return data;
}
public void setData(K data) {
this.data = data;
}
public SinglyNode<K> getNext() {
return next;
}
public void setNext(SinglyNode<K> next) {
this.next = next;
}
@Override
public String toString() {
return "SinglyNode [data=" + data + "]";
}
}
热心网友
时间：4分钟前
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild ; //左孩子指针
struct BiTNode *rchild; // 右孩子指针
} BiTNode, *BiTree;
void CountLeaf (BiTree T, int& count){
if ( T ) {
if ((!T->lchild)&& (!T->rchild))
count++; // 对叶子结点计数
CountLeaf( T->lchild, count);
CountLeaf( T->rchild, count);
}
else return;
} // CountLeaf
