假设二叉树以二叉链表作为存储结构，试设计一个计算二叉树叶子结点树的递归算 法 要求用递归算法啊
#include
#define ARRAY_MAX 12
int main()
{
int tree[ARRAY_MAX];
for(int i = 0;i < ARRAY_MAX;i++)
tree[i] = i+1;
int flag = 0;//记录当前叶子的遍历位置,0 刚遍历到这个叶子,1 已经遍历完成该叶子的左儿子,2 已经遍历完成该叶子的右儿子
int count = 1;//假设tree不为空
while(!(count == 1&&flag == 2))
{
if(flag == 0)
{
printf("%d ",tree[count-1]);
if(count*2 > ARRAY_MAX)
flag = 1;
else
count = count*2;
}
else if(flag == 1)
{
if(count*2+1 > ARRAY_MAX)
flag = 2;
else
{
count = count*2+1;
flag = 0;
}
}
else if(flag == 2)
{
if(count%2 == 0)
flag = 1;
else
flag = 2;
count = count/2;
}
}
getchar();
return 0;
}
以上代码Microsoft Visual C++ 6.0中编译通过，输出的数列为以下下二叉树的前序遍历
连5分都不给，真小气......
很容易写的，就用一个先序遍历来执行，然后当左右子树都为空的时候i++，然后当遍历结束的时候输出i值，就是叶子结点的个数
只给你提供个思路，具体代码自己实现
1、首先要定义两个类：结点类和二叉树类。
2、二叉树类的组成：建立树的函数、遍历函数、删除函数。求结点数函数。
3、采用递归的思想，遇到标识符表示该结点为空，否则开辟空间创建新结点，同时调用递归开辟左结点和右结点。
4、前序遍历函数。
5、删除函数的思路：如果当前结点不为空，采用递归访问左结点和右结点、回收当前结点的空间。
6、求结点数函数的思路：如果当前结点为空，返回0、如果当前结点的左右孩子都为空，放回1。
7、求树高函数的思路：如果当前结点为空，返回0、递归访问左孩子和右孩子、比较左右孩子的高度，返回 较大值+1。
叶子节点：没有孩子节点的节点
下面我给出两种求解思路，其中就包括你要的递归求解。Java版的示例代码如下：
package cn.zifangsky.tree.binarytree.questions;
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
叶子节点个数是：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 + "]";
}
}
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
设二叉树以二叉链表为存储结构,编写一个后续遍历二叉树的非递归算法
答：include <stdio.h> include <malloc.h> include <stdlib.h> define STACK_INT_SIZE 100 define STACKINCREMENT 10 define OK 1 define ERROR 0 define TRUE 1 define FALSE 0 define OVERFLOW -2 typedef char TElemType;typedef int Status;typedef char SElemType;typedef struct BiTNode { TElemType...
以二叉链表为存储结构,分别写出求二叉树结点总数及叶子总数的算法...
答：【答案】：(1)计算结点总数 int CountNode(BinTree*root){ intnum1,num2;if(root==Null)return(0);else if(root-＞lchild==Null＆＆rooot-＞rchild==Null)return(1);else { num 1=CountNode(root-＞lchild);num 2=CountNode(root-＞rchild);return(num1+num2+!);} } (2)计算叶子总数...
若用二叉链表作为二叉树的存储表示,试编写算法交换二叉树中各结点的...
答：递归:void exchange(BTree *rt){ BTree *temp = NULL;if(rt->lchild == NULL && rt->rchild == NULL)return;else{ temp = rt->lchild;rt->lchild = rt->rchild;rt->rchild = temp;} if(rt->lchild)exchange(rt->lchild);if(rt->rchild)exchange(rt->rchild);} 非递归:Stack是一个...
已知一棵二叉树是以二叉链表的形式存储的求出以T为根的子树的结点个数...
答：已知一棵二叉树是以二叉链表的形式存储的,其结点结构说明如下:structnode{intdata;structnode*left;structnode*right;};要求写出2个具有下面功能的算法:①、求出以T为根的子树的结... 已知一棵二叉树是以二叉链表的形式存储的,其结点结构说明如下:struct node{int data;struct node * left;struct node * right...
若用二叉链表作为二叉树的存储表示,试针对以下问题编写算法:统计二叉...
答：//二叉树结构体 struct BTNode { int data;BTNode *rchild;BTNode *lchild;};//非递归遍堆栈 struct ABTStack { BTNode *ptree;ABTStack *link;};static pCounter = 0; //计数器，记录节点个数 / 前序遍历函数pre_Order_Access()<非递归算法> 参数描述：BTNode *head: 根节点指针 / void ...
以二叉链表作存储结构,试编写求二叉树高度的算法
答：二叉树的遍历算法 二叉树的度 其他类似问题2012-02-04 假设以二叉链表作为二叉树的存储结构,试编写一个求树的高度的算... 10 2009-01-15 以二叉链表为存储结构,写出求二叉树高度和宽度的算法 30 2012-07-16 以二叉树链表作为二叉树的存储结构,编写算法计算返回二叉树的高... 20 2007-12-03 以二叉...
假设以二叉链表存储的二叉数中,每个结点所含数据结构元素均为单字母,试...
答：同理，第四层的打印空间是9个字符宽，第五层是4个字符宽，第六层是1个字符宽。因此，这个程序最多只能显示6层的二叉树。中序访问二叉树（从右子树开始，而不是左子树）的结点，根据结点的深度打印相应的空格，每打印一个字母就换行，当整个二叉树的中序访问结束后就打印出树状二叉树了。
以二叉链表为存储结构,写出求二叉树高度和宽度的算法
答：以二叉链表为存储结构,分别写出求二叉树高度及宽度的算法。所谓宽度是指在二叉树的各层上,具有结点数最多的那一层上的结点总数。标准答案:①求树的高度思想:对非空二叉树,其深度等于左子树的最大深度加1。Int Depth(BinTree *T){int dep1,dep2;if(T==Null) return(0);else{dep1=Depth(T->lchild);...
编写算法:已知二叉排序树按二叉链表形式存储,树中结点各不相同,欲得...
答：二叉排序树（Binary Sort Tree）又称二叉查找树，亦称二叉搜索树。 它或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；...
若用二叉链表作为二叉树的存储表示,试用编写递归算法,统计二叉树中叶子...
答：int count(Node *root) { if (!root) return 0;int ret = count(root->leftChild) + count(root->rightChild);return ret == 0 ? 1 : ret;} 第一行: 空指针返回0 第二行：统计左右子树的叶子节点个数 第三行：如果左右子树的叶子节点个数为0,则本身是一个叶子节点，返回1；否则返回...
