怎么在二叉链表中找到自己的双亲？
唯一的办法就是从树根开始遍历，匹配子节点并返回当前节点。算法如下，T为树，e为待查找节点，q为队列。
if(T)
{
InitQueue(q);
EnQueue(q,T); //树根入队列
while(!QueueEmpty(q)) //队不空
{
DeQueue(q,a);//出队，队列元素赋给a
if(a->lchild && a->lchild->data==e || a->rchild && a->rchild->data==e)//找到e
return a->data;
else
{
if(a->lchild)
EnQueue(q,a->lchild);//入队列左孩子
if(a->rchild)
EnQueue(q,a->rchild);//入队列右孩子
}
}
}
孩子兄弟表示法
树的左儿子右兄弟表示法又称为二叉树表示法或二叉链表表示法。每个结点除了data域外，还含有两个域，分别指向该结点的最左儿子和右邻兄弟。这种表示法常用二叉链表实现，因此又称为二叉链表表示法。若用指针实现，其类型定义为：
typedef
NodeType
TPosition;
struct
NodeType
ElemType
data;
TPosition
Leftmost_Child,Right_Sibling;
}
用树的左儿子右兄弟表示法可以直接实现树的大部分操作，只有在对树结点作Parent操作时需遍历树。如果要反复执行Parent操作，可在结点记录中再开辟一个指向父结点的指针域，也可以利用最右儿子单元中的Right_Sibling作为指向父结点的指针(否则这里总是空指针)。当执行Parent(v)时，可以先通过Right_Sibling逐步找出结点v的最右兄弟，再通过最右兄弟的Right_Sibling(父亲指针)找到父结点。这个结点就是结点v的父亲。在这样的表示法下，求一个结点的父亲所需要的时间正比于该结点右边的兄弟个数。不过，这时每个记录中需要多用一位(bit)空间，用以标明该记录中的right_sibling是指向右邻兄弟还是指向父亲。
考虑到对于现在的计算机，内存已经不是很重要的限制因素了。我们下面就采取增加一个parent域的方案，以改进左儿子右兄弟表示法中Parent操作的效率。因此重新定义树的类型如下：
typedef
NodeType
TPosition;
struct
NodeType
ElemType
data;
TPosition
Parent,Leftmost_Child,Right_Sibling;
//增加一个Parent域
}
如果是
二叉树，还可以用
一维数组表示，父节点i（i从1开始）
，
左孩子2i，右孩子
2i+1；
如下代码是通过算法的方式求父节点，其中二叉树的创建是先序方式，如abd##e##c##\x0d\\x0d\#include "stdlibh"\x0d\typedef int Element;\x0d\struct Tree\x0d\{ \x0d\ Element data;\x0d\ struct Tree left; \x0d\ struct Tree right;\x0d\};\x0d\\x0d\void CreateBinSortTree(struct Tree t);\x0d\void InsertNode2Tree(struct Tree root, Element num);\x0d\void PrintTree(struct Tree r, int order);\x0d\struct Tree FindParent(struct Tree r, char ch);\x0d\\x0d\int main(int argc, char argv[])\x0d\{\x0d\ printf("请输入一组字母(#表示子树为空)\n");\x0d\ struct Tree t=NULL;\x0d\ CreateBinSortTree(&t);\x0d\ printf("\n根左右:");\x0d\ PrintTree(t,1);\x0d\ printf("\n左根右:");\x0d\ PrintTree(t,2);\x0d\ printf("\n左右根:");\x0d\ PrintTree(t,3);\x0d\ printf("\n");\x0d\ char ch='a';\x0d\ getchar();//获取前次输入回车符\x0d\ printf("请输入节点数据值");\x0d\ scanf("%c",&ch);\x0d\ struct Tree temp = FindParent(t,ch);\x0d\ if (temp!=NULL)\x0d\ {\x0d\ printf("其父节点数据值为:%c",temp->data);\x0d\ }\x0d\ else\x0d\ {\x0d\ printf("找不到父节点");\x0d\ }\x0d\ return 0;\x0d\ \x0d\}\x0d\void CreateBinSortTree(struct Tree t)\x0d\{ \x0d\ char ch;\x0d\ ch = getchar(); \x0d\ if (ch == '#') \x0d\ { \x0d\ t = NULL; \x0d\ return ; \x0d\ }\x0d\ t = (struct Tree )malloc(sizeof(struct Tree)); \x0d\ (t)->data = ch;\x0d\ CreateBinSortTree( &((t)->left)); \x0d\ CreateBinSortTree( &((t)->right));\x0d\ \x0d\}\x0d\\x0d\void PrintTree(struct Tree r, int order)\x0d\{ \x0d\ if (r == NULL) \x0d\ { \x0d\ return ; \x0d\ }\x0d\ switch(order)\x0d\ { \x0d\ case 1: \x0d\ printf("%c ",r->data);\x0d\ PrintTree(r->left,order); \x0d\ PrintTree(r->right,order); \x0d\ break;\x0d\ case 2: \x0d\ PrintTree(r->left,order); \x0d\ printf("%c ",r->data); \x0d\ PrintTree(r->right,order); \x0d\ break; \x0d\ case 3: \x0d\ PrintTree(r->left,order); \x0d\ PrintTree(r->right,order); \x0d\ printf("%c ",r->data); \x0d\ break; \x0d\ }\x0d\}\x0d\\x0d\struct Tree FindParent(struct Tree r, char ch)\x0d\{\x0d\ if (r==NULL)\x0d\ {\x0d\ return NULL;\x0d\ }\x0d\ if (r->left != NULL)\x0d\ {\x0d\ if (r->left->data == ch)\x0d\ {\x0d\ return r;\x0d\ }\x0d\ }\x0d\ if (r->right != NULL)\x0d\ {\x0d\ if (r->right->data == ch)\x0d\ {\x0d\ return r;\x0d\ }\x0d\ }\x0d\ struct Tree t=FindParent(r->left,ch);\x0d\ if (t != NULL)\x0d\ {\x0d\ return t;\x0d\ }\x0d\ t = FindParent(r->right,ch);\x0d\ return t;\x0d\}
Huffman 树为正则二叉树，因此，只有度为2和度为0的结点，如果用二叉链表来存储，度为2的结点的左右孩子都存在，没有空指针，度为0的叶子没有孩子，因此左右孩子的链域都为空，因此该Huffman树一共有2m个空指针。
在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。
用普通的表示方法时，每个英文字母均占用一个字节，即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。
扩展资料：
动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树。
所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。
——哈夫曼树
以下程序已在win-tc和tc20下运行通过，已加详细注释(本人所写)。
/ 数据安全实用程序，加密解密简单程序 /
#include<stdioh>
#include<stdlibh>
#include<conioh>
int flag;
char encrypt(char ch,int key)/加密函数，把字符循环移位/
{
if(ch>='a' && ch<='z') / 如果是小写字母 /
{
ch=(ch-'a'+key%26)%26+'a'; / 字母向后移key%26个位置，超过字母z则再从a开始向后移动 /
}
else if(ch>='A' && ch<='Z') / 如果是大写字母 /
{
ch=(ch-'A'+key%26)%26+'A'; / 字母向后移key%26个位置，超过字母Z则再从A开始向后移动 /
}
return ch;
}
char decrypt(char ch,int key)/解密函数，把字符循环移位/
{
if(ch>='a' && ch<='z') / 如果是小写字母 /
{
ch=(ch-'a'+26-key%26)%26+'a'; / 字母向后移26-key%26个位置，超过字母z则再从a开始向后移动 /
}
else if(ch>='A' && ch<='Z') / 如果是大写字母 /
{
ch=(ch-'A'+26-key%26)%26+'A'; / 字母向后移26-key%26个位置，超过字母Z则再从A开始向后移动 /
}
return ch;
}
void menu()/菜单，1加密，2解密，3显示文本文件内容/
{
clrscr();
printf("\n=======================================================");
printf("\n1Encrypt the text file"); / 加密文件 /
printf("\n2Decrypt the text file"); / 解密文件 /
printf("\n3Display text file contents");/ 显示加密或解密或未加密或解密的文件 /
printf("\n4Quit\n");
printf("=========================================================\n");
printf("Please select a item:"); / 选择一个菜单 /
}
void logo()/显示程序信息/
{
printf("\nwelcome to encrypt program \n ");
return;
}
void encrypt_decrypt_File(char infile,int key, char outfile) / 加密或解密函数 /
{
FILE in,out;
char ch;
clrscr(); / 清屏 /
if((in=fopen(infile,"r"))==NULL) / 打开欲加密或解密的文件/
{
printf("Can not open the infile!\n"); / 如果打开文件失败或文件不存在打印打开失败信息 /
printf("Press any key to exit!\n");
getch(); / 并等待任一按键然后退出程序 /
exit(0);
}
if((out=fopen(outfile,"w"))==NULL) / 打开文件保存加密或解密后的内容/
{
printf("Can not open the outfile!\n"); / 如果打开文件失败或文件不存在打印打开失败信息 /
printf("Press any key to exit!\n"); / 并等待任一按键然后退出程序 /
fclose(in); / 关闭输入文件 /
getch(); / 等待按键，按任一键退出程序 /
exit(0);
}
ch=fgetc(in); /从文本文件中读入字符/
while(ch!=EOF)/加密或解密/
{
/如果是英文字符，则进行加密或解密，否则，不进行加密或解密处理/
if((ch>='a' && ch<='z' ) || (ch>='A' && ch<='Z'))
{ if(flag==1)
fputc(encrypt(ch,key),out);
if(flag==2)
fputc(decrypt(ch,key),out);
}
else
fputc(ch,out);
ch=fgetc(in);
}
/关闭输入及输出文件/
fclose(in);
fclose(out);
}
void displayFile(char infile) /将文本文件的内容显示在屏幕上/
{
FILE fp;
char string[81];
if((fp=fopen(infile,"r"))==NULL) / 以只读方式打开文本文件 /
{
printf("cann't open file");exit(0); / 如果文件不存在或打开失败打印无法打开信息并退出程序 /
}
while(fgets(string,81,fp)!=NULL)
fputs(string,stdout); /把所取字符串送到屏幕显示/
fclose(fp); / 关闭文件 /
}
int main()
{
int i,n;
char ch0,ch1;
char infile[40],outfile[40];
textbackground(LIGHTGRAY); /设置背景颜色为浅灰色/
textcolor(BLACK); /设置文字颜色为黑色/
clrscr();/清除屏幕显示/
logo(); /显示程序信息/
sleep(2); / 延时2秒 /
menu(); /显示屏幕菜单/
ch0=getche();/等待用户从键盘输入，并把输入显示在屏幕上/
while(ch0!='4')
{
clrscr();
if(ch0=='1') /选择加密功能/
{
flag=1;
printf("\nPlease input the infile to be encrypted:"); / 输入要加密的文件名 /
scanf("%s",infile); / 该文件要和本程序放在同一个目录下 /
printf("Please input the encrypt key:");
scanf("%d",&n);/输入加密密码/
printf("Please input the outfile:"); /输入存放加密内容的文件名/
scanf("%s",outfile); / 该文件可以自动创建 /
encrypt_decrypt_File(infile,n,outfile);
printf("\nEncrypt is over!\n");/ 加密成功 /
sleep(1); / 延时1秒 /
}
else if(ch0=='2') /选择解密功能/
{
flag=2;
printf("\nPlease input the infile to be decrypted:"); / 输入要解密的文件名 /
scanf("%s",infile); / 该文件要和本程序放在同一个目录下 /
printf("Please input the decrypt key:");
scanf("%d",&n);/输入解密密码，加密和解密密码应相同/
printf("Please input the outfile:"); /输入存放解密内容的文件名/
scanf("%s",outfile); / 该文件可以自动创建 /
encrypt_decrypt_File(infile,n,outfile);
printf("\nDecrypt is over!\n");
sleep(1); / 延时1秒 /
}
else if(ch0=='3') /选择显示文本文件功能/
{
printf("\nPlease input the infile to be displayed:"); / 输入要显示的文件名 /
scanf("%s",infile);
displayFile(infile);/ 显示文件 /
getch();
}
else
{ /不合法输入/
printf("\nplease input a valid number(1-4)\n");
sleep(1); / 延时1秒 /
}
menu();/显示程序菜单/
ch0=getche(); /等待用户下一次的功能选择/
}
system("cls");/清除屏幕/
logo(); /显示程序信息/
printf("\nGood Bye!\n");
sleep(2);/ 延时2秒 /
system("pause"); / 暂停，按任一键退出程序 /
return 0;
}
怎么在二叉链表中找到自己的双亲？
本文2023-11-11 04:36:28发表“资讯”栏目。
本文链接：https://www.lezaizhuan.com/article/455273.html
相关文章
