任务

1. 假设二叉树采用链式方法存储，数据结构定义如下：

typedef char DataType;
struct node
{
  DataType info ;
  struct node *lchild , *rchild ;
};

完成两个函数编写

• 请编写算法计算二叉树T的高度的函数
• 请编写算法计算二叉树T的叶子结点数的函数

2. 已知某二叉树的先根周游序列是：ABDEGCFHIJ，中根周游序列是：DBGEAHFIJC，画出这课二叉树，并给出二叉树的后根周游序列。

3.已知了一棵二叉树的顺序存储结构如下，其中空白表示结点不存在。请画出这棵二叉树

4.已知一棵度为m的树中有n1个度为1 的结点，n2个度为2的结点，.....nm个
度为m的结点，问该树中有多少个终端结点? ( 要求写出计算推导过程)。

5.设给定权集w＝{2,3,4,7,8,9}

1. 求各权值对应等长二进制编码
2. 试构造关于w的一棵哈夫曼树，并求其哈夫曼编码。

代码实现

第一题

#include <iostream>
using namespace std;
typedef char DataType;
struct node{
  DataType info ;
  struct node *lchild , *rchild ;
};
typedef struct node *BiTree;
/*
函数名：createBiTree
函数功能：创建二叉树，并返回二叉树的根结点指针 
参数：无 
返回值：二叉树的根结点指针 
*/ 
BiTree createBiTree() {
    DataType ipt;
    BiTree root;
    cin>>ipt;
    if(ipt == '#'){
        root = NULL;
        return root;
    } 
    else{
        root = new node; 
        root->info = ipt;
        root->lchild = createBiTree();
        root->rchild = createBiTree();
    }
    return root;
}
// 计算叶子数 
int countLeaf(BiTree T)
{
    static int num = 0;
    if(T)
        {
            if(T->lchild==NULL && T->rchild==NULL)
                num++;
            countLeaf(T->lchild);
            countLeaf(T->rchild);
        }
    return num;
}
// 计算树高 
int countLevel(BiTree root){
    if(root == NULL) return -1;
    else{
        int left, right;
        left = 1 + countLevel(root->lchild);
        right = 1 + countLevel(root->rchild);
        return left>right?left:right;
    }
}
int main(){ 
    BiTree root = createBiTree();
    cout<<countLeaf(root)<<" ->叶子"<<endl;
    cout<<countLevel(root)<<" ->树高"<<endl; 
    return 0;
}

第三题

#include <iostream>
using namespace std;

typedef char DataType;
struct BinTree{
    int curNum;
    int maxNum;
    DataType *info;
};

typedef struct BinTree * tree;

// 创建树
tree createTree(DataType ipt[], int len){
    int i;
    tree root = new struct BinTree;
    root->info = new DataType(len);
    root->curNum = 0;
    for(i=0; i<len; i++) {
        root->info[i] = ipt[i];
        root->curNum++;
    }
    root->maxNum = i;
    return root;
}

// 输出节点元素值
void visit(tree root, int i){
    cout<< root->info[i]<<" ";
}

// 左树
int leftChild(int i){
    return 2*i+1;
}

// 右树
int rightChild(int i){
    return 2*i+2;
}

// 先序
void preOrder(tree root, int k){
    if(root->info[k] == ' ') return ;
    visit(root, k);
    if(leftChild(k) < root->curNum){
        preOrder(root, leftChild(k));
    }
    if(rightChild(k) < root->curNum){
        preOrder(root, rightChild(k));
    }
}

// 中序
void midOrder(tree root, int k){
    if(root->info[k] == ' ') return ;
    if(leftChild(k) < root->curNum){
        midOrder(root, leftChild(k));
    }
    visit(root, k);
    if(rightChild(k) < root->curNum){
        midOrder(root, rightChild(k));
    }
}

// 后序
void lastOrder(tree root, int k){
    if(root->info[k] == ' ') return ;
    if(leftChild(k) < root->curNum){
        lastOrder(root, leftChild(k));
    }
    if(rightChild(k) < root->curNum){
        lastOrder(root, rightChild(k));
    }
    visit(root, k);
}

int main(){
    DataType ipt[] = {'A', 'B', 'C', ' ', ' ', 'D', 'F', ' ', ' ',
                          ' ', ' ', 'E', 'G', ' ', 'H'};
    tree root = createTree(ipt, 14);
    cout<<"先序输出"<<endl; 
    preOrder(root, 0);
    cout<<"\n中序输出"<<endl; 
    midOrder(root, 0);
    cout<<"\n后序输出"<<endl;
    lastOrder(root, 0);
    return 0;
}

运行结果

第一题

第二题

第三题

第四题