二叉树的创建和遍历

古城微笑少年丶 2024-02-19 11:10 48阅读 0赞

#include<iostream>
    #define MAXSIZE 100
    using namespace std;
    
    //编写二叉链表的数据结构体
    typedef struct BiTNode 
    {
    	char data;
    	struct BiTNode* 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);
    	}
    }
    
    
    //先序遍历二叉树
    void xian(BiTree T)
    {
    	if (T)
    	{
    		cout << T->data << " ";
    		xian(T->lchild);
    		xian(T->rchild);
    	}
    }
    
    //中序遍历二叉树
    void zhong(BiTree T)
    {
    	if (T)
    	{
    		zhong(T->lchild);
    		cout << T->data << " ";
    		zhong(T->rchild);
    	}
    }
    
    //后序遍历二叉树
    void hou(BiTree T)
    {
    	if (T)
    	{
    		hou(T->lchild);
    		hou(T->rchild);
    		cout << T->data << " ";
    	}
    }
    
    //可以运用队列来帮助层次遍历
    //创建队列的结构体
    typedef struct
    {
    	BiTNode* data[MAXSIZE];//定义为树类型的数据
    	int front;//头指针
    	int rear;//尾指针
    }sequeue;
    
    //判断队列是否为空
    int EmptyQueue(sequeue q)
    {
    	if (q.front == q.rear)
    		return 0;
    	else
    		return 1;
    }
    //入队
    void pushqueue(sequeue& q, BiTree t)
    {
    	if (q.front == (q.rear + 1) % MAXSIZE)
    		cout << "队列已满";
    	q.rear = (q.rear + 1) % MAXSIZE;
    	q.data[q.rear] = t;
    }
    //出队
    void popqueue(sequeue& q)
    {
    	if (q.front == q.rear)
    		cout << "队列为空";
    	q.front = (q.front + 1) % MAXSIZE;
    }
    //层次遍历二叉树
    void ceng(BiTree t)
    {
    	sequeue q;
    	q.front = q.rear = 0; //初始化
    	BiTree tem;//创建一个子树
    	pushqueue(q, t);//将根节点录入队列
    	while (EmptyQueue(q))//判断队列是否为空
    	{
    		tem = q.data[q.front + 1]; 
    		cout << tem->data << " ";//输出头结点
    		popqueue(q);//头结点出队
    		if (tem->lchild != NULL)//左子树不为空，则左子树入队
    			pushqueue(q,tem->lchild);
    		if (tem->rchild != NULL)//右子树不为空，则右子树入队
    			pushqueue(q, tem->rchild);
    	}
    }
    
    //主函数
    int main()
    {
    	BiTree T;
    	cout << "请输入按照先序遍历创建二叉树(输入‘#’为空数)：" << endl;
    	CreateBiTree(T);
    	//先序遍历
    	cout << "先序遍历二叉树的结果如下：" << endl;
    	xian(T);
    	cout << endl;
    	//中序遍历
    	cout << "中序遍历二叉树的结果如下：" << endl;
    	zhong(T);
    	cout << endl;
    	//后序遍历
    	cout << "后序遍历二叉树的结果如下：" << endl;
    	hou(T);
    	cout << endl;
    	cout << "层次遍历二叉树的结果如下：" << endl;
    	ceng(T);
    	return 0;
    }

结果如下：

![10c8ca8a93584bd6a287ff78dbae598a.png][]

[10c8ca8a93584bd6a287ff78dbae598a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/7978a8a4577546cca525251f2e1b0db2.png