数据结构作业——————二叉树的三种遍历方式

末蓝、 2022-05-12 14:50 144阅读 0赞

# 数据结构作业： #

*  ##### 二叉树的建立 #####
 *  ##### 三种遍历方式 #####

L：遍历左子树  
D：访问根节点  
R：遍历右子树

DLR：先序遍历  
LDR：中序遍历  
LRD：后序遍历

#include<bits/stdc++.h>
    using namespace std;
    typedef char ElemType;//节点保存数据的类型，我让节点保存字符型数据
    struct node{
        
            ElemType data;//数据域
            node *lchild,*rchild;//两个指针域，二叉链表存储二叉树
    };
    
    void merge_tree(node *p,node *l,node *r)//p:父亲，l:left_child左儿子，r:right_child:右儿子
    {
        
            p->lchild = l;
            p->rchild = r;
    }
    node *create_node(ElemType data)//建立节点，返回一个node指针
    {
        
            node *p = new node;
            p->data = data;
            p->lchild = p->rchild =0;
            return p;
    }
    void InOrderTraverse(node *t)//老师的代码，先序遍历
    {
        
            if(t)
            {
        
                    InOrderTraverse(t->lchild);//遍历左子树
                    cout<<t->data<<" ";//访问根节点
                    InOrderTraverse(t->rchild);//遍历右节点
            }
    }
    void DLR(node *t)//先序遍历
    {
        
            if(t)
            {
        
                    cout<<t->data<<" ";//访问根节点
    
                    DLR(t->lchild);//遍历左子树
    
                    DLR(t->rchild);//遍历右子树
            }
    }
    
    void LDR(node *t)//中序遍历
    {
        
            if(t)
            {
        
    
                    LDR(t->lchild);
    
                    cout<<t->data<<" ";
    
                    LDR(t->rchild);
            }
    }
    
    void LRD(node *t)//后序遍历
    {
        
            if(t)
            {
        
                    LRD(t->lchild);
    
                    LRD(t->rchild);
    
                    cout<<t->data<<" ";
            }
    }
    int main()
    {
        
            /*
                    建立节点
            */
            node *a=create_node('a');
            node *b=create_node('b');
            node *c=create_node('c');
            node *d=create_node('d');
            node *e=create_node('e');
            node *f=create_node('f');
            node *g=create_node('g');
            /*
                    建立树
                             a
                          /     \
                         b       c
                        / \     / \
                       d   e   f   g
    
    
                    先序遍历：a b d e c f g
                    中序遍历：d b e a f c g
                    后序遍历：d e b f g c a
    
            */
            merge_tree(a,b,c);
            merge_tree(b,d,e);
            merge_tree(c,f,g);
            /*
                    遍历树
            */
            cout<<"先序遍历：";
            DLR(a);
            cout<<endl;
            cout<<"中序遍历：";
            LDR(a);
            cout<<endl;
            cout<<"后序遍历：";
            LRD(a);
            cout<<endl;
            return 0;
    }

三个节点形成的二叉树有五种形式：(空代表节点不存在)

# 第一种：![第一种][70] #

*  先序遍历：a b c
 *  中序遍历：b a c
 *  后序遍历：b c a

# 第二种：![在这里插入图片描述][70 1] #

*  先序遍历：a b c
 *  中序遍历：c b a
 *  后序遍历：c b a

# 第三种：![在这里插入图片描述][70 2] #

*  先序遍历：a b c
 *  中序遍历：b c a
 *  后序遍历：c b a

# 第四种![在这里插入图片描述][70 3] #

*  先序遍历：a b c
 *  中序遍历：a c b
 *  后序遍历：c b a

# 第五种![在这里插入图片描述][70 4] #

*  先序遍历：a b c
 *  中序遍历：a b c
 *  后序遍历：c b a

--------------------

本人水平有限，如有错误请指出，谢谢！

[70]: /images/20220504/67f7d53fb60b4de3b45830592a5d86ad.png
[70 1]: /images/20220504/d5e06e864acc40dea56f6fbf4db02b4a.png
[70 2]: /images/20220504/4119901e7e1f4e5b846dbe9ac94b345e.png
[70 3]: /images/20220504/d40b355516234ad69e33349fe27c1a7f.png
[70 4]: /images/20220504/7039a5e2ac46470694fa5fb669741d57.png