数据结构之二叉树的深度优先遍历

约定不等于承诺〃 2022-08-06 01:18 129阅读 0赞

可以将二叉树的遍历方式分为两类：

一：深度

先序遍历

中序编列

后序遍历

二、广度（也就是从左往右）

层序遍历

下面是深度的三种遍历方式：

#include<iostream>
    
    using namespace std;
    
    
    typedef struct BitNode{
    	char data;
    	struct  BitNode *lchild, *rchild;
    }BitNode,*BiTree;
    
    void CreateBiTree(BiTree &T);
    void PreOrderTraverse(BiTree T);
    void InOrderTraverse(BiTree T);
    void PostOrderTraverse(BiTree T);
    
    
    
    void CreateBiTree(BiTree &T)
    {
    	
    	//创建二叉树时使用完整的字符串序列表示,
    	//示例:ab##c##
    
    	char ch;
    	scanf("%c",&ch);
    	if (ch == '#')	T = NULL;//   空树
    	else
    	{
    		T = new BitNode;
    		if (T)
    		{
    			T->data = ch;
    			CreateBiTree(T->lchild);
    			CreateBiTree(T->rchild);
    		}
    	}
    }
    
    
    //先序遍历二叉树
    void PreOrderTraverse(BiTree T)
    {
    	if (T != NULL)
    	{
    		cout << T->data << endl;
    		PreOrderTraverse(T->lchild);
    		PreOrderTraverse(T->rchild);
    	}
    }
    
    //中序遍历二叉树
    void InOrderTraverse(BiTree T)
    {
    	if (T != NULL)
    	{
    		InOrderTraverse(T->lchild);
    		cout << T->data << endl;
    		InOrderTraverse(T->rchild);
    	}
    }
    
    
    //后序遍历二叉树
    void PostOrderTraverse(BiTree T)
    {
    	if (T != NULL)
    	{
    		PostOrderTraverse(T->lchild);
    		PostOrderTraverse(T->rchild);
    		cout<< T->data << endl;
    	}
    }
    
    
    
    
    int main()
    {
    	BiTree T;
    	CreateBiTree(T);
    	cout << "二叉树已经生成，开始先序遍历：" << endl;
    	PreOrderTraverse(T);
    	cout << "开始中序遍历：" << endl;
    	InOrderTraverse(T);
    	cout << "开始后序遍历：" << endl;
    	PostOrderTraverse(T);
    	return 0;
    }