【数据结构与算法】二叉树的递归遍历

╰+哭是因爲堅強的太久メ 2022-01-13 10:27 252阅读 0赞

# 二叉树的递归遍历 #

## 基本概念 ##

**前序遍历**：先访问根结点，再前序遍历左子树，再前序遍历右子树，访问顺序ABDGHCEIF  
![在这里插入图片描述][20190616214140511.PNG]  
**中序遍历**：先中序遍历左子树，然后访问根结点，最后中序遍历右子树,访问顺序GDHBAEICF  
![在这里插入图片描述][20190616214149926.PNG]  
**后序遍历**：先叶子后结点遍历左子树，右子树，最后访问根结点,访问顺序GHDBIEFCA  
![在这里插入图片描述][2019061621420125.PNG]

## 代码实现 ##

1.  定义树节点

//定义节点
    typedef struct node
    {
        
    	struct node *lchild;
    	struct node *rchild;
    	char data;
    }BiTreeNode, *BiTree;//*BiTree的意思是给 struct node*起了个别名，叫BiTree，故BiTree为指向节点的指针。

1.  按照前序顺序创建二叉树

//按照前序顺序建立二叉树
    void createBiTree(BiTree &T) //&的意思是传进来节点指针的引用，括号内等价于 BiTreeNode* &T,目的是让传递进来的指针发生改变
    {
        
    	char c;
    	cin >> c;
    	if ('#' == c)             //当遇到#时，令树的根节点为NULL，从而结束该分支的递归
    		T = NULL;
    	else
    	{
        
    		T = new BiTreeNode;
    		T->data = c;
    		createBiTree(T->lchild);
    		createBiTree(T->rchild);
    	}
    }

1.  使用前序遍历二叉树并打印

//前序遍历二叉树并打印
    void preTraverse(BiTree T)
    {
        
    	if (T)
    	{
        
    		cout << T->data << " ";
    		preTraverse(T->lchild);
    		preTraverse(T->rchild);
    	}
    }

1.  使用中序遍历二叉树并打印

//中序遍历二叉树并打印
    void midTraverse(BiTree T)
    {
        
    	if (T)
    	{
        
    		midTraverse(T->lchild);
    		cout << T->data << " ";
    		midTraverse(T->rchild);
    	}
    }

1.  使用后续遍历二叉树并打印

//后续遍历二叉树并打印
    void postTraverse(BiTree T)
    {
        
    	if (T)
    	{
        
    		postTraverse(T->lchild);
    		postTraverse(T->rchild);
    		cout << T->data << " ";
    	}
    }

1.  测试主函数

#include <iostream>
    #include <string>
    using namespace std;
    
    int main()
    {
        
    	BiTree T;               //声明一个指向二叉树根节点的指针               
    	createBiTree(T);
    	cout << "二叉树创建完成！" << endl;
    	cout << "前序遍历二叉树：" << endl;
    	preTraverse(T);
    	cout << endl;
    	cout << "中序遍历二叉树：" << endl;
    	midTraverse(T);
    	cout << endl;
    	cout << "后序遍历二叉树：" << endl;
    	postTraverse(T);
    	return 0;
    }

ps:更多数据结构知识详见：  
[常见数组结构与算法][Link 1]

[20190616214140511.PNG]: /images/20220113/9969d81503d441b0b11a133cc4b4c722.png
[20190616214149926.PNG]: /images/20220113/4f45fe592eef49b58cc9b74133055f20.png
[2019061621420125.PNG]: /images/20220113/7fed5e2937ae4b57959ef8b5c5f79a4a.png
[Link 1]: https://blog.csdn.net/weixin_43930512/article/details/90812460#font_colorredfont_42