【PTA】 二叉树的层次遍历C++ (20 分)

本文主要是介绍【PTA】 二叉树的层次遍历C++ (20 分)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

编写程序，要求实现（1）按先序遍历序列建立二叉树的二叉链表；（2）按层次遍历二叉树。

C++： 
构成二叉链表的结点类代码如下：
typedef struct BiNode
{            
        char data;                        //结点数据域
        struct BiNode *lchild,*rchild;    //左右孩子指针
}BiTNode,*BiTree;

按加入空树信息的先序遍历序列建立二叉树的二叉链表代码提供如下：
//先序遍历序列建立二叉链表
void CreateBiTree(BiTree &T)
{         
      char ch;
      cin >> ch;
      if(ch=='#')  T=NULL;            //递归结束，建空树
      else{                            
                 T=new BiTNode;
                 T->data=ch;                    //生成根结点
                 CreateBiTree(T->lchild);    //递归创建左子树
                 CreateBiTree(T->rchild);    //递归创建右子树
      }    //else
}                

代码：用队列完成即可。

#include<bits/stdc++.h>
using namespace std;

typedef struct BiNode
{            
    char data;                        //结点数据域
    struct BiNode *lchild,*rchild;    //左右孩子指针
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T)
{         
      char ch;
      cin >> ch;
      if(ch=='#')  T=NULL;            //递归结束，建空树
      else{                            
            	T=new BiTNode;
                 T->data=ch;                    //生成根结点
                 CreateBiTree(T->lchild);    //递归创建左子树
                 CreateBiTree(T->rchild);    //递归创建右子树
      }    //else
}     

queue<BiTree>Q;
void cxbl(BiTree T)  
{
	if(T)
	{
		Q.push(T);
		while(!Q.empty())
		{
			BiTree p=Q.front();
			cout<<p->data;
			Q.pop();
			if(p->lchild) Q.push(p->lchild);
			if(p->rchild) Q.push(p->rchild);
		}
	}
}

int main()
{
	BiTree T;
	CreateBiTree(T);
	cxbl(T);
	return 0;
	
}

这篇关于【PTA】 二叉树的层次遍历C++ (20 分)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！