1．编写递归算法，计算二叉树中叶子结点的数目

Question

1．编写递归算法，计算二叉树中叶子结点的数目？2．写出求二叉树深度的算法，先定义二叉树的抽象数据类型？3．试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。

Answer 1

#include<iostream>
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;
}

Answer 2

int BtreeDepth(BiTNode *BT){//求二叉树的深度
if (BT==NULL)//空树则返回0
return 0;
else{
int dep1=BtreeDepth(BT->lchild );//递归调用逐层分析
int dep2=BtreeDepth(BT->rchild );
if(dep1>dep2)
return dep1+1;
else
return dep2+1;
}
}
int Leave(BiTNode *BT){//求二叉树中的叶子节点数
if (BT==NULL)
return 0;
else{
if(BT->lchild ==NULL && BT->rchild ==NULL)
return 1;
else
return(Leave(BT->lchild )+Leave(BT->rchild ));
}
}

这是学数据结构时做的练习，用的是递归的形式，理解时需稍稍的想一下，但是函数这样写起来会相对比较的简单。

Answer 3

#include <iostream>
using namespace std;static int sum=0;template<typename T>
void Count(T* root){
if(root==NULL)
++sum;
else{
Count(root->left);
Count(root->right);
}
}int main(void){
//test
//cout<<sum<<endl; //即可
return 0;
} //这里我没有树的节点定义，所以直接用模板替代了本回答被网友采纳

Answer 4

第三题：Console.Write("请输入一个字符串(以@结束)：");
string str = Console.ReadLine();
if (str[str.Length - 1] == '@')
{
if (str.Length % 2 == 1)
{
Console.WriteLine("不是回文");
}
else
{
string str1 = "";
string str2 = "";
for (int i = 0; i < str.Length / 2; i++)
{
str1 = str1 + str[i];
}
for (int i = str.Length - 2; i >= str.Length / 2 - 1; i--)
{
str2 = str2 + str[i];
}
if (str1.Equals(str2))
{
Console.WriteLine("是回文");
}
else
{
Console.WriteLine("不是回文");
}
}
}
else
{
Console.WriteLine("请以@符号结束输入！");
}

Answer 5

#include <stdio.h>

#include<malloc.h>

struct node{

char info;

struct node *llink, *rlink;

};

typedef struct node NODE;

NODE *create(){ //构造二叉树

char x;

NODE *p;

scanf("%c", &x);

printf("%c", x); //打印出已输入的二叉树

if(x!='.'){

p=(NODE *)malloc(sizeof(NODE)); p->info=x;

p->llink=create();

p->rlink=create();

}

else p=NULL;

return p;

}

int run(NODE *t){

static int count=0;

if(t){

run(t->llink); //递归遍历左子树，直到叶子处

run(t->rlink); //递归遍历右子树，直到叶子处

if(t->llink ==NULL && t->rlink == NULL) { count++;

}

}

return count;

}

main()

{ NODE *T;

int left_number;

printf("请输入一棵树:\n" );

T=create();

printf("\n");

if(!T) printf("This is a empty binary tree.");

else{

left_number=run(T);

printf("\n这棵树共有 %d 个子叶. \n", left_number);

}

printf("\n");}