【数据结构】二叉树的层次遍历2

拼搏现实的明天。 2022-08-25 13:58 220阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    typedef char DataType;
    //树结点的数据类型定义
    typedef struct BTnode{
    	DataType data;
    	struct BTnode* lchild,*rchild;
    }BTree;
    //队列的结点数据类型定义
    typedef struct node{
      BTree * tdata; //存放树结点类型的指针
      struct node *next;
    }qnode;
    //队头指针 和 队尾指针
    typedef struct {
      qnode *front,*rear;
    }linkQueue;
    //初始化队列
    void Init(linkQueue *q)
    {
    	q->front=q->rear=NULL;
    }
    //元素入队
    void InsertQueue(linkQueue * &q,BTree * e)
    {
    	qnode * node;
    	node=(qnode*)malloc(sizeof(qnode));
    	node->tdata=e;
    	node->next=NULL;
    	if(NULL==q->front)
    	{
    		q->front=q->rear=node;
    	}
    	else
    	{
    		q->rear->next=node;
    		q->rear=node;
    	}
    
    }
    //元素出队
    BTree * outQueue(linkQueue * &q)
    {
    	BTree * e;
    	qnode *temp;
    	if(NULL==q->front)
    		e=NULL;
    	else
    	{
    		temp=q->front;
    		e=temp->tdata;
    		q->front=temp->next;
    		free(temp);
    	}
    	return e;
    }
    //创建二叉树,以先序的方式输入，如果左孩子或右孩子为空，则输入#  
    /* 
       例子  A      输入为:ABD##E##CF### 
           /  \ 
         B     C 
        / \    /  
       D   E  F     
    */   
    void createBTree(BTree * &t)
    {
    	char c;
       	c=getchar();
    	if(c=='#')
    		t=NULL;
    	else
    	{
    		t=(BTree*)malloc(sizeof(BTree));
    		t->data=c;
    		createBTree(t->lchild);//创建左子树
    		createBTree(t->rchild);//创建右子树
    	}
    }
    
    /*
    
    二叉树的层次遍历算法: 
    1.队列queue初始化；
    2. 将根指针入队；
    3. 循环直到队列queue为空
          3.1 q=队列queue出队的元素;
          3.2 访问结点q的数据域;
          3.3 若结点q存在左孩子，则将左孩子入队;
          3.4 若结点q存在右孩子，则将右孩子入队;
    
    */
    //二叉树的层次遍历
    void hierarchyTtraversal(linkQueue *queue,BTree * root)
    {
    	BTree *q;
    	InsertQueue(queue,root);
    	while(NULL!=queue->front)
    	{
    		q=outQueue(queue);
    		printf("%c  ",q->data);
    		if(q->lchild)
    			InsertQueue(queue,q->lchild);
    		if(q->rchild)
    			InsertQueue(queue,q->rchild);
    	}
    }
    
    int main()
    {
    	BTree *root;
    	linkQueue queue;
    	Init(&queue);
    	createBTree(root);
    	hierarchyTtraversal(&queue,root);
    	printf("\n");
    	return 0;
    }