树和二叉树的建立及应用
一个单位有10个部门，每个部门都有一部电话，但是整个单位只有一根外线，当有电话打过来的时候，由转接员转到内线电话，已知各部门使用外线电话的频率为（次/天）
5 20 10 12 8 4 3 5 6 9
问应该如何设计个内线电话号码，使得接线员拨号次数尽可能少？
这是哈夫曼树的应用。
一种数据结构，用于保存和处理树状的数据，如家谱。
应用极为广泛，因为根据数据结构的理论，任何复杂的树够可以转换为二叉中并进行处理。
二叉树再排序、查找、大规模数据索引方面有很多很多应用。
二叉树排序是简单算法排序中速度最快的。
树的一个大类是自平衡二叉搜索树 (self-balanced BST), 变种特别多:RB 树是每个节点是红色或者黑色, 颜色隔代遗传AVL 树是每个节点包含平衡因子, 等于左高-右高Splay 树是每个节点带个父节点的指针Treap 是每个节点都带个随机的 priority number, parent priority >= child priority。
自平衡二叉搜索树在面试中经常出现, 但做网页的互联网码农却很少用得上，如果是当 Map 用, 往往还不如直接上哈希表. 如果是当排序用, 不如直接用排序算法... 不过也有有用的时候, 例如查找一个数字的上下界。
树的另一个大类是 Trie, 特点是能保证字典序, 存储词典的空间压缩率高, 能做前缀搜索. 在正则匹配, 数据压缩, 构建索引都可能用到. Trie 也有不少变种:Double Array - trie 的一个经典实现。
每个节点可以存一段字符串而不限于一个字符Judy Array - 基于 256-ary radix tree, 用了 20 种压缩方式, 极其复杂...Burst Trie - 如果一个子树足够小, 就用 binary 堆的方式存储,。
不过压缩效果一般HAT Trie - 压缩率高而且不容易出现 CPU cache miss, 查速接近哈希表而耗内存少得多. 节点可以是以下三种之一: Array Hash, 序列化的 Bucket, 传统 Trie nodeMARISA Trie - 压缩率最高, 支持 mmap 载入, 也是用了很多压缩技巧的复杂实现, 就是构建比较花时间, 也不能动态更新。
楼主你好
具体代码如下：
#include
#include
#define MAX 40
typedef struct node//二叉树结点定义
{
char data;
struct node *lChild;//左孩子
struct node *rChild;//右孩子
}BTNode;
//*************************************二叉树操作***************************************
void Initial_BT(BTNode * &b)
{
b=NULL;
}
void Creat_BT(BTNode * &b)//创建二叉树
{
BTNode *St[MAX];//用栈辅助实现二叉树的建立
BTNode *p=NULL;
b=NULL;
int top=-1;//栈指针
int k;//k为左右孩子标示(1为左孩子、2为右孩子)
char ch;
printf("Enter the binary tree:
");
ch=getchar();
while(ch!='
')
{
switch(ch)
{
case '('://左孩子
top++;
St[top]=p;
k=1;
break;
case ')':
top--;
break;
case ','://右孩子
k=2;
break;
default:
p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;
p->lChild=p->rChild=NULL;
if(!b)//如果为根节点
b=p;
else
{
switch(k)
{
case 1:
St[top]->lChild=p;
break;
case 2:
St[top]->rChild=p;
break;
}
}
}
ch=getchar();//继续读入数据
}
}
void InOrder(BTNode *b)//中序遍历
{
if(b)
{
InOrder(b->lChild);
printf("%c",b->data);
InOrder(b->rChild);
}
}
void PostOrder(BTNode *b)//后序遍历
{
if(b)
{
PostOrder(b->lChild);
PostOrder(b->rChild);
printf("%c",b->data);
}
}
int Leaf_Sum(BTNode *b)
{
if(!b)
return 0;
else if(b->lChild == NULL && b->rChild == NULL)
return 1;
else
return Leaf_Sum(b->lChild)+Leaf_Sum(b->rChild);
}
void Start()
{
BTNode *b;//二叉树
char choice;
b=(BTNode *)malloc(sizeof(BTNode));
Initial_BT(b);
GOTO:system("cls");
printf("1.创建二叉树.
"
"2.中序遍历.
"
"3.后序遍历.
"
"4.叶子结点个数.
"
"5.退出.
");
printf("输入你的选择:");
GOTO1:choice=getchar();
switch(choice)
{
case '1':
getchar();
Creat_BT(b);
system("pause");
goto GOTO;
case '2':
InOrder(b);
printf("
");
system("pause");
getchar();
goto GOTO;
case '3':
PostOrder(b);
printf("
");
system("pause");
getchar();
goto GOTO;
case '4':
printf("共有%d个叶子结点
",Leaf_Sum(b));
system("pause");
getchar();
goto GOTO;
case '5':
system("pause");
break;
default:
printf("输入错误!
"
"重新输入:");
goto GOTO1;
}
}
int main()
{
Start();
return 0;
}
希望能帮助你哈
#include "stdio.h"
#include "string.h"
#define NULL 0
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree Create(BiTree T){
char ch;
ch=getchar();
if(ch=='#')
T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
printf("Error!");
T->data=ch;
T->lchild=Create(T->lchild);
T->rchild=Create(T->rchild);
}
return T;
}
void Preorder(BiTree T){
if(T){
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
int Sumleaf(BiTree T){
int sum=0,m,n;
if(T){
if((!T->lchild)&&(!T->rchild))
sum++;
m=Sumleaf(T->lchild);
sum+=m;
n=Sumleaf(T->rchild);
sum+=n;
}
return sum;
}
void zhongxu(BiTree T){
if(T){
zhongxu(T->lchild);
printf("%c",T->data);
zhongxu(T->rchild);
}
}
void houxu(BiTree T){
if(T){
houxu(T->lchild);
houxu(T->rchild);
printf("%c",T->data);
}
}
int Depth(BiTree T){
int dep=0,depl,depr;
if(!T) dep=0;
else{
depl=Depth(T->lchild);
depr=Depth(T->rchild);
dep=1+(depl>depr?depl:depr);
}
return dep;
}
main(){
BiTree T;
int sum,dep;
T=Create(T);
Preorder(T);
printf("\n");
zhongxu(T);
printf("\n");
houxu(T);
printf("\n");
sum=Sumleaf(T);
printf("%d",sum);
dep=Depth(T);
printf("\n%d",dep);
}
树和二叉树的运行与操作
答：分为几个步骤：（1）准备原始数组 （2）分析数组中的有效值，对应二叉树节点非空；（3）创建二叉树节点；（4）计算除最后一层子节点外，构造节点间父子关系时的循环次数；（5）构造二叉树节点间的父子关系；（6）确实二叉树根节点；
数据结构树和二叉树的实际应用
答：数据结构树和二叉树的实际应用：哈夫曼编码。利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求...
树和二叉树的建立及应用
答：以下是我的数据结构实验的作业：肯定好用，里面还包括了统计树的深度和叶子数！记住每次做完一个遍历还要重新输入你的树哦！include "stdio.h"include "string.h"define NULL 0 typedef struct BiTNode{ char data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;BiTree Create(BiTree T){ char c...
树和二叉树
答：对于 完全二叉树 采用此方法，则：对于 一般二叉树 采用此方法，首先需要用某种方法将其转换成完全二叉树，为此可增设若干个 虚拟结点 ，则：遍历二叉树 ：是指按 某种次序访问 二叉树上的所有结点，使每个结点被 访问一次 且仅被访问一次。先序遍历，DLR ：根 -> 左子树 -> 右子树...
二叉树算法有哪些应用场景?
答：二叉树常被用于实现二叉查找树和二叉堆。在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。根据不同的用途可分为：1、完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且...
请问C语言如何创建二叉树???
答：创建二叉树的源程序如下：include <cstdlib> include <stdio.h> typedef struct node { //树的结点 int data;struct node* left;struct node* right;} Node;typedef struct { //树根 Node* root；} Tree;void insert(Tree* tree, int value)//创建树 { Node* node=(Node*)malloc(sizeof(...
二叉树的建立及其遍历算法的应用问题描述
答：BTree *bt;int count=0;InitBTree(&bt,node); /*用初始串构造一个顺序存储的二叉树*/ printf("先序遍历:\n\t");PreorderTraverse(bt,1);printf("\n");Leaf(bt,&count);printf("\nThe number of leaves is %d\n",count);getch();} 我的编辑环境是win-TC ，但愿能对你有帮助。
数据结构教程第二十一课树、二叉树定义及术语
答：教学目的： 掌握树、二叉树的基本概念和术语，二叉树的性质 教学重点： 二叉树的定义、二叉树的性质 教学难点： 二叉树的性质 授课内容：一、树的定义：树是n(n>=0)个结点的有限集。在任意一棵非空树中：(1)有且仅有一个特定的称为根的结点；(2)当n>1时,其余结点可分为m(m>0)个互不...
二叉树是什么?
答：二叉树的基本操作：(1)INITIATE(BT ） 初始化操作。置 BT为空树。(2)ROOT(BT)\ROOT(x) 求根函数。求二叉树 BT的根结点或求结点 x所在二叉树的根结点。若 BT是空树或 x不在任何二叉树上，则函数值为 “空 ”。(3)PARENT(BT,x) 求双亲函数。求二叉树 BT中结点 x的双亲结点。若结点 x...
树和二叉树的基本知识?
答：二叉树在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层...
