【数据结构】二叉树的三种遍历——创建与输出

深碍√TFBOYSˉ_ 2023-07-20 08:21 6阅读 0赞

二叉树有三种遍历方式：先序遍历、中序遍历和后序遍历。

不妨我们现在规定：在任何的遍历方式中，我们都让左子树先于右子树遍历。这样就可以使得遍历方式由6种变为我们规定的以上三种。

用N表示根节点的话，这三种遍历方式可以分表示为：NLR，LNR，LRN。

## 一、关于ADT的定义及声明 ##

创建二叉树之前，我们需要先创建一个抽象数据类型（简称ADT）：

typedef struct bt{
            //binary tree的简称，哈哈哈quq
    	ElemType data;
    	bt *left,*right;    //节点的左子树和右子树
    }BT;

## 二、二叉树的创建 ##

**注：默认`using namespace std;`了哟**

**基于先序遍历的二叉树建立：**

void preOrderCreateo(BT *&t){
        
    	ElemType elem;
    	cin>>elem;
    	if(elem=='#'){
             //不妨以#作为不创建子树的标志吧
    		t=NULL;
    	}
    	else{
        
    		t=new BT;
    		t->data=elem;
    		t->left=NULL;
    		t->right=NULL;
    		preOrderCreate(t->left);
    		preOrderCreate(t->right);  //递归创建左右子树
    	}
    }

*建立二叉树建议用**先序遍历**哟~其余两种在此处不做说明了quq*

## 三、二叉树的遍历 ##

**1.基于先序遍历建立输出二叉树的先序遍历序列**

void preOrder(BT *&t){
        
    	if(t!=NULL){
        
    		cout<<t->data<<" "; //先输出当前节点
    		preOrder(t->left);  //然后遍历左子树
    		preOrder(t->right);  //最后遍历右子树
    	}
    }

**2.基于先序遍历建立输出二叉树的中序遍历序列**

void preOrder(BT *&t){
        
    	if(t!=NULL){
        
    		preOrder(t->left);  //先遍历左子树
    		cout<<t->data<<" "; //然后输出当前节点
    		preOrder(t->right);  //最后遍历右子树
    	}
    }

**3.基于先序遍历创建输出二叉树的后序遍历序列**

void preOrder(BT *&t){
        
    	if(t!=NULL){
        
    		preOrder(t->left);  //先遍历左子树
    		preOrder(t->right);  //然后遍历右子树
    		cout<<t->data<<" "; //最后输出当前节点	
    	}
    }

*显然，采取的遍历方式不同，输出的结果也会收到影响。A题时一定要注意题目要求！！*