树：
树的概念：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 结构特点：树是一个层次结构,“有且仅有一个根结点无前驱(第一层);有一或多个叶结点无后继;其余结点有唯一前驱和若干后继”? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 递归描述：空是树；不空时，树由根结点(唯一)及该根结点的若干 “子树”组成。每个子树也都是树（符合前述定义）
树的相关术语：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 空树 ?根结点(可标识一颗树) ? 叶子结点? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 结点的子树 ?树的子树? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 结点的度 ?(叶子结点的度为几) ? 树的度? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 终端结点 ?非终端(分支)结点 ?内部结点? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 结点的孩子/双亲/兄弟/祖先/子孙/堂兄弟? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 结点的层次(从1始) ? ?树的深度、宽度? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 无序树 有序树 森林:互不相交的树的集合? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Tree=(root, F)，F={T1,…,Tm}? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Ti={ri,Fi},<root,ri>∈RF? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 路径与路径长度，如A->D->J长为2? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 从根结点到任意结点存在唯一路径
二叉树：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 定义：度不大于2的有序树(空树也是二叉树)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 二叉树的性质：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 性质1：在二叉树的第i层上最多有2i-1个结点? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 性质2：深度为K的二叉树最多有2K-1个结点? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 性质3： 对于任意一棵二叉树BT，如果度 为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 性质4：含n个结点的完全二叉树深度为 log2n?+1? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 性质5：若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中编号为 i 的结点： (1) 若 i=1，则该结点是二叉树的根，无双亲，否则，其双亲节点的编号为 i/2； (2) 其左孩子节点编号为 2i（前提是2n没有越界，即2i<=n，否则无左孩子)； (3) 其右孩子节点编号为 2i+1（前提是2n+1没有越界，即2i+1<=n，否则无右孩子)；
二叉树的链式存储：二叉链表
二叉树的操作：1.求二叉树的节点数 2.求二叉树的叶子节点数 3.求二叉树的深度 4.二叉树的创建 5.二叉树的销毁
1.二叉树求结点数：
int NodeCount(BiTree T){
//递归边界：空树节点数为0
//递归关系：非空时，二叉树节点数为 左子树节点数+右子树节点数+ 1. 子树节点数递归可得
if(!T){
n=0;
}else{
n = NodeCount(T->lchild)
+NodeCount(T->rchild)
+1;
}
return n;
}
2.二叉树求叶子节点树：
int LeafCount(BiTree T){
//递归边界：空树叶子数为0；单节点二叉树叶子数为1
//递归关系：其他情况下，二叉树的叶子数为左右子树叶子数之和
if(!T){ n=0;
}else if(!T->lchild && !T->rchild ){
n=1;
}else{
n=LeafCount(T->lchild)
+LeafCount(T->rchild);
}
return n;
}
或者：
int LeafCount(BiTree T){
int m,n;
if(!T)
return 0;
else{
if(!T->lchild&&!T->rchild)
return 1;
m=LeafCount(T->lchild);
n=LeafCount(T->rchild);
return m+n;
}
}3.求二叉树的深度：
int GetDepthOfBiTree ( BiTree T){
int m,n;
if(!T)
return 0;
else{
m=GetDepthOfBiTree(T->lchild);
n=GetDepthOfBiTree(T->rchild);
return m<n?n+1:m+1;
}
}合起来的代码：
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define INFEASIBLE -2
typedef int Status;
typedef int TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status CreateBiTree(BiTree &T){
int n;
scanf("%d",&n);
if(n==0)
T=NULL;
else{
T=(BiTree)malloc(sizeof(BiTree));
if(!T)
exit(OVERFLOW);
//先序递归创建二叉树
T->data=n;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
int GetDepthOfBiTree ( BiTree T){
int m,n;
if(!T)
return 0;
else{
m=GetDepthOfBiTree(T->lchild);
n=GetDepthOfBiTree(T->rchild);
return m<n?n+1:m+1;
}
}
int LeafCount(BiTree T){
int m,n;
if(!T)
return 0;
else{
if(!T->lchild&&!T->rchild)
return 1;
m=LeafCount(T->lchild);
n=LeafCount(T->rchild);
return m+n;
}
}
int main(){
BiTree T;
int depth,leaves;
CreateBiTree(T);
depth=GetDepthOfBiTree(T);
leaves=LeafCount(T);
printf("%d %d",depth,leaves);
return 0;
}
?二叉树统计指定取值元素节点的个数：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?编写函数计算二叉树中数据域取值为x的节点个数。二叉树采用二叉链表存储结构。
函数接口定义：int XNodeCountOfBiTree ( BiTree T, TElemType x);? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 其中?T是二叉树根节点的地址;x是用户给定的一个元素值。函数须返回二叉树中取值等于x的节点个数。
输入样例：（注意输入0为空数）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1?3 0 0 5 3 0 0 0? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 3? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?输出样例：2
//头文件包含
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>
//函数状态码定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define INFEASIBLE -2
typedef int Status;
//二叉链表存储结构定义
typedef int TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
//先序创建二叉树各结点，输入0代表创建空树。
Status CreateBiTree(BiTree &T){
TElemType e;
scanf("%d",&e);
if(e==0)T=NULL;
else{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T)exit(OVERFLOW);
T->data=e;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
//下面是需要实现的函数的声明
int XNodeCountOfBiTree ( BiTree T, TElemType x);
//下面是主函数
int main()
{
BiTree T;
int n;
TElemType x;
CreateBiTree(T); //先序递归创建二叉树
scanf("%d", &x);
n= XNodeCountOfBiTree(T,x);
printf("%d",n);
return 0;
}
/* 请在这里填写答案 */
int XNodeCountOfBiTree ( BiTree T, TElemType x){
int m,n;
if(T==NULL)
return 0;
else{
m=XNodeCountOfBiTree(T->lchild,x);
n=XNodeCountOfBiTree(T->rchild,x);
if(x==T->data)
return m+n+1;
else
return m+n;
}
}
统计二叉树中具有度为1的结点数目：
输入格式：测试数据有多组，处理到文件尾。每组测试数据在一行中输入一个字符串（不含空格且长度不超过80），表示二叉树的先序遍历序列，其中字符*表示虚结点（对应的子树为空）。
输出格式：对于每组测试，对所建立的二叉树，输出该二叉树中具有度为1的结点数目。输出格式为：“num: d”,其中d为二叉树中具有度为1的结点数目。
输入样例：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? HDA**C*B**GF*E***
A*B*C*D*E*F**
输出样例：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? num: 3
num: 5
//头文件包含
#include <bits/stdc++.h>
using namespace std;
//函数状态码定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define INFEASIBLE -2
int i=0;
typedef int Status;
//二叉链表存储结构定义
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
//先序创建二叉树各结点，输入0代表创建空树。
Status CreateBiTree(BiTree &T,string s){
if(s[i]=='*'){
T=NULL;
i++;
return OK;
}
else{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T)exit(OVERFLOW);
T->data=s[i];
i++;
CreateBiTree(T->lchild,s);
CreateBiTree(T->rchild,s);
}
return OK;
}
Status DestroyTree(BiTree &T){
if(!T)
return OK;
DestroyTree(T->lchild);
DestroyTree(T->rchild);
free(T);
}
int CountTree(BiTree T){
if(!T)
return 0;
else{
if((!T->lchild&&T->rchild)||(!T->rchild&&T->lchild))
return 1+CountTree(T->lchild)+CountTree(T->rchild);
else
return CountTree(T->lchild)+CountTree(T->rchild);
}
}
//下面是主函数
int main()
{
BiTree T;
string s;
while(cin>>s){
i=0;
if(CreateBiTree(T,s)){
int n=CountTree(T);
cout<<"num: "<<n<<endl;
DestroyTree(T);
}
}
return 0;
}