数据结构--树与二叉树练习题

1 . 设一棵二叉树的先序序列：ABDFCEGH,中序序列：BFDAGEHC.
（1）画出这棵二叉树。
（2）画出这棵二叉树的后序线索树。
（3）将这棵二叉树转换成对应的树（或森林）

2 . 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07、0.19、0.02、0.06、0.32、0.03、0.21和0.10。
（1）试为这8个字母设计哈夫曼编码。
（2）试设计另一种由二进制表示的等长编码方案。
（3）对于上述实例，比较两种方案的优缺点。

3 . 【408真题】如果一棵非空k(k≥2)叉树T中每个非叶子结点都有k个孩子，则称T为正则后k树。请回答下列问题并给出推导过程。

（1）若T有m个非叶子结点，则T中的叶子结点有多少个？
（2）若T的高度为h(根的高度为1)，则T的结点个数最多为多少个？最少为多少个？（提示，答案皆与K有关）

4 . 【算法题】以二叉链表为存储结构，交换二叉树每个结点的左孩子和有孩子。(编程实现后，只需将swapLR函数写在本子上）

//二叉树编程练习
typedef char ElemType;

typedef struct BiTNode{
    //数据域
    ElemType data;
    //指向左孩子结点的指针
    struct BiTNode *lchild;
    //指向左孩子结点的指针
    struct BiTNode *rchild;
}BiTNode, *BiTree;

//创建一个二叉树
//按照先序遍历创建二叉树，空节点使用#表示，每个字符以空格隔开
//ABD##E##CF##G##    是一个层次遍历序列为ABCDEFE的满二叉树
int CreateBiTree(BiTree *T){
    char ch;
    scanf("%c", &ch);
    //如果输入为空，则返回一颗空树
    if(ch == '#'){
        *T = NULL;
    } else {
        *T = (BiTNode *) malloc(sizeof(BiTNode));
        if(!(*T)){
            exit(OVERFLOW);
        }
        (*T)->data = ch;
        CreateBiTree(&((*T)->lchild));
        CreateBiTree(&((*T)->rchild));
    }
    return OK;
}

//交换二叉树每个结点的左右子树
void swapLR(BiTree *T){
  	//...
}

//打印二叉树
void printTree(BiTNode *root, int spaces) {
    int loop;
    while (root != NULL) {
        printTree(root->rchild, spaces + 4);

        for (loop = 1; loop <= spaces; loop++) {
            printf(" ");
        }
        printf("%cn", root->data);
        printTree(root->lchild, spaces + 4);
        root = NULL;
    }
}

int main(int argc, const char * argv[]) {
    BiTree root;
    CreateBiTree(&root);
    printf("root 结点的值为：%cn", root->data);
    printf("root 结点左子树的值为：%cn", root->lchild->data);
    printf("root 结点右子树的值为：%cn", root->rchild->data);
    
    printTree(root, 0);
  	//调用交换二叉树
  	swapLR(&root);
  	printTree(root, 0);
    return 0;
}