数据结构(八)

Myth丶恋晨 2022-08-20 10:10 251阅读 0赞

接着二叉树：

已知中序和先序，中序和后序求原始二叉树：先从先序和后序开始找根结点，再定位到中序找出根结点的左子树和右子树，再依次递归找出各位非终端结点。

示例1

先序：ABCDEFGH

中序：BDCEAFHG

求后序：DECBHGFA

示例2

先序：ABDGHCEFI

中序：GDHBAECIF

求后序：GHDBEIFCA

示例3

中序：BDCEAFHG

后序：DECBHGFA

求先序：ABCDEFGH

树的应用：

树是数据库数据组织的一种重要形式

操作系统子父进程的关系本身就是一棵树:

![Center][]

面向对象语言中类的继承关系本身就是一棵树

赫夫曼树

下面是二叉树遍历的算法：

#include<stdio.h>
    #include<malloc.h>
    
    struct BTNode
    {
    	char data;
    	struct BTNode * pLchild;
    	struct BTNode * pRchild;
    };
    
    struct BTNode * CreateBTree(void);
    void preTraverse(struct BTNode * pA);
    void middleTraverse(struct BTNode *pA);
    void afterTraverse(struct BTNode *pA);
    
    int main()
    {
    	struct BTNode * pT = CreateBTree();
    	printf("\n*******先序*******\n");
    	preTraverse(pT);
    	printf("\n********中序******\n");
    	middleTraverse(pT);
    	printf("\n*******后序*******\n");
    	afterTraverse(pT);
    	return 0;
    }
    
    struct BTNode * CreateBTree(void)
    {
    	struct BTNode * pA=(struct BTNode *)malloc(sizeof(struct BTNode));
    	struct BTNode * pB=(struct BTNode *)malloc(sizeof(struct BTNode));
    	struct BTNode * pC=(struct BTNode *)malloc(sizeof(struct BTNode));
    	struct BTNode * pD=(struct BTNode *)malloc(sizeof(struct BTNode));
    	struct BTNode * pE=(struct BTNode *)malloc(sizeof(struct BTNode));
    	pA->data='A';
    	pB->data='B';
    	pC->data='C';
    	pD->data='D';
    	pE->data='E';
    	pA->pLchild=pB;
    	pA->pRchild=pC;
    	pB->pLchild=pB->pRchild=NULL;
    	pC->pLchild=pD;
    	pC->pRchild=NULL;
    	pD->pLchild=NULL;
    	pD->pRchild=pE;
    	pE->pLchild=pE->pRchild=NULL;
    	return pA;
    }
    
    void preTraverse(struct BTNode *pA)
    {
    	if(pA!=NULL)
    	{
    		printf(" %c   ",pA->data);
    			if(pA->pLchild!=NULL)
    			{
    				preTraverse(pA->pLchild);
    			}
    			if(pA->pRchild!=NULL)
    			{
    				preTraverse(pA->pRchild);
    			}
    	}
    }
    void middleTraverse(struct BTNode *pA)
    {
    	if(pA!=NULL)
    	{
    			if(pA->pLchild!=NULL)
    			{
    				preTraverse(pA->pLchild);
    				printf(" %c   ",pA->data);
    			}
    			if(pA->pRchild!=NULL)
    			{
    				preTraverse(pA->pRchild);
    			}
    	}
    }
    void afterTraverse(struct BTNode *pA)
    {
    	if(pA!=NULL)
    	{
    			if(pA->pLchild!=NULL)
    			{
    				preTraverse(pA->pLchild);
    			}
    			if(pA->pRchild!=NULL)
    			{
    				preTraverse(pA->pRchild);
    				printf(" %c   ",pA->data);
    			}
    	}
    }

![Center 1][]

排序算法：排序有很多种，下面介绍快速排序，思路是递归：

#include<stdio.h>
    
    void sort(int * a,int low,int high);
    int findpos(int * a,int low,int high);
    
    int main()
    {
    	int a[6]={12,4,3,1,7,4};
    	int i;
    	sort(a,0,6);
    	for(i=0;i<6;i++)
    	{
    		printf("%d   ",a[i]);
    	}
    	printf("\n");
    	return 0;
    }
    
    void sort(int * a,int low,int high)
    {
    	int pos;
    	if(low<high)
    	{
    		pos=findpos(a,low,high);
    		sort(a,low,pos-1);
    		sort(a,pos+1,high);
    	}
    }
    
    int findpos(int *a,int low,int high)
    {
    	int val=a[low];
    	while(low<high)
    	{
    		
    		while(low<high&&a[high]>=val)
    		{
    			--high;
    		}
    		a[low]=a[high];
    		while(low<high&&a[low]<=val)
    		{
                ++low;
    		}
    		a[high]=a[low];
    	}
    	a[low]=val;
    	return low;
    }

![Center 2][]

再次讨论数据结构：

数据结构是研究数据的存储和数据的操作的一门学问

数据的存储分两部分：

个体的存储

个体关系的存储

从某个角度而言，数据的存储最核心的是个体关系的存储，个体的存储可以忽略不计。

再次讨论什么是泛型

同一种逻辑结构，无论该逻辑结构物理存储是什么样子的，我们可以对它执行相同的操作。

[Center]: /images/20220731/3c6a9d64566d4171af8d8cd76754e540.png
[Center 1]: /images/20220731/2c599f4b6b4347e999034762051f38c8.png
[Center 2]: /images/20220731/a6f5c8f48b5348e198a5b53144649265.png