二叉树算法题（写一个算法，计算给定二叉树的叶结点数）

：暂无数据 2026-08-27 01:20:01 ：0

各位老铁们，大家好，今天由我来为大家分享二叉树算法题，以及写一个算法，计算给定二叉树的叶结点数的相关问题知识，希望对大家有所帮助。如果可以帮助到大家，还望关注收藏下本站，您的支持是我们最大的动力，谢谢大家了哈，下面我们开始吧！

本文目录

写一个算法，计算给定二叉树的叶结点数
数据结构试题；设一棵二叉树以二叉链表为存储结构，试写一算法求该二叉树上度为2的结点个数
c++二叉树求双亲算法问题
一道算法题，用python初始化一颗二叉树并求解其最短路径的值
某颗二叉树中有2000个节点，则它的最小高度怎么求
这是一道数据结构的题：试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构
设二叉树的存储结构为二叉链表，编写有关二叉树的递归算法：
在一棵二叉树先序遍历、中序遍历、后序遍历所产生序列中，所有叶子结点先后顺序（）

写一个算法，计算给定二叉树的叶结点数

【答案】：(1)数据结构
采用二叉树的链接表示。
(2)算法
int num_of_leaves(BinTree t){ /*计算二叉树的叶结点个数*/
if(t==NULL)return 0; /*空树,返回0*/
if(t-＞llink==NULL&&t-＞rlink==NULL)return 1;
/*根结点是树叶,返回1*/
return num_of_leaves(t-＞llink)+num_of leaves(t-＞rlink);
/*返回"左子树的叶结点数+右子树的叶结点数"*/
}
(3)代价分析
该算法访问每个结点各一次，时间代价为O(n)，空间代价为O(h)。

数据结构试题；设一棵二叉树以二叉链表为存储结构，试写一算法求该二叉树上度为2的结点个数

算法步骤：
设根节点为 r。
情况1，如果 r 既有左孩子又有右孩子，则返回 1 + 递归求左子树度为2节点个数 + 递归求右子树度为2节点个数。
情况2，如果 r 只有左孩子，则返回递归求左子树度为2节点个数。
情况3，如果 r 只有右孩子，则返回递归求右子树度为2节点个数。
情况4，如果 r 既没有左孩子又没有右孩子，则返回 0。

c++二叉树求双亲算法问题

1、以二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。
#define M 10
typedef int DataType;/*元素的数据类型*/
typedef struct node
{ DataType data;
struct node *lchild,*rchild;
}BitTNode,*BiTree;
int front=0,rear=0;
BitTNode *que;
BitTNode *creat()
{BitTNode *t;
DataType x;
scanf("%d",&x);
if(x==0) t=NULL;
else{ t=(BitTNode *)malloc(sizeof(BitTNode));
t-》data=x;
t-》lchild=creat();
t-》rchild=creat();
}
return(t);
}/*creat*/
/* 前序遍历二叉树t */
void preorder(BiTree t)
{ if(t!=NULL)
{ printf("%4d",t-》data);
preorder(t-》lchild);
preorder(t-》rchild);
}
}
/* 中序遍历二叉树t */
void inorder(BiTree t)
{ if(t!=NULL)
{ inorder(t-》lchild);
printf("%4d",t-》data);
inorder(t-》rchild);
}
}
/* 后序遍历二叉树t */
void postorder(BiTree t)
{ if(t!=NULL)
{ postorder(t-》lchild);
postorder(t-》rchild);
printf("%4d",t-》data);
}
}
void enqueue(BitTNode *t)
{if (front!=(rear+1)%M)
{ rear=(rear+1)%M;
que=t;
}
}/*enqueue*/
BitTNode * delqueue()
{ if(front==rear)return NULL;
{ front=(front+1)%M;
return (que);
}
}/*delqueue*/
/* 按层次遍历二叉树t */
void levorder(BiTree t)
{ BitTNode *p;
if(t!=NULL)
{ enqueue(t);
while (front!=rear)
{ p=delqueue();
printf("%4d",p-》data);
if(p-》lchild!=NULL) enqueue(p-》lchild);
if(p-》rchild!=NULL) enqueue(p-》rchild);
}
}
}/* levorder */
main()
{BitTNode *root;
root=creat();
printf("\n按先序遍历次序生成的二叉树");
printf("\n前序遍历二叉树");
preorder(root);
printf("\n中序遍历二叉树");
inorder(root);
printf("\n后序遍历二叉树");
postorder(root);
printf("\n层次顺序遍历二叉树");
levorder(root);
}
2、以二叉链表作存储结构，试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法
#include 《stdio.h》
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *left,*right;
} BTree;
BTree * createbt( )
{ BTree *q;
struct node1 *s;
int j,i,x;
printf("建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\n\n");
printf("i,x = ");
scanf("%d,%c",&i,&x);
while(i != 0 && x != ’$’)
{ q = (BTree*)malloc(sizeof(BTree)); /*建立一个新结点q*/
q-》data = x; q-》left = NULL; q-》right = NULL;
s = q; /*q新结点地址存入s指针数组中*/
if(i != 1) /*i = 1，对应的结点是根结点*/
{ j = i / 2; /*求双亲结点的编号j*/
if(i % 2 == 0)
s-》left = q; /*q结点编号为偶数则挂在双亲结点j的左边*/
else
s-》right = q; /*q结点编号为奇数则挂在双亲结点j的右边*/
}
printf("i,x = ");
scanf("%d,%c",&i,&x);
}
return s; /*返回根结点地址*/
}
void preorder(BTree *BT)
/* 前序遍历二叉树t */
{ if(BT!=NULL)
{ printf("%4c", BT -》data);
preorder(BT -》left);
preorder(BT -》right);
}
}
int BTreeDepth(BTree *BT)
{
int leftdep,rightdep;
if (BT==NULL)
return(0);
else
{
leftdep=BTreeDepth(BT-》left);
rightdep=BTreeDepth(BT-》right);
if (leftdep》rightdep)
return(leftdep+1);
else
return(rightdep+1);
}
}
int nodecount(BTree *BT)
{
if (BT==NULL)
return(0);
else
return(nodecount(BT-》left)+nodecount(BT-》right)+1);
}
int leafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT-》left==NULL && BT-》right==NULL)
return(1);
else
return(leafcount(BT-》left)+leafcount(BT-》right));
}
int notleafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT-》left==NULL && BT-》right==NULL)
return(0);
else
return(notleafcount(BT-》left)+notleafcount(BT-》right)+1);
}
int onesoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if ((BT-》left==NULL && BT-》right!=NULL) ||
(BT-》left!=NULL && BT-》right==NULL))
return(onesoncount(BT-》left)+onesoncount(BT-》right)+1);
else
return(onesoncount(BT-》left)+onesoncount(BT-》right));
}
int twosoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT-》left==NULL || BT-》right==NULL)
return(twosoncount(BT-》left)+twosoncount(BT-》right));
else if (BT-》left!=NULL && BT-》right!=NULL)
return(twosoncount(BT-》left)+twosoncount(BT-》right)+1);
}
main()
{
BTree *B;
B=creatree();
printf("\n按先序遍历次序生成的二叉树");
preorder(B);
printf("\n二叉树深度:%d\n",BTreeDepth(B));
printf("总结点个数:%d\n",nodecount(B));
printf("叶子结点个数:%d\n",leafcount(B));
printf("非叶子结点个数:%d\n",notleafcount(B));
printf("具有双孩子结点个数:%d\n",twosoncount(B));
printf("具有单孩子结点个数:%d\n",onesoncount(B));
}

一道算法题，用python初始化一颗二叉树并求解其最短路径的值

　　二叉树算法，可能按照你的需求不是很多：
　　下面是我用的一个，不过你可以借鉴一下的：
　　# -*- coding: cp936 -*-
　　import os
　　class Node(object):
　　"""docstring for Node"""
　　def __init__(self, v = None, left = None, right=None, parent=None):
　　self.value = v
　　self.left = left
　　self.right = right
　　self.parent = parent
　　class BTree(object):
　　"""docstring for BtTee """
　　def __init__(self):
　　self.root = None
　　self.size = 0
　　def insert(self, node):
　　n = self.root
　　if n == None:
　　self.root = node
　　return
　　while True:
　　if node.value 《= n.value:
　　if n.left == None:
　　node.parent = n
　　n.left = node
　　break
　　else:
　　n = n.left
　　if node.value 》 n.value:
　　if n.right == None:
　　n.parent = n
　　n.right = node
　　break
　　else:
　　n = n.right
　　def find(self, v):
***隐藏网址***
　　while True:
　　if n == None:
　　return None
　　if v == n.value:
　　return n
　　if v 《 n.value:
　　n = n.left
　　continue
　　if v 》 n.value:
　　n = n.right
　　def find_successor(node):
　　’’’查找后继结点’’’
　　assert node != None and node.right != None
　　n = node.right
　　while n.left != None:
　　n = n.left
　　return n
　　def delete(self, v):
　　n = self.find(v)
　　print "delete:",n.value
　　del_parent = n.parent
　　if del_parent == None:
　　self.root = None;
　　return
　　if n != None:
　　if n.left != None and n.right != None:
　　succ_node = find_successor(n)
　　parent = succ_node.parent
　　if succ_node == parent.left:
　　#if succ_node is left sub tree
　　parent.left = None
　　if succ_node == parent.right:
　　#if succ_node is right sub tree
　　parent.right = None
　　if del_parent.left == n:
　　del_parent.left = succ_node
　　if del_parent.right == n:
　　del_parent.right = succ_node
　　succ_node.parent = n.parent
　　succ_node.left = n.left
　　succ_node.right = n.right
　　del n
　　elif n.left != None or n.right != None:
　　if n.left != None:
　　node = n.left
　　else:
　　node = n.right
　　node.parent = n.parent
　　if del_parent.left == n:
　　del_parent.left = node
　　if del_parent.right == n:
　　del_parent.right = node
　　del n
　　else:
　　if del_parent.left == n:
　　del_parent.left = None
　　if del_parent.right == n:
　　del_parent.right = None
　　def tranverse(self):
　　def pnode(node):
　　if node == None:
　　return
　　if node.left != None:
　　pnode(node.left)
　　print node.value
　　if node.right != None:
　　pnode(node.right)
　　pnode(self.root)
　　def getopts():
　　import optparse, locale
　　parser = optparse.OptionParser()
　　parser.add_option("-i", "--input", dest="input", help=u"help name", metavar="INPUT")
　　(options, args) = parser.parse_args()
　　#print options.input
　　return (options.input)
　　if __name__ == ’__main__’:
　　al =
　　bt = BTree()
　　for x in al :
　　bt.insert(Node(x))
　　bt.delete(12)
　　bt.tranverse()
　　n = bt.find(12)
　　if n != None:
　　print "find valud:",n.value

某颗二叉树中有2000个节点，则它的最小高度怎么求

11。

计算过程如下：

1、具有n个结点的m叉树的最小高度为logm(n(m-1)+1)或 logm((n-1)(m-1)+1)+1 。

2、推理： mk-1＜n(m-1)+1≤mk →logm(n(m-1)+1)≤k＜logm(n(m-1)+1)+。

3、k只能取整数，所以k=logm(n(m-1)+1)。

4、现在是下取整(log2(2000)) + 1= 11；

5、所以，某颗二叉树中有2000个节点，则它的最小高度是11。

扩展资料：

本题另一算法：

1、最小高度自然就是等于2000个结点的完全二叉树的高度；

2、设根结点高度为1，n个结点完全二叉树高度：下取整(log2n) + 1；

3、下取整(log2(2000)) + 1= 11；

4、所以，某颗二叉树中有2000个节点，则它的最小高度是11。

一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子结点，至多有2k-1个结点。

这是一道数据结构的题：试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构

用递归：

a=当前节点是否为排序树，是为1，不是为0

f(x)=1 当x为叶节点

f(x)= a&&f(x-》lchid)&&f(x-rchild) 当x非叶节点

----------------------------------------------------------------------

int IsAVTree(BiTree t)

{

int a=1;

if(t-》Child==NULL&&t-》Rchild==NULL) return 1; //叶子节点判断

if((t-》Lchild-》data》t-》data)||(t-》Rchild-》datadata))

{

a=0;

a=a&&(isAVTree(t-》Lchild))&&(IsAVTree(t-》Rchild));

}

return a;

}

扩展资料：

构成递归需具备的条件：

一、子问题须与原始问题为同样的事，且更为简单；

二、不能无限制地调用本身，须有个出口，化简为非递归状况处理。

在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。

例如，下列为某人祖先的递归定义：

某人的双亲是他的祖先（基本情况）。某人祖先的双亲同样是某人的祖先（递归步骤）。斐波纳契数列（Fibonacci Sequence），又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8。

设二叉树的存储结构为二叉链表，编写有关二叉树的递归算法：

给了一个程序给你参考，有前中后序遍历，实现了前5个功能。
提示：8功能可以用任意一种遍历方法，在程序中，将打印字符的部分换成自己的判断程序即可。
6功能用后续遍历，当遍历到任意一节点时，判断其孩子是不是叶子，是就删除。
7功能参考求广度的实现】
9功能参考6功能，用前序遍历也可以
10功能也参考求广度的方法
程序：
#include 《stdio.h》
#include 《stdlib.h》
#include 《malloc.h》
#include 《time.h》
#define NUM_NODE12
#define MOST_DEPTH 10
typedef struct BiTree{
int data;
BiTree *lchild;
BiTree *rchild;
}BiTree;
typedef struct Answear{
int Degree0;
int Degree1;
int Degree2;
int Depth;
} Answear;
BiTree* CreateTree(int n)
{
BiTree *t;
if (n 《= 0 || n》 NUM_NODE) return NULL;
if (!(t = (BiTree*)malloc(sizeof(BiTree))))
return NULL;
t-》data = n;
printf("%d ", t-》data);
t-》lchild = CreateTree(2*n);
t-》rchild = CreateTree(2*n+1);
return t;
}
void FreeTree(BiTree *t)
{
if (t)
{
if (t-》lchild)
FreeTree(t-》lchild);
if (t-》rchild)
FreeTree(t-》rchild);
printf("%d ", t-》data);
free(t);
}
}
//中序遍历
void InOrder(BiTree *t)
{
BiTree **stack, **top, *p;
//创建堆栈
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
//初始化堆栈
top = stack;
p = t;
while (p || top》stack)//p不为NULL，堆栈不空
if (p)
{
*top++ = p;//p入堆栈
p = p-》lchild;
}
else
{
p = *--top;//p出栈
if (p)printf("%d ", p-》data);
p = p-》rchild;
}
}
//前序遍历
void PreOrder(BiTree *t)
{
BiTree **stack, **top, *p;
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
top = stack;
p = t;
while (p || top》stack)
if (p)
{
*top++ = p;
if (p)printf("%d ", p-》data);
p = p-》lchild;
}
else
{
p = *--top;
p = p-》rchild;
}
}
//后序遍历
void PostOrder(BiTree *t)
{
BiTree **stack, **top, *p, *p_old, *p_new;
int Flag;
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
top = stack;
Flag = 0;
*top++ = t;
while (top 》 stack)
{
p = *(top-1);
if (p-》lchild && !Flag)
*top++ = p-》lchild;
else
{
if (p-》rchild)
{
*top++ = p-》rchild;
Flag = 0;
}
else
{
p_old = *--top;
printf("%d ", p_old-》data);
while (top 》 stack)
{
p_new = *(top-1);
if (p_old == p_new-》lchild)
{
Flag = 1;
break;
}
else
{
p_new = *--top;
printf("%d ", p_new-》data);
p_old = p_new;
Flag = 0;
}
}
}
}
}
}
//中序遍历求结点的深度和度为0，1,2的结点数，结果保存在pAns指的。。。
void InOrderDO(BiTree *t , Answear * pAns)
{
//遍历用的数据
BiTree **stack, **top, *p;
//求深度的数据
int curDeep, MostDeep;
//创建堆栈
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
//初始化堆栈
top = stack;
p = t;
//初始化数据
curDeep = MostDeep = 0;
pAns-》Degree0 = pAns-》Degree1 = pAns-》Degree2 = 0;
//遍历循环
while (p || top》stack)//p不为NULL，堆栈不空
if (p)
{
*top++ = p;//p入堆栈
p = p-》lchild;
curDeep++;
if (MostDeep 《 curDeep) MostDeep = curDeep; //保存最深度
}
else
{
p = *--top;//p出栈
curDeep--;
//if (p)printf("%d ", p-》data); //Visit结点
//计算个结点的度
if (p-》lchild && p-》rchild) pAns-》Degree2++;
else if (p-》lchild || p-》rchild) pAns-》Degree1++;
else pAns-》Degree0++;
p = p-》rchild;
}
//得到深度
pAns-》Depth = MostDeep;
return ;
}
//前序递归求广度
void Pre(BiTree *T, int* woed, int depth)
{
woed++;
if (T-》lchild) Pre(T-》lchild, woed, depth+1);
if (T-》rchild) Pre(T-》rchild, woed, depth+1);
}
//求广度的程序，返回值为广度
int GetTreeWidth(BiTree *root)
{
int i, WidthOfEachDepth={0};
Pre(root, WidthOfEachDepth, 0);
for (i=1; i《MOST_DEPTH; i++)
if (WidthOfEachDepth)
WidthOfEachDepth;
return WidthOfEachDepth;
}
int main()
{
BiTree *root;
Answear ans;
printf("Create Tree\n");
root = CreateTree(1);
printf("\nInOrder\n");
InOrder(root);
printf("\nPreOrder\n");
PreOrder(root);
printf("\nPostOrder\n");
PostOrder(root);
InOrderDO(root, &ans);
printf("\nTheMostDepth is : %d\n", ans.Depth);
printf("TheMostWidth is : %d\n", GetTreeWidth(root));
printf("Each Degree (0,1,2)is: (%d, %d, %d)\n",
ans.Degree0, ans.Degree1, ans.Degree2);
printf("\nFree Tree\n");
FreeTree(root);
return 0;
}

在一棵二叉树先序遍历、中序遍历、后序遍历所产生序列中，所有叶子结点先后顺序（）

【答案】：B
本题算法与数据结构基本知识。遍历就是按照某条路径访问树中每个结点，使每个结点被访问仅且一次。（1）先序遍历（D L R）：访问根结点；先序遍历左子树；先序遍历右子树。（2）中序遍历（L D R）：中序遍历左子树；访问根结点；中序遍历右子树。（3）后序遍历（L R D）：后序遍历左子树；后序遍历右子树；访问根结点。一棵二叉树不论哪种遍历算法，有以下要点：①所有叶子节点先后顺序不变，总是从左到右排列。②左子树节点，总是出现在右子树节点前面。

OK，关于二叉树算法题和写一个算法，计算给定二叉树的叶结点数的内容到此结束了，希望对大家有所帮助。

二叉树算法题（写一个算法，计算给定二叉树的叶结点数）