ch04.树--二叉树创建与遍历

﹏ヽ暗。殇╰゛Y 2023-02-21 12:25 74阅读 0赞

### ch04.树--二叉树创建与遍历 ###

*   *  0.引言
     *  1.demo

## 0.引言 ##

常用的三种方式：

*  中序遍历inorder traversal：左+节点+右. 的顺序遍历.–>中缀表达式
 *  后序遍历postorder traversal: 左+右+节点. 的遍历顺序.–>后缀表达式
 *  先序遍历preorder traversal：节点+左+右. 的遍历顺序.–>前缀表达式（不常用）
 *  层序遍历：顾名思义，从根及诶单开始，每层从左到右依次遍历.
 *  中序遍历应用：二叉搜索树使用中序遍历的结果就是从小到大的序列
 *  后续遍历应用：删除二叉树–先删除两个子节点再删除当前节点

注：  
数据结构与算法描述中，先序遍历为：节点+右+左  
大话数据结构中，先序遍历为：节点+左+右

## 1.demo ##

对下图的二叉树采用前序创建法进行初始化！用字符`#`代表`NULL`.则输入应该为`ABDH#K###E##CFI###G#J##`则理论上几种输出应该如下.

*  前序输出：`ABDHKECFIGJ`
 *  中序输出：`HKDBEAIFCGJ`
 *  后序输出：`KHDEBIFJGCA`

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZiXzk0MTIxOQ_size_16_color_FFFFFF_t_70_pic_center]

#include <iostream>
    
    using namespace std;
    
    typedef  char ElementType;
    
    typedef struct BiTreeNode *PtrToTree;
    typedef PtrToTree BiTree;
    
    struct BiTreeNode
    {
        
    	ElementType Element;
    	BiTree Left;
    	BiTree Right;
    };
    
    
    //按前序输入字符串:节点+左+右.           #表示空节点
    //中序和后序只需将构造节点和左右节点顺序做相应的变换
    void CraeteBiTree(BiTree *bt)
    {
        
    	ElementType x;
    	scanf_s("%c", &x);
    	if (x=='#')//递归出口
    		*bt = NULL;
    	else
    	{
        
    		*bt = (BiTree)malloc(sizeof(BiTreeNode));
    		if (!*bt)
    			exit(OVERFLOW);
    		(*bt)->Element = x;
    
    		CraeteBiTree(&(*bt)->Left);
    		CraeteBiTree(&(*bt)->Right);
    	}
    }
    
    
    //前序遍历：节点+左+右
    void PreorderTraversal(BiTree *bt)
    {
        
    	if (*bt == NULL)//这个NULL不是在构造的时候一般不写吗？
    		return;
    	cout << (*bt)->Element;
    	PreorderTraversal(&(*bt)->Left);
    	PreorderTraversal(&(*bt)->Right);
    }
    
    //中序遍历：左+节点+右
    void InorderTraversal(BiTree *bt)
    {
        
    	if (*bt == NULL)
    		return;
    	InorderTraversal(&(*bt)->Left);
    	cout << (*bt)->Element;
    	InorderTraversal(&(*bt)->Right);
    }
    
    //后序遍历: 左+右+节点
    void PostorderTraversal(BiTree *bt)
    {
        
    	if (*bt == NULL)
    		return;
    	PostorderTraversal(&(*bt)->Left);
    	PostorderTraversal(&(*bt)->Right);
    	cout << (*bt)->Element;
    }
    
    
    void BiTreeTest()
    {
        
    	BiTree BT;
    	//按前序输入ABDH#K###E##CFI###G#J##
    	CraeteBiTree(&BT);
    	//输出ABDHKECFIGJ
    	PreorderTraversal(&BT);
    	cout << endl;
    	//输出HKDBEAIFCGJ
    	InorderTraversal(&BT);
    	cout << endl;
    	//输出KHDEBIFJGCA
    	PostorderTraversal(&BT);
    	cout << endl;
    }
    int main(int argc, char** argv)
    {
        
    	BiTreeTest();
    	system("pause");
    	return 0;
    }

实现效果：  
![在这里插入图片描述][20200630162413186.png_pic_center]

*  [前序中序与中序后序建树][Link 1].

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZiXzk0MTIxOQ_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200630161904653.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZiXzk0MTIxOQ==,size_16,color_FFFFFF,t_70#pic_center
[20200630162413186.png_pic_center]: https://img-blog.csdnimg.cn/20200630162413186.png#pic_center
[Link 1]: https://blog.csdn.net/fb_941219/article/details/107057625