目录

18924 二叉树的宽度

18923 二叉树的直径

18724 二叉树的遍历运算

8609 哈夫曼树

额外题：任意两节点距离

18924 二叉树的宽度

#include 
#include 
#include 

using namespace std;



struct tree
{
    int l;
    int r;
} v[100];

queue  q;

int main()
{
    int n;
    cin>>n;
    n--;
    while(n--)
    {
        int x,y;
        cin>>x>>y;
        if(v[x].l)
            v[x].r=y;
        else
            v[x].l=y;
    }
    int curwide=1,maxwide=1;
    q.push(1);
    while(!q.empty())
    {
        curwide=q.size();
        if(maxwide 
 
 
18923 二叉树的直径 
#include
#include
#include

//用数组储存二叉树的特殊性
using namespace std;

int ans=0;

struct Node
{
    int l,r;
};
Node a[10000];
int dd(int x)
{
    if(!x) //非法输入 或是已无孩子（该题的特殊性）
        return 0;
    //收集答案
    int n=dd(a[x].l);
    int m=dd(a[x].r);
    int len=max(n,m)+1; //选出较大的分支
    ans=max(ans,m+n); //记录直径，要求的答案是这个
    return len;  //返回的是长度，不是直径
}


int main()
{
    int i,n,x,y;
    //输入环节
    cin>>n;
    for(i=1; i>x>>y;
        if(a[x].l==0)
            a[x].l=y;
        else
            a[x].r=y;
    }
    //输入结束

    //开始处理
    dd(1);
    cout<
 
 
 
18724 二叉树的遍历运算 
#include
#include
using namespace std;
char pre[100];//全局变量，先序序列
char in[100];//全局变量，中序序列
void solve(int xl,int xr,int zl,int zr)

{
    int i;
    if(xl>xr)
        
        return ;
    char ch=pre[xl];//根结点就是先序序列的第一个
    for(i=zl; i<=zr; i++) //在中序序列中找出根节点的下标
    {
        if(in[i]==ch)
            break;
    }
    //对序列进行二分递归
    int lenl=i-zl;//左子树的序列长度

    solve(xl+1,xl+lenl,zl,zl+lenl-1);//左子树，重点记忆
    solve(xl+lenl+1,xr,zl+lenl+1,zr);//右子树，重点记忆
    cout< 
 
 
8609 哈夫曼树 
#include 
#include 

typedef struct //哈夫曼树的各节点存储在数组中，且0号单元不使用。因此总共需要大小为2n的数组，其中1~n号单元存储叶子结点，后面的n-1个单元存储其他节点
{
    int weight;
    int parent, lchild, rchild;
} HTNode, *HuffmanTree;
typedef char **HuffmanCode; //哈夫曼编码表是一个二维数组，存储着n个一维数组，每个一维数组存储这一个节点的哈夫曼编码

void Select(HuffmanTree HT, int n, int &s1, int &s2) //记住0号位不储存
{
    

    int i,min1=999,min2=1000;
    s1=s2=0;
    for(i=1 ; i<=n ; i++)
    {
        if(!HT[i].parent) //没配对的
        {
            if(HT[i].weight=min1&&HT[i].weight 
 
 
额外题：任意两节点距离 
#include 

using namespace std;








#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK  1
#define ERROR  0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int  Status;

typedef char  ElemType;
typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;

Status CreateBiTree(BiTree &T)    // 算法6.4
{
    // 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
    // 构造二叉链表表示的二叉树T。
    char ch;
    scanf("%c",&ch);
    if (ch=='#') T = NULL;
    else
    {
        if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
        T->data=ch; // 生成根结点
        CreateBiTree(T->lchild);   // 构造左子树
        CreateBiTree(T->rchild);  // 构造右子树
    }
    return OK;
} // CreateBiTree






BiTNode* findzuxian(BiTNode*T,char n1,char n2)
{
    if(!T)
        return NULL;
    if(T->data==n1||T->data==n2)
    {
        return T; //想不到
    }
    BiTNode*l=findzuxian(T->lchild,n1,n2);
    BiTNode*r=findzuxian(T->rchild,n1,n2);
    if(l&&r)
        return T;
    return (l==NULL?r:l);
}

int dfs(BiTNode*T,char n)
{
    if(T==NULL)
        return -1;
    if(T->data==n)
        return 0;

    int l=dfs(T->lchild,n);
    if(l==-1)
        l=dfs(T->rchild,n);
    if(l!=-1)
        return l+1;
    else
        return -1;

}

int main()   //主函数
{
    BiTNode*T=NULL;
    CreateBiTree(T);

    char n1,n2;
    cin>>n1>>n2;
    BiTNode*tmp=findzuxian(T,n1,n2);

    int dista=dfs(T,tmp->data);
    int dist1=dfs(T,n1);
    int dist2=dfs(T,n2);

    cout<