C语言实现二叉查找树的输出

浅浅的花香味﹌ 2022-06-03 02:22 280阅读 0赞

二叉树是数据结构和算法中的重要部分。本文将简单介绍其中的一类——二叉查找树：

二叉排序树（BinarySortTree），又称二叉查找树、二叉搜索树。它或者是一棵空树；或者是具有下列性质的[二叉树][Link 1]：若左子树不空，则左子树上所有结点的值均小于它的根结点的值；若右子树不空，则右子树上所有结点的值均大于它的根结点的值；左、右子树也分别为二叉排序树。若子树为空，查找不成功。

二叉查找树的输出方式也有多种，本文简单介绍二叉查找树的前序、中序和后序输出以及按层输出，具体代码实现如下：

**前序、中序和后序输出可以利用递归方法实现：**

前序输出代码实现：

//前序遍历二叉树输出
    #include<stdio.h>
    #include<stdlib.h>
    //创建二叉树结构体 
    typedef struct node{
    	int data;
    	struct node *left,*right;
    }BTNode;
    //创建二叉树 
    BTNode *CreateBTree(int a[],int n)
    {
    	BTNode *root,*c,*p,*pa;
    	root=(BTNode*)malloc(sizeof(BTNode));      //创建根结点 
    	root->data=a[0];
    	root->left=root->right=NULL;
    //	创建其他结点 
    	for(int i=1;i<n;i++){
    		p=(BTNode*)malloc(sizeof(BTNode));
    		p->data=a[i];
    		p->left=p->right=NULL;
    		c=root;
    		while(c){
    			pa=c;
    			if(c->data>p->data)   c=c->left;
    			else                  c=c->right;
    		}
    		if(pa->data>p->data)      pa->left=p;
    		else                      pa->right=p;
    	}
    	return root;
     } 
    // 输出二叉树 
     void Forder(BTNode *root)
     {
     	if(root){
    // 		前序遍历输出 
     		printf("%5d",root->data);
     	    Forder(root->left);
     	    Forder(root->right);
    	 }
    	 else  return;
     }
     int main(void)
     {
     	int a[9]={6,2,3,7,4,8,5,9,1};
     	BTNode *root;    //创建根结点 
     	root=CreateBTree(a,9);
     	Forder(root);//前序输出二叉树 
     	return 0;
     }

中序输出代码实现（可得到递增序列）：

//中序遍历二叉树输出 
    #include<stdio.h>
    #include<stdlib.h>
    #define N  9
    typedef struct node{
    	int data;
    	struct node *left, *right;
    }BTNode;
    BTNode*CreateBTree(int a[],int n)
    {
    	BTNode* root,*c,*pa,*p;
    //	创建根结点 
    	root=(BTNode*)malloc(sizeof(BTNode));
    	root->data=a[0];
    	root->left=root->right=NULL;
    //	创建其他结点
        for(int i=1;i<n;i++)
    	{
    		p=(BTNode*)malloc(sizeof(BTNode));
    		p->data=a[i];
    		p->left=p->right=NULL;
    		c=root;
    		while(c){
    			pa=c;
    			if(c->data>p->data)   c=c->left;
    			else                  c=c->right;
    		}
    		if(pa->data>p->data)  pa->left=p;
    		else                  pa->right=p; 
    	 } 
    	 	return root;
    }
    //利用中序遍历输出
    void Inorder(BTNode *root)
    {	
     if(!root)    return;
     else{ 
     	Inorder(root->left);
     	printf("%5d",root->data);
     	Inorder(root->right);
     }
     }
     int main(void)
     {
     	int a[9]={6,2,3,7,4,8,5,9,1};
     	BTNode *root;
    // 	创建搜索二叉树
        root=CreateBTree(a,9);
    //	中序遍历
       Inorder(root);
       return 0; 
      }

后序输出代码实现：

//后序遍历二叉树输出
    #include<stdio.h>
    #include<stdlib.h>
    //创建二叉树结构体 
    typedef struct node{
    	int data;
    	struct node *left,*right;
    }BTNode;
    //创建二叉树 
    BTNode *CreateBTree(int a[],int n)
    {
    	BTNode *p,*c,*pa,*root;
    	root=(BTNode*)malloc(sizeof(BTNode));   //创建根结点 
    	root->data=a[0];
    	root->left=root->right=NULL;
    //	创建其他结点 
    	for(int i=1;i<n;i++){
    		p=(BTNode*)malloc(sizeof(BTNode));
    		p->data=a[i];
    		p->left=p->right=NULL;
    		c=root;
    		while(c){
    			pa=c;
    			if(c->data>p->data)   c=c->left;
    			else                  c=c->right;
    		}
    		if(pa->data>p->data)      pa->left=p;
    		else                      pa->right=p;
    	}
    	return root;
     } 
    // 后序输出二叉树 
     void Porder(BTNode*root)
     {
     	if(root){
     	Porder(root->left);
    	Porder(root->right);
    	printf("%5d",root->data);	
    	 }
    	 else return;
     }
     int main(void)
     {
     	int a[9]={6,2,3,7,4,8,5,9,1};
     	BTNode *root;
    // 	创建根结点 
     	root=CreateBTree(a,9);
    // 	后序输出二叉树 
     	Porder(root);
     	return 0;
     }

由于按层输出没有办法利用递归实现，所以我们采取非递归方法实现按层输出。

按层输出代码实现：

//按层输出二叉树 
    #include<stdio.h>
    #include<stdlib.h>
    #define size 100 
    //创建二叉树结构体 
    typedef struct node{
    	int data;
    	struct node *left,*right;
    }BTNode;
    //创建二叉树 
    BTNode *CreateBTree(int a[],int n)
    {
    	BTNode *root,*c,*p,*pa;
    	root=(BTNode*)malloc(sizeof(BTNode));      //创建根结点 
    	root->data=a[0];
    	root->left=root->right=NULL;
    //	创建其他结点 
    	for(int i=1;i<n;i++){
    		p=(BTNode*)malloc(sizeof(BTNode));
    		p->data=a[i];
    		p->left=p->right=NULL;
    		c=root;
    		while(c){
    			pa=c;
    			if(c->data>p->data)   c=c->left;
    			else                  c=c->right;
    		}
    		if(pa->data>p->data)      pa->left=p;
    		else                      pa->right=p;
    	}
    	return root;
     } 
    // 输出二叉树 
     void postorder(BTNode *root)
     {
     	BTNode**Q;
     	BTNode *p;
     	int front,rear;
    // 	创建队列
    	Q=(BTNode**)malloc(size*sizeof(BTNode*));
    	front=rear=0;
    //	初始化
    	rear=(rear+1)%size;
    	Q[rear]=root;
    //	非递归按层
    	while(front-rear)//队列非空
    	{
    		front=(front+1)%size;//出队列
    		p=Q[front];
    		printf("%5d",p->data);
    		if(p->left){
    			rear=(rear+1)%size;//左子树入队列 
    			Q[rear]=p->left;
    		} 
    		if(p->right){
    			rear=(rear+1)%size;//右子树入队列 
    			Q[rear]=p->right;
    		} 
    	
    	 } 
    	free(Q);
     }
     int main(void)
     {
     	int a[9]={6,2,3,7,4,8,5,9,1};
     	BTNode *root;    //创建根结点 
     	root=CreateBTree(a,9);
     	postorder(root);//按层输出二叉树 
     	return 0;
     }

[Link 1]: http://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=111776&ss_c=ssc.citiao.link