假设二叉树以二叉链表作为存储结构，试设计一个计算二叉树叶子结点树的递归算 法 要求用递归算法啊

叶子节点：没有孩子节点的节点

下面我给出两种求解思路，其中就包括你要的递归求解。Java版的示例代码如下：

package cnzifangskytreebinarytreequestions;

import orgjunitTest;

import cnzifangskyqueueLinkQueue;

import cnzifangskytreebinarytreeBinaryTreeNode;

/

  求二叉树中叶子节点的个数

  @author zifangsky

 

 /

public class Question2 {

/

  通过递归遍历获取叶子节点个数

  

  @时间复杂度 O(n)

  @param root

  @return

 /

public int getNumberOfLeavesByPreOrder(BinaryTreeNode<Integer> root){

if(root == null){

return 0;

}else{

if(rootgetLeft() == null && rootgetRight() == null){ //叶子节点

return 1;

}else{ //左子树叶子节点总数 + 右子树叶子节点总数

return getNumberOfLeavesByPreOrder(rootgetLeft()) + getNumberOfLeavesByPreOrder(rootgetRight());

}

}

}

/

  使用层次遍历获取二叉树叶子节点个数

  

  @时间复杂度 O(n)

  @param root

 /

public int getNumberOfLeavesByQueue(BinaryTreeNode<Integer> root){

int count = 0; //叶子节点总数

LinkQueue<BinaryTreeNode<Integer>> queue = new LinkQueue<>();

if(root != null){

queueenQueue(root);

}

while (!queueisEmpty()) {

BinaryTreeNode<Integer> temp = queuedeQueue(); //出队

//叶子节点：左孩子节点和右孩子节点都为NULL的节点

if(tempgetLeft() == null && tempgetRight() == null){

count++;

}else{

if(tempgetLeft() != null){

queueenQueue(tempgetLeft());

}

if(tempgetRight() != null){

queueenQueue(tempgetRight());

}

}

}

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); //根节点

queueenQueue(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 = queuedeQueue();

tempsetLeft(tmpNode1);

tempsetRight(tmpNode2);

if(i != 4)

queueenQueue(tmpNode1);

queueenQueue(tmpNode2);

}

Systemoutprintln("叶子节点个数是：" + getNumberOfLeavesByPreOrder(root));

Systemoutprintln("叶子节点个数是：" + getNumberOfLeavesByQueue(root));

}

}

输出如下：

叶子节点个数是：5

叶子节点个数是：5

附：上面代码中用到的两个类的定义：

i）BinaryTreeNodejava：

package cnzifangskytreebinarytree;

/

  二叉树的单个节点定义

  @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) {

thisdata = data;

}

public BinaryTreeNode(K data, BinaryTreeNode<K> left, BinaryTreeNode<K> right) {

thisdata = data;

thisleft = left;

thisright = right;

}

public K getData() {

return data;

}

public void setData(K data) {

thisdata = data;

}

public BinaryTreeNode<K> getLeft() {

return left;

}

public void setLeft(BinaryTreeNode<K> left) {

thisleft = left;

}

public BinaryTreeNode<K> getRight() {

return right;

}

public void setRight(BinaryTreeNode<K> right) {

thisright = right;

}

}

ii）LinkQueuejava：

package cnzifangskyqueue;

import cnzifangskylinkedlistSinglyNode;

/

  基于单链表实现的队列

  @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 = currentNodegetNext();

}

return length;

}

/

  入队：在链表表尾插入数据

  @时间复杂度 O(1)

  @param data

 /

@Override

public void enQueue(K data){

SinglyNode<K> newNode = new SinglyNode<K>(data);

if(rearNode != null){

rearNodesetNext(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 = frontNodegetData();

if(frontNode == rearNode){

frontNode = null;

rearNode = null;

}else{

frontNode = frontNodegetNext();

}

return result;

}

}

/

  返回队首的元素，但不删除

  @时间复杂度 O(1)

 /

@Override

public K front() {

if(isEmpty()){

throw new RuntimeException("Queue Empty!");

}else{

return frontNodegetData();

}

}

/

  遍历队列

  @时间复杂度 O(n)

  @return

 /

@Override

public void print() {

SinglyNode<K> tmpNode = frontNode;

while (tmpNode != null) {

Systemoutprint(tmpNodegetData() + " ");

tmpNode = tmpNodegetNext();

}

}

/

  删除整个队列

  @时间复杂度 O(1)

  @return

 /

@Override

public void deleteQueue() {

frontNode = null;

rearNode = null;

}

}

iii）SinglyNodejava：

package cnzifangskylinkedlist;

/

  单链表的定义

  

  @author zifangsky

  @param <K>

 /

public class SinglyNode<K extends Object> {

private K data; // 数据

private SinglyNode<K> next; // 该节点的下个节点

public SinglyNode(K data) {

thisdata = data;

}

public SinglyNode(K data, SinglyNode<K> next) {

thisdata = data;

thisnext = next;

}

public K getData() {

return data;

}

public void setData(K data) {

thisdata = data;

}

public SinglyNode<K> getNext() {

return next;

}

public void setNext(SinglyNode<K> next) {

thisnext = next;

}

@Override

public String toString() {

return "SinglyNode [data=" + data + "]";

}

}

#include<malloch> // malloc()等

#include<stdioh> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等

#include<stdlibh> // atoi()，exit()

#include<mathh> // 数学函数头文件，包括floor()，ceil()，abs()等

#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的 *** 作一样

typedef struct BiTNode

{

int data; // 结点的值

BiTNode lchild,rchild; // 左右孩子指针

}BiTNode,BiTree;

int Nil=0; // 设整型以0为空

void visit(int e)

{ printf("%d ",e); // 以整型格式输出

}

void InitBiTree(BiTree &T)

{ // *** 作结果：构造空二叉树T

T=NULL;

}

void CreateBiTree(BiTree &T)

{ // 算法64：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，

// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改

int number;

scanf("%d",&number); // 输入结点的值

if(number==Nil) // 结点的值为空

T=NULL;

else // 结点的值不为空

{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点

if(!T)

exit(OVERFLOW);

T->data=number; // 将值赋给T所指结点

CreateBiTree(T->lchild); // 递归构造左子树

CreateBiTree(T->rchild); // 递归构造右子树

}

}

void DestroyBiTree(BiTree &T)

{ // 初始条件：二叉树T存在。 *** 作结果：销毁二叉树T

if(T) // 非空树

{ DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何 *** 作

DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何 *** 作

free(T); // 释放根结点

T=NULL; // 空指针赋0

}

}

void PreOrderTraverse(BiTree T,void(Visit)(int))

{ // 初始条件：二叉树T存在，Visit是对结点 *** 作的应用函数。修改算法61

// *** 作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次

if(T) // T不空

{ Visit(T->data); // 先访问根结点

PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树

PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树

}

}

void InOrderTraverse(BiTree T,void(Visit)(int))

{ // 初始条件：二叉树T存在，Visit是对结点 *** 作的应用函数

// *** 作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次

if(T)

{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树

Visit(T->data); // 再访问根结点

InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树

}

}

void PostOrderTraverse(BiTree T,void(Visit)(int))

{ // 初始条件：二叉树T存在，Visit是对结点 *** 作的应用函数

// *** 作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次

if(T) // T不空

{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树

PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树

Visit(T->data); // 最后访问根结点

}

}

void main()

{

BiTree T;

InitBiTree(T); // 初始化二叉树T

printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n");

CreateBiTree(T); // 建立二叉树T

printf("先序递归遍历二叉树：\n");

PreOrderTraverse(T,visit); // 先序递归遍历二叉树T

printf("\n中序递归遍历二叉树：\n");

InOrderTraverse(T,visit); // 中序递归遍历二叉树T

printf("\n后序递归遍历二叉树：\n");

PostOrderTraverse(T,visit); // 后序递归遍历二叉树T

}

先序列号为这个，那么在编辑的时候，可以先进行用顺序的方式，然后再进行。

后序序列是CBA。根据前序，可以确定A为根，A在中序中的位置，可以确定CB为A的左子树上的结点，没有右子树。确定A之后，再看中序第二值为B，查看B在中序中的位置，C在B左边，确定C为B的左子树。

扩展资料：

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个 *** 作：

（1）访问结点本身(N)，

（2）遍历该结点的左子树(L)，

（3）遍历该结点的右子树(R)。

参考资料来源：百度百科-遍历序列

#include "stdioh"

#include "stdlibh"

#include "stringh"

#define null 0

struct node

{

char data;

struct node lchild;

struct node rchild;

};

//先序，中序 建树

struct node create(char pre,char ord,int n)

{

struct node head;

int ordsit;

head=null;

if(n<=0)

{

return null;

}

else

{

head=(struct node )malloc(sizeof(struct node));

head->data=pre;

head->lchild=head->rchild=null;

ordsit=0;

while(ord[ordsit]!=pre)

{

ordsit++;

}

head->lchild=create(pre+1,ord,ordsit);

head->rchild=create (pre+ordsit+1,ord+ordsit+1,n-ordsit-1);

return head;

}

}

//中序递归遍历

void inorder(struct node head)

{

if(!head)

return;

else

{

inorder(head->lchild );

printf("%c",head->data );

inorder(head->rchild );

}

}

//中序非递归遍历

void inorder1(struct node head)

{

struct node p;

struct node stack[20];

int top=0;

p=head;

while(p||top!=0)

{

while (p)

{

stack[top++]=p;

p=p->lchild ;

}

p=stack[--top];

printf("%c ",p->data );

p=p->rchild ;

}

}

//主函数

int main()

{

struct node head;

char pre[30],ord[30];

int n;

gets(pre);

gets(ord);

n=strlen(pre);

head=create(pre,ord,n);

inorder(head);

printf("\n");

inorder1(head);

printf("\n");

}

关于递归，你可以看成是一句一句往下运行嘛。需要保存状态的时候，系统就会自动用栈帮你保存。就依你说得那个为例：

n为全局变量，初值为0；

第一次调用height(T)，假设T！=NULL

由于T!=NULL：跳过if (T==NULL) return 0;

关键到了u=height(T->lchild); 调用本身的函数：此时的T->lchild保存在栈中，既然是调用就得从函数开头执行：

看下这时候T2（其实就是T->lchild），if (T==NULL) return 0；

这里假设T不是NULL，就继续运行在遇到u=height(T->lchild); 在调这个函数本身——

这里就假设它为T->lchild==NULL吧。这下可好，这个函数执行return 0；

慢着：第二次函数调用u=height(T->lchild)中的函数值已经计算出来啦。这时u=0；

你还记得第二次调用运行到了v=height(T->rchild); 这句话吧？好，这个过程就和u=height(T->lchild)完全一样。

这里也假设得到的v=0

则第二次调用到了if (u>n) return (u+1)

return (v+1)

得到一个返回值，不如就假设u〉n，于是返回值1；

好，这一波完毕；

你还记得第一次调用的height吧，这时把返回值给u,u=1；

然后执行到第一次调用中的v=height(T->rchild); 了。分析同上。

这个过程的确比较复杂。慢慢琢磨吧。呵呵。

#include

using namespace std;

typedef struct TNode//二叉树结构

{

char nodeValue;//结点的值

TNode left;//左子树

TNode right;//右子树

}BiTree;

void CreateBiTree(BiTree &T)//中序遍历方式创建二叉树 ,输入#代表该结点为空

{

char nodeValue;

cin>> nodeValue;

if(nodeValue!='#')//结点非空

{

T=new TNode;

T->nodeValue=nodeValue;

CreateBiTree(T->left);

CreateBiTree(T->right);

}

else T=NULL;

}

int CountLeaf(BiTree T)

{

static int LeafNum=0;//叶子初始数目为0，使用静态变量

if(T)//树非空

{

if(T->left==NULL&&T->right==NULL)//为叶子结点

LeafNum++;//叶子数目加1

else//不为叶子结点

{

CountLeaf(T->left);//递归统计左子树叶子数目

CountLeaf(T->right);//递归统计右子树叶子数目

}

}

return LeafNum;

}

//用来测试的main函数，

int main()

{

BiTree T;

int leafNum;

cout<<"请输入中序遍历的二叉树序列(#号代表该结点为空)：如(ABC##DE#G##F###)"<<endl;

CreateBiTree(T);

leafNum=CountLeaf(T);

cout<<"该二叉树中叶子结点数为："<<leafNum<<endl;

return 0;

}

以上就是关于假设二叉树以二叉链表作为存储结构，试设计一个计算二叉树叶子结点树的递归算 法 要求用递归算法啊全部的内容，包括:假设二叉树以二叉链表作为存储结构，试设计一个计算二叉树叶子结点树的递归算 法 要求用递归算法啊、c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法、怎么用递归算法遍历二叉树的前序序列等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！