Java教程

数据结构-树与二叉树-算法实现

本文主要是介绍数据结构-树与二叉树-算法实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

任务

  1. 假设二叉树采用链式方法存储,数据结构定义如下:
typedef char DataType;
struct node
{
  DataType info ;
  struct node *lchild , *rchild ;
};

完成两个函数编写

  • 请编写算法计算二叉树T的高度的函数
  • 请编写算法计算二叉树T的叶子结点数的函数
  1. 已知某二叉树的先根周游序列是:ABDEGCFHIJ,中根周游序列是:DBGEAHFIJC,画出这课二叉树,并给出二叉树的后根周游序列。

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

元素 A B C D F E G H
下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

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;
}

运行结果

第一题

第二题

第三题

第四题

这篇关于数据结构-树与二叉树-算法实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!