二叉树的先序，中序，后序（递归、非递归版本）（一）

二叉树的结构

typedef struct{
    char val;
    struct Binode *lchild;
    struct Binode *rchild;
}Binode;

一、递归情况下实现

示例：进行先序、中序、后序以及层次遍历

#include<iostream>
#include<queue>
#include<stdlib.h>
using namespace std;

typedef char ElemType;

typedef  struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//二叉树的建立，按前序遍历的方式建立二叉树
void CreateBiTree(BiTree &T)
{
    ElemType ch;
    cin >> ch;
    if (ch == '#')
        T = NULL;  //保证是叶结点
    else
    {
        T = (BiTree)malloc(sizeof(BiTNode));
        (T)->data = ch;
        CreateBiTree(T->lchild);//构造左子树
        CreateBiTree(T->rchild);//构造右子树    
    }
}


//递归方式前序遍历二叉树
void PreOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    cout<<T->data; 
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}

//递归方式中序遍历二叉树
void InOrderTraverse(BiTree T)
{
    if(T==NULL)
       return;
    InOrderTraverse(T->lchild);
    cout<<T->data; 
    InOrderTraverse(T->rchild);
}

//递归方式后序遍历二叉树

void PostOrderTraverse(BiTree T)
{
  if(T==NULL)
    return;
  PostOrderTraverse(T->lchild);
  PostOrderTraverse(T->rchild);
  cout<<T->data; 
}
void Level_Traverse(BiTree T){//层次遍历
	queue<BiTree> q;//创建队列q
	BiTree q1;
	q.push(T);
	while(!q.empty()){
	   q1=q.front();
	   cout<<q1->data;
	   q.pop();
	   if(q1->lchild)
		   q.push(q1->lchild);
	   if(q1->rchild)
		   q.push(q1->rchild);
	}

}

int main()
{
    
    BiTree T = NULL;
    cout << "请以前序遍历的方式输入二叉树："; 
    CreateBiTree(T);// 建立二叉树

    cout << "递归前序遍历输出为：" << endl;
    PreOrderTraverse(T);
    cout << endl;

    cout << "递归中序遍历输出为：" << endl;
    InOrderTraverse(T);
    cout << endl;

    cout << "递归后序遍历输出为：" << endl;
    PostOrderTraverse(T);
    cout << endl;
	cout << "层次遍历输出为：" << endl;
    Level_Traverse(T);
	cout<<endl;
	system("pause");
    return 0;
}

二叉树的先序，中序，后序（递归、非递归版本）（一）

这里，我重点说一下层次遍历的实现：

层次遍历，先将根元素入队，再利用循环（当队列不空时，访问该出队的元素，再进行出队）

该出队元素，若其左子树不为空，则将左子树入队；

若其右子树不为空，则将右子树入队。

注意：我在队列的选择时，选取的是STL容器中的queue队列，因为其提供了许多方便快捷的成员函数，操作起来更为方便，大大减少了代码量。

二叉树的先序，中序，后序（递归、非递归版本）（一）

二叉树的结构

相关推荐