树与二叉树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了树与二叉树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1814字，纯文字阅读大概需要3分钟。

内容图文

树和二叉树的思维导图

重要概念：

  (1)树的顺序存储结构：对于一颗树所有节点按照层序自顶向下，同一层自左向右。

（2）二叉树是一个有限的结点集合，这个集合或者为空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成

先序、中序和后序遍历递归算法

(1)代码如下

void PreOrder(BTNode* b) {                //先序遍历递归算法
    if (b != NULL) {
        printf("%c", b->data);            //访问根节点
        PreOrder(b->Ichild);              //先序遍历左子树
        PreOrder(b->rchild);              //先序遍历右子树
    }
}
void InOrder(BTNode* b) {                //中序遍历递归算法
    if (b != NULL) {
        InOrder(b->Ichild);              //中序遍历左子树
        printf("%c", b->data);            //访问根节点
        InOrder(b->rchild);              //中序遍历右子树
    }
}
void PostOrder(BTNode* b) {                //后序遍历递归算法
    if (b != NULL) {
        PostOrder(b->Ichild);              //后序遍历左子树
        PostOrder(b->rchild);              //后序遍历右子树
        printf("%c", b->data);            //访问根节点
    }
}

（2）遍历结果如下

 

构造二叉树

BTNode* CreatBT(char* pre, char* in, int n) {
    //pre存放先序序列，in存放中序序列，n为二叉树结点个数
    BTNode* b;
    char* p;
    int k;
    if (n <= 0)return NULL;
    b = new BTNode;                    //创建二叉树结点b
    b->data = *pre;           
    for (p = in; p < in + n; p++) {    //在中序遍历中找等于*pre字符的位置
        if (*p == *pre)break;          //pre指向根节点
    }
    k = p - in;                       //确定根节点在in中的位置
    b->Ichild = CreatBT(pre + 1, in, k);//递归构造左子树
    b->rchild = CreatBT(pre + 1 + k, in, k);//递归构造右子树
    return b;
}

哈夫曼树

定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。

路径：在一棵树中，一个结点到另一个结点之间的通路。

路径长度：在一条路径中，每经过一个结点，路径长度加1。

结点的权：给每一个结点赋予一个新的数值。

结点的带权路径长度：指的是从根节点到该结点之间路径长度与该结点的权的乘积。

内容总结

以上是互联网集市为您收集整理的树与二叉树全部内容，希望文章能够帮你解决树与二叉树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---