/实验14—2 设计一个程序，采用二叉树表示一个家谱关系。要求程序具有如下功能：

（1） 文件操作功能：记录输入、记录输出，清除全部文件记录和将家谱记录存盘。

（2） 家谱操作功能：用括号表示法输出家谱二叉树，查找某人所有的儿子，查找某人所有的祖先。/

#include<iostreamh>

#include<stdlibh>

#include<stdioh>

#include<stringh>

typedef struct Node

{

int degree;//人员所在代数

char data;//人员标志

struct Node lchild;//data的孩子

struct Node rchild;//data的兄弟

}BTNode;

#define max 100

int choose;

char X;

void CreatBTNode(BTNode b,char str);//创建记录

BTNode SearchX(BTNode b,char X);//查找记录

void InputBTNode(BTNode b,char str);//1记录输入

void OutputBTNode(BTNode b,char str);//2记录输出

void Store(BTNode b,char str);//3家谱记录存盘

void DispTree(BTNode b);//4用括号法输出家谱

void SearchXSon(BTNode b,char X);//5查找某人的儿子

void SearchXAncestor(BTNode b,char X);//6查找某人的祖先

void Distory(BTNode b,char str);//7清除全部文件记录

int main()

{BTNode b=NULL;

char str=(char)malloc(maxsizeof(char));

str[0]='\0';

cout<<"--------------------------------------------------------------------"<<endl;

cout<<"0退出"<<endl;

cout<<"1记录输入:\t"<<endl;

cout<<"2记录输出:\t"<<endl;

cout<<"3家谱记录存盘:\t"<<endl;

cout<<"4用括号法输出家谱:\t"<<endl;

cout<<"5查找某人的儿子:\t"<<endl;

cout<<"6查找某人的祖先:\t"<<endl;

cout<<"7清除全部文件记录:\n"<<endl;

cout<<"-------------------------------------------------------------------"<<endl;

cout<<"Please choose the operation you want to do "<<endl;

cout<<"choose=";

cin>>choose;

while(choose)

{switch(choose)

{

case 1:

InputBTNode(&b,str);break;

case 2:

OutputBTNode(&b,str);break;

case 3:

Store(b,str);

printf("文件已经保存!");

break;

case 4:

DispTree(b); break;

case 5:

printf("请输入需要查找儿子的结点:");

cin>>X;

SearchXSon(b,X);

break;

case 6:

printf("请输入需要查找祖先的结点:\n");

cin>>X;

BTNode p;

p=SearchX(b,X);

if(p!=NULL)

SearchXAncestor(b,X);

else

printf("该结点不存在!");

break;

case 7:

Distory(&b,str);

printf("文件记录已经清除!");

break;

default:

cout<<endl<<"Invalid input,input again";

}

cout<<endl<<"please choose again:"<<endl;

cout<<"the choose =";

cin>>choose;

}

return 0;

}

void CreatBTNode(BTNode b,char str) //创建树

{

BTNode S[max],p=NULL;

int top=-1,tag,j=0,d=0;

char ch;

b=NULL;

ch=str[j];

while(ch!='\0')

{

switch(ch)

{

case '(':

d++;

top++;

S[top]=p;

tag=1;break;

case ')':

top--;break;

case ',':

d--;

tag=2;break;

default:

p=(BTNode )malloc(sizeof(BTNode));

p->degree=d;

p->data=ch;

p->lchild=NULL;

p->rchild=NULL;

if((b)==NULL)(b)=p;

else

{

switch(tag)

{

case 1: S[top]->lchild=p;break;

case 2: S[top]->rchild=p;break;

}

}

}

ch=str[++j];

}

}

void InputBTNode(BTNode b,char str)//记录输入

{

do

{

printf("请输入需要输入的记录:\n");

gets(str);

if(str[0]=='\0')

printf("输入的记录为空，请再次输入:\n");

}while(str[0]=='\0');

CreatBTNode(b,str);

printf("记录创建成功!");

}

void OutputBTNode(BTNode b,char str)//从文件中读出记录

{

FILE fp;

if((fp=fopen("wangljtxt","r"))==NULL)

{

printf("不存在记录文件,要建立吗\n建立请输入Y，否则按其他键：");

if(getchar()=='Y')

{

fp=fopen("wangljtxt","w+");

printf("记录文件“wangljtxt”已建立\n");

}

else

exit(1);

}

else

{

if(!feof(fp))

fscanf(fp,"%s",str);

fclose(fp);

CreatBTNode(b,str);

printf("文件中记录已输出\n");

}

}

void Store(BTNode b,char str)//储存全部的结点记录

{

BTNode p;

p=b;

FILE fp;

fp=fopen("wangljtxt","w+");

if(fp==NULL)

{

printf("文件打开失败!");

return;

}

else

{

if(p!=NULL)

{

fprintf(fp,"%s",str);

fclose(fp);

}

}

}

void DispTree(BTNode b)//用括号法输出家谱记录

{

if(b!=NULL)

{printf("%c",b->data);

if(b->lchild!=NULL||b->rchild!=NULL)

{printf("(");

DispTree(b->lchild);

if(b->rchild!=NULL)

{printf(",");

DispTree(b->rchild);

}

printf(")");

}

}

else

printf("\0");

}

BTNode SearchX(BTNode b,char X)//查找结点X

{BTNode p;

if(b==NULL) return NULL;

else if(b->data==X) return b;

else

{

p=SearchX(b->lchild,X);

if(p!=NULL) return p;

else

{

return SearchX(b->rchild,X);

}

}

}

void SearchXSon(BTNode b,char X)//查找结点X的所有儿子

{

BTNode p,q;

p=SearchX(b,X); //找到节点X

if(p!=NULL)

{

p=p->lchild;

if(p==NULL) //X没有孩子

printf("节点%c没有儿子!",X);

else

{

printf("节点%c的所有儿子为:",X);

if(p!=NULL)

printf("%c ",p->data);

q=p->rchild;

while(q)

{

printf("%c ",q->data);

q=q->rchild;

}

}

}

else

printf("该结点不存在!");

}

void TraverseBT(BTNode b,int d)//遍历家谱

{

if(b!=NULL)

if(b->degree<d)

{

printf("%c ",b->data);

if(b->lchild!=NULL)

TraverseBT(b->lchild,d);

if(b->rchild!=NULL)

TraverseBT(b->rchild,d);

}

}

void SearchXAncestor(BTNode b,char X)//查找结点X的所有祖先

{

if(b==NULL)

{

printf("这是一棵空树!");

return ;

}

BTNode p=SearchX(b,X);

if(p->degree==0)

{

printf("X为根节点或其兄弟，没有祖先!");

return;

}

printf("%c结点的祖先有：",X);

TraverseBT(b,p->degree);

}

void Distory(BTNode b,char str)//清除全部的记录

{

(b)=NULL;

FILE fp;

fp=fopen("wangljtxt","w");

if(fp==NULL)

{

printf("打开文件失败!");

exit(1);

}

str="";

fclose(fp);

}

你懂的，同道中人！

首先确定点到点的向量范围

然后做枝叶的随机，将最终节点设置为LEAF

我只给出结构，剩下的LZ自己来吧

function Node(){

thisnodeCount=0;子节点数量

thisisLeaf=false;

thisLChild=[];左枝叶

thisRChild=[];右枝叶

}

结构请按照二叉树的生成来

数组是最简单也是最常见的数据结构。它们的特点是可以通过索引（位置）轻松访问元素。

它们是做什么用的？

想象一下有一排剧院椅。每把椅子都分配了一个位置（从左到右），因此每个观众都会从他将要坐的椅子上分配一个号码。这是一个数组。将问题扩展到整个剧院（椅子的行和列），您将拥有一个二维数组（矩阵）。

特性

链表是线性数据结构，就像数组一样。链表和数组的主要区别在于链表的元素不存储在连续的内存位置。它由节点组成——实体存储当前元素的值和下一个元素的地址引用。这样，元素通过指针链接。

它们是做什么用的？

链表的一个相关应用是浏览器的上一页和下一页的实现。双链表是存储用户搜索显示的页面的完美数据结构。

特性

堆栈是一种抽象数据类型，它形式化了受限访问集合的概念。该限制遵循 LIFO（后进先出）规则。因此，添加到堆栈中的最后一个元素是您从中删除的第一个元素。

堆栈可以使用数组或链表来实现。

它们是做什么用的？

现实生活中最常见的例子是在食堂中将盘子叠放在一起。位于顶部的板首先被移除。放置在最底部的盘子是在堆栈中保留时间最长的盘子。

堆栈最有用的一种情况是您需要获取给定元素的相反顺序。只需将它们全部推入堆栈，然后弹出它们。

另一个有趣的应用是有效括号问题。给定一串括号，您可以使用堆栈检查它们是否匹配。

特性

队列是受限访问集合中的另一种数据类型，就像前面讨论的堆栈一样。主要区别在于队列是按照FIFO（先进先出）模型组织的：队列中第一个插入的元素是第一个被移除的元素。队列可以使用固定长度的数组、循环数组或链表来实现。

它们是做什么用的？

这种抽象数据类型 (ADT) 的最佳用途当然是模拟现实生活中的队列。例如，在呼叫中心应用程序中，队列用于保存等待从顾问那里获得帮助的客户——这些客户应该按照他们呼叫的顺序获得帮助。

一种特殊且非常重要的队列类型是优先级队列。元素根据与它们关联的“优先级”被引入队列：具有最高优先级的元素首先被引入队列。这个 ADT 在许多图算法（Dijkstra 算法、BFS、Prim 算法、霍夫曼编码 ）中是必不可少的。它是使用堆实现的。

另一种特殊类型的队列是deque 队列（双关语它的发音是“deck”）。可以从队列的两端插入/删除元素。

特性

Maps （dictionaries）是包含键集合和值集合的抽象数据类型。每个键都有一个与之关联的值。

哈希表是一种特殊类型的映射。它使用散列函数生成一个散列码，放入一个桶或槽数组：键被散列，结果散列指示值的存储位置。

最常见的散列函数（在众多散列函数中）是模常数函数。例如，如果常量是 6，则键 x 的值是x%6。

理想情况下，散列函数会将每个键分配给一个唯一的桶，但他们的大多数设计都采用了不完善的函数，这可能会导致具有相同生成值的键之间发生冲突。这种碰撞总是以某种方式适应的。

它们是做什么用的？

Maps 最著名的应用是语言词典。语言中的每个词都为其指定了定义。它是使用有序映射实现的（其键按字母顺序排列）。

通讯录也是一张Map。每个名字都有一个分配给它的电话号码。

另一个有用的应用是值的标准化。假设我们要为一天中的每一分钟（24 小时 = 1440 分钟）分配一个从 0 到 1439 的索引。哈希函数将为h(x) = x小时60+x分钟。

特性

术语：

因为maps 是使用自平衡红黑树实现的（文章后面会解释），所以所有操作都在 O(log n) 内完成；所有哈希表操作都是常量。

图是表示一对两个集合的非线性数据结构：G={V, E}，其中 V 是顶点（节点）的集合，而 E 是边（箭头）的集合。节点是由边互连的值 - 描述两个节点之间的依赖关系（有时与成本/距离相关联）的线。

图有两种主要类型：有向图和无向图。在无向图中，边(x, y)在两个方向上都可用：(x, y)和(y, x)。在有向图中，边(x, y)称为箭头，方向由其名称中顶点的顺序给出：箭头(x, y)与箭头(y, x) 不同。

它们是做什么用的？

特性

图论是一个广阔的领域，但我们将重点介绍一些最知名的概念：

一棵树是一个无向图，在连通性方面最小（如果我们消除一条边，图将不再连接）和在无环方面最大（如果我们添加一条边，图将不再是无环的）。所以任何无环连通无向图都是一棵树，但为了简单起见，我们将有根树称为树。

根是一个固定节点，它确定树中边的方向，所以这就是一切“开始”的地方。叶子是树的终端节点——这就是一切“结束”的地方。

一个顶点的孩子是它下面的事件顶点。一个顶点可以有多个子节点。一个顶点的父节点是它上面的事件顶点——它是唯一的。

它们是做什么用的？

我们在任何需要描绘层次结构的时候都使用树。我们自己的家谱树就是一个完美的例子。你最古老的祖先是树的根。最年轻的一代代表叶子的集合。

树也可以代表你工作的公司中的上下级关系。这样您就可以找出谁是您的上级以及您应该管理谁。

特性

二叉树是一种特殊类型的树：每个顶点最多可以有两个子节点。在严格二叉树中，除了叶子之外，每个节点都有两个孩子。具有 n 层的完整二叉树具有所有2ⁿ-1 个可能的节点。

二叉搜索树是一棵二叉树，其中节点的值属于一个完全有序的集合——任何任意选择的节点的值都大于左子树中的所有值，而小于右子树中的所有值。

它们是做什么用的？

BT 的一项重要应用是逻辑表达式的表示和评估。每个表达式都可以分解为变量/常量和运算符。这种表达式书写方法称为逆波兰表示法 (RPN)。这样，它们就可以形成一个二叉树，其中内部节点是运算符，叶子是变量/常量——它被称为抽象语法树（AST）。

BST 经常使用，因为它们可以快速搜索键属性。AVL 树、红黑树、有序集和映射是使用 BST 实现的。

特性

BST 有三种类型的 DFS 遍历：

所有这些类型的树都是自平衡二叉搜索树。不同之处在于它们以对数时间平衡高度的方式。

AVL 树在每次插入/删除后都是自平衡的，因为节点的左子树和右子树的高度之间的模块差异最大为 1。 AVL 以其发明者的名字命名：Adelson-Velsky 和 Landis。

在红黑树中，每个节点存储一个额外的代表颜色的位，用于确保每次插入/删除操作后的平衡。

在 Splay 树中，最近访问的节点可以快速再次访问，因此任何操作的摊销时间复杂度仍然是 O(log n)。

它们是做什么用的？

AVL 似乎是数据库理论中最好的数据结构。

RBT（红黑树） 用于组织可比较的数据片段，例如文本片段或数字。在 Java 8 版本中，HashMap 是使用 RBT 实现的。计算几何和函数式编程中的数据结构也是用 RBT 构建的。

在 Windows NT 中（在虚拟内存、网络和文件系统代码中），Splay 树用于缓存、内存分配器、垃圾收集器、数据压缩、绳索（替换用于长文本字符串的字符串）。

特性

最小堆是一棵二叉树，其中每个节点的值都大于或等于其父节点的值：val[par[x]]