二叉树的三种遍历的数据顺序_数据结构树的遍历[通俗易懂]

二叉树的三种遍历的数据顺序_数据结构树的遍历[通俗易懂]二叉树(BinaryTree)一种重要的树形结构,其每个节点最多只能有两棵子树,通常称为左子树和右子树,且子树有左右之分,其次序不能颠倒

目录

一. 二叉树概述

1. 基本性质

2. 例题分析

二. 二叉树的实现方式

1. 第一类数组实现

2. 结构体指针实现

3. 第二类数组实现

4. 例题分析

三. 二叉树的遍历方式

1. 先序遍历

2. 中序遍历

3. 后序遍历

4. 例题分析

4.1 UVA548 树

4.2 UVA839 天平

四. 二叉树的建树方式

1. 按位置建树

2. 按遍历建树

3. 例题分析

五. 二叉树的层序与宽度

1. 二叉树的层序遍历

1.1 基本概念

1.2 实现方式

2. 二叉树的宽度


一. 二叉树概述

二叉树(Binary Tree)一种重要的树形结构,其每个节点最多只能有两棵子树,通常称为左子树和右子树,且子树有左右之分,其次序不能颠倒。二叉树是n个有限元素的集合,该集合或者为空(称为空二叉树),或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。

1. 基本性质

(1)在二叉树的第 i 层上最多有 2^{i-1}个节点 (i>=1)

(2)二叉树中如果深度为k(有k层),那么最多有2^{k}-1个节点(k>=1)

(3)若二叉树按照从上到下从左到右依次编号,则若某节点编号为k,则其左右子树根节点编号分别为2k和2k+1;

(4)二叉树可以分为一些特殊类型,比如满二叉树、完全二叉树。其中,满二叉树是指高度为h且由2^{h}-1个节点构成,并且所有叶子结点都在同一层上的二叉树;完全二叉树则是对一颗具有n个结点的二叉树按层序编号,如果编号为i(1 ≤ i ≤ n)的结点与同样深度的满二叉树中编号为i 的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树。

二叉树的三种遍历的数据顺序_数据结构树的遍历[通俗易懂]

二叉树的三种遍历的数据顺序_数据结构树的遍历[通俗易懂]

(5)在完全二叉树中,具有n个节点的完全二叉树的深度为\left \lfloor \log _{2}n \right \rfloor + 1,其中\left \lfloor x \right \rfloor是对结果x向下取整。而满二叉树的深度则为\left \lfloor \log _{2}(n+1) \right \rfloor

2. 例题分析

(1)问题描述

UVA679 小球下落

Problem Description
有一颗满二叉树,每个节点是一个开关,初始全是关闭的,小球从顶点落下,小球每次经过开关就会把它的状态置反,这个开关为关时,小球左跑,为开时右跑。现在问第k个球下落到d层时的开关编号。

Input

输入深度d和小球个数k。d<20,k<524288

Output
对于每组测试数据,输出计算结果。

(2)题解代码

        在分析时,该题最先想到的应该是模拟,即开一个数组表示开关,下标表示编号,根据k的子树为2k和2k+1来改变数组状态,并判断输出结果。但是该思路不但要开2^20这么大的数组而且循环判断会超时。因此需要改变思路,寻找题目的规律:

  • 对于每一层,第奇数个落入该层的球都是往左走的,第偶数个落入该层的球都是往右走的。
  • 小球都是按照编号依次下落的,对于左枝(也就是奇数球),每个I号小球落入该层都是第(I+1)/2个小球,而偶数是往右走的I/2个小球。
  • 每一层循环递归(共d层),来判断I的状态,即可找出最后叶子。
#include <iostream>
#include<cstdio>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==-1)break;
        int D,I;
        while(n--)
        {
            cin>>D>>I;//D层I个小球
            int k=1;
            for(int i=0; i<D-1; i++)
            {
                if(I%2)//奇数是往左走的第(i+1)/2个小球
                {
                    k=k*2;//往左走是k*2
                    I=(I+1)/2;//改变小球
                }
                else
                {
                    k=(k*2+1);//偶数是往右走的第(i/2)个小球
                    I=I/2;
                }
            }
            cout<<k<<endl;
        }
    }
    return 0;
}

二. 二叉树的实现方式

1. 第一类数组实现

        第一类数组实现使用数组root[]存储结点值,在这种实现当中,对于编号为k的节点,其左子节点的编号为2*k,右子节点的编号为2*k + 1,另外确定根节点的编号为1。毫无疑问,这种实现极易产生巨大的空间浪费,比如对于一个只有一条链的树,假设该树含有31个节点,存储这31个节点却需要开一个2^30大小的数组,因此此方法虽易于理解但较少使用。

2. 结构体指针实现

        该方法用结构体指针u来表示一个节点,其中u->v表示该节点的权值,u->left和u->right分别指向该节点的左右子节点,初始化全部为NULL,若需用到该节点,则申请空间,否则视为无子节点,就这样互相联系成一颗结构体指针二叉树。这种方式下非常节省空间,但是容易出现指针悬挂或者未知的指针内存错误。

3. 第二类数组实现

        对于一棵有n个节点树,只需要开一个大小为n的数组,节点按照出现顺序依次编号。这么一来,虽然节省空间,但每个节点的左右节点的编号就无法通过2*k、2*k+1的形式来直接确定关系了,这时就需要开辟数组lch[maxn] , rch[maxn]

        其中lch[u]表示u节点的左子节点的编号,因此通过u = lch[u]就可以访问到u节点的左子节点,rch[u]的含义同理。另外,用value[u]表示编号为u节点的权值。如此一来,申请新节点的newnode函数与初始化的newtree函数写法就变得不同了,具体见代码。(此处只需结点个数个数组即可,并不计算数值!)

4. 例题分析

(1)问题描述

UVA122 树的层次遍历

Problem Description

给你一颗二叉树,按照从上到下从左到右的顺序输出每个节点的权值,若某个节点没有赋值或者输入超过一次,则输出no complete

Example Input

(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()

Example Output

5 4 8 11 13 4 7 2 1
not complete

(2)题解代码

方法一:结构体指针实现法

#include <iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=266;
char s[maxn];//输入
bool failed;
struct Node//节点
{
    bool have_value;//该点是否被赋值过
    int v;//该点权值
    Node*left,*right;//左右子节点
    Node():have_value(false),left(NULL),right(NULL){}//初始化函数
};
Node*root;//树根!!
Node* newnode()//分配内存
{
    return new Node();//分配同时初始化
}
void addnode(int v,char *a)//建树
{
    int len=strlen(a);
    Node *u=root;
    for(int i=0;i<len;i++)
    {
        if(a[i]=='L')//左
        {
            if(u->left==NULL)u->left=newnode();//若左节点没有分配内存,没有开辟过,则申请内存,因为经过该节点了,该节点必须赋值!
            u=u->left;//更新路径
        }
        else if(a[i]=='R')//右
        {
            if(u->right==NULL)u->right=newnode();//同上
            u=u->right;
        }
    }
    if(u->have_value)failed=true;//如果该节点已经被赋值过了,则非法输入,报错
    u->v=v;//更新该节点
    u->have_value=true;//标记赋值
}

bool read_in()//输入
{
    root=newnode();//给树根申请内存
    failed=false;//标记
    for(;;)
    {
        if(scanf("%s",s)!=1)return false;//输入c+z了结束
        if(strcmp(s,"()")==0)break;//读到()表示该组数据正常结束
        int v;
        sscanf(&s[1],"%d",&v);//sscanf读取权值并赋给v
        addnode(v,strchr(s,',')+1);//读取路径,并且建树,最好不要在此处判断failed因为还没有完整输入数据
    }
    return true;
}
bool bfs(vector<int>&ans)//遍历树,并保存权值
{
    queue<Node*>q;//队列
    ans.clear();
    q.push(root);
    while(!q.empty())
    {
        Node*u=q.front();
        q.pop();
        if(!u->have_value)return false;//若该节点没有赋值,说明出现了越节点赋值现象,报错
        ans.push_back(u->v);//存入节点权值,按照从上到下从左到右
        if(u->left!=NULL)q.push(u->left);//左
        if(u->right!=NULL)q.push(u->right);//右--->循环递归!!借助queue
    }
    return true;
}
int main()
{
    while(1)
    {
        if(!read_in())//输入数据并且建树完成
            break;
        vector<int> ans;//ans用来存储权值,最后输出
        if(!failed&&bfs(ans))//均无错误,则可输出
        {
            int l=ans.size();
            for(int j=0;j<l;j++)//输出
            {
                if(j==0)
                    cout<<ans[j];
                else
                    cout<<" "<<ans[j];
            }
            cout<<endl;
        }
        else
            cout<<"not complete"<<endl;
    }
    return 0;
}

方法二:第二类数组实现法

void newtree()                        //初始化一颗新树,由于静态实现无法回收内存,因此顺便充当析构函数  
{  
    lch[root] = rch[root] = 0;  
    have_value[root] = 0;  
    cnt = root;  
}  
int newnode()                       //建立新节点的函数,其中0相当于结构体中的空指针  
{  
    int u = ++cnt;  
    lch[u] = rch[u] = 0;  
    have_value[u] = 0;  
    return u;  
}  
void addnode(int v , char * s)      //建立新节点的过程  
{  
    int n = strlen(s);  
    int u = root;  
    for(int i = 0; i<n;i++){  
        if(s[i] == 'L' ) {  //重点!
            if(lch[u] == 0)  
                lch[u] = newnode();  
            u = lch[u];  
        }  
        else if(s[i] == 'R'){  
            if(rch[u] == 0)  
                rch[u] = newnode();  
            u = rch[u];  
        }  
    }  
    if(have_value[u])failed = true;  
    value[u] = v;  
    have_value[ u ] = 1;
}  

三. 二叉树的遍历方式

1. 先序遍历

        先序遍历按照根节点->左子树->右子树的顺序访问二叉树(注:每个节点的分支都遵循上述的访问顺序,体现“递归调用”),具体遍历步骤为:

  (1)访问根节点;

  (2)采用先序递归遍历左子树;

  (3)采用先序递归遍历右子树;

二叉树的三种遍历的数据顺序_数据结构树的遍历[通俗易懂]

        以上述图片为例,其先序遍历结果为:A BDFE CGHI,具体思维过程如下:

  (1)先访问根节点A,

  (2)A分为左右两个子树,因为是递归调用,所以左子树也遵循“先根节点-再左-再右”的顺序,所以访问B节点,

  (3)然后访问D节点,

(4)访问F节点的时候有分支,同样遵循“先根节点-再左–再右”的顺序,

  (5)访问E节点,此时左边的大的子树已经访问完毕,

  (6)然后遵循最后访问右子树的顺序,访问右边大的子树,右边大子树同样先访问根节点C,

  (7)访问左子树G,

  (8)因为G的左子树没有,所以接下俩访问G的右子树H,

  (9)最后访问C的右子树I

2. 中序遍历

        中序遍历按照左子树->根节点->右子树的顺序访问二叉树(注:每个节点的分支都遵循上述的访问顺序,体现“递归调用”),具体遍历步骤为:

  (1)采用中序遍历左子树;

  (2)访问根节点;

  (3)采用中序遍历右子树

二叉树的三种遍历的数据顺序_数据结构树的遍历[通俗易懂]

        以上述图片为例,其中序遍历结果为:DBEF      GHCI

3. 后序遍历

        后序遍历按照左子树->右子树->根节点的顺序访问二叉树(注:每个节点的分支都遵循上述的访问顺序,体现“递归调用”),具体遍历步骤为:

  (1)采用后序递归遍历左子树;

  (2)采用后序递归遍历右子树;

  (3)访问根节点;

二叉树的三种遍历的数据顺序_数据结构树的遍历[通俗易懂]

         以上述图片为例,其后序遍历的结果为:DEFB  HGIC   A

        注意:三种方法遍历过程中经过节点的路线一样;只是访问各个节点的时机不同,递归算法主要使用堆栈来实现。

4. 例题分析

4.1 UVA548 树

(1)问题描述

Problem Description

输入一个二叉树的中序和后序,输出一个叶子节点,使得该叶子节点到根的数值总和最小。

Sample Input
3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255

Sample Output
1
3
255

(2)题解代码

        首先需要先明确一个知识点,就是如果知道了一棵树的中序和后序遍历,如何求它的前序遍历?思考如下:

  • 第一步:初始时后序遍历的最后一个数字就是我们的一个子树的根节点
  • 第二步:找到根结点后,跟据中序遍历的性质,该序列树就会被自然地分成了左右两个部分
  • 第三步:统计出来左右两个子树的大小和长度,这样就能继续重复上面的步骤

        不断通过中序和后序来建树,然后递归找到所有节点到根节点的路径和,不断更新,最后输出即可。其代码如下:

#include <iostream>
#include<string>
#include<sstream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=10000+10;
int lch[maxn],rch[maxn],in_order[maxn],post_roder[maxn];
int n;
int read_list(int* a)
{
//    memset(lch,0,sizeof(lch));
//    memset(rch,0,sizeof(rch));
//    memset(in_order,0,sizeof(in_order));
//    memset(post_roder,0,sizeof(post_roder));
    string line;
    if(!getline(cin,line))return false;//因为题目说一行数据,没有结束标志,所以以回车为结束用字符串读入!
    stringstream ss(line);
    n=0;
    int x;
    while(ss>>x)a[n++]=x;//存入数组
    return n>0;
}
int build(int L1,int R1,int L2,int R2)//建树各树的: 中序-后序
{
    if(L1>R1)return 0;//空树
    int root=post_roder[R2];//树根是后序的最后一个字符
    int p=L1;
    while(in_order[p]!=root)p++;//在中序里找到左子树结点个数
    int cnt=p-L1;//左子树个数
    lch[root]=build(L1,p-1,L2,L2+cnt-1);//以root为根的左子树建树l1-p-1是中序的左边也就是左子树的中序,l2-l2+cnt-1是左子树的后序,看上面图片就可以知道,下面同,这样不断递归找到各个节点!
    rch[root]=build(p+1,R1,L2+cnt,R2-1);//右子树建树
    return root;
}
int best,best_sum;//最优解
void dfs(int u,int sum)//找最优解
{
    sum+=u;
    if(!lch[u]&&!rch[u])//没有左右子树了说明已经到达最低端叶子,该路径完成,判断是否最优解
    {
        if(sum<best_sum||(sum==best_sum&&u<best))
        {
            best_sum=sum;
            best=u;
        }
    }
    if(lch[u])dfs(lch[u],sum);//否则还在树枝上,继续向下找叶子
    if(rch[u])dfs(rch[u],sum);
}
int main()
{
    while(read_list(in_order))//把中序读入数组in_order
    {
        read_list(post_roder);//读入后序post_order
        build(0,n-1,0,n-1);//建树
        best_sum=1000000000;//最优解
        dfs(post_roder[n-1],0);//递归寻找最优解
        cout<<best<<endl;
    }
    return 0;
}

4.2 UVA839 天平

(1)问题描述

Problem Description
根据干杠平衡原理,判断题目所给出的数据组成的天平能否平衡。注意,此天平可能包含子天平。输入时,如果w为0,则表示包含子天平,子天平按照先左后右的方法输入,子天平只需要判断w1*d1==w2*d2是否正确即可。那么父天平又如何判断呢? 公式一样,不同的是,父天平的两边的重量是子天平砝码总和。  

Sample Input
1
0 2 0 4
0 3 0 1
1 1 1 1
2 4 4 2
1 6 3 2

Sample Output
YES

(2)题解代码

        该题的要点在于怎么输入。题目的输入是按照构建天平进行的,什么时候天平构建完什么时候一组输入结束,所以这就要求一边输入一边建树,可以考虑递归输入!

#include <iostream>
using namespace std;
bool solve(int &w)
{
    int w1,d1,w2,d2;
    cin>>w1>>d1>>w2>>d2;
    bool b1=true,b2=true;
    if(!w1)b1=solve(w1);//如果w1=0,则说明w1有子树,同时把w1带入递归求出w1也就是子树总重量
    if(!w2)b2=solve(w2);//同上
    //求总重量,其实如果只考虑最上层的天平,这步似乎没什么意义;
    //但其实它的意义在于,在当前是递归到一个子天平的情况时,就要重新输入子天平所在处的左右天平,如果有了这句代码,参数 W1 或者 W2,最终就能变为子天平上的两个左右天平的总重量。如此,等到判断 D1 * W1 == D2 * W2时,W1 和 W2就都不会是0了,而是该子天平下所有子天平的总重量(如果有的话,没有子天平,就还是它本身的质量,总之不会是0,而是它自己或是自己所有子天平的重量
    w=w1+w2;
    return b1&&b2&&(w1*d1==w2*d2);//要想平衡,每一个天平都要平衡!
}
int main()
{
    int T,W;
    cin>>T;//组数
    while(T--)
    {
        if(solve(W))//输入同时判断
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
        if(T)
            cout<<endl;
    }
    return 0;
}

四. 二叉树的建树方式

1. 按位置建树

        如果题目给出了每一个节点的位置描述,则每个节点递归赋值即可,类似于例题二。其核心代码如下:

void addnode(int v,char *a)//建树
{
    int len=strlen(a);
    Node *u=root;
    for(int i=0;i<len;i++)
    {
        if(a[i]=='L')//左
        {
            if(u->left==NULL)u->left=newnode();//若左节点没有分配内存,没有开辟过,则申请内存,因为经过该节点了,该节点必须赋值!
            u=u->left;//更新路径
        }
        else if(a[i]=='R')//右
        {
            if(u->right==NULL)u->right=newnode();//同上
            u=u->right;
        }
    }
}

2. 按遍历建树

        如果题目给出的是整棵树的路径顺序,如整棵树的先序,后序等等,这时候就需要整棵树按照给予的字符串递归建树,类似uva297四分树的指针结构体建树思路。其核心代码如下:

Node* createNode(char* s) { //递归建树 

    if (s[n]=='\0') return NULL; 

    Node* pNode=new Node; 

    if (s[n]=='p') { 
        pNode->type=0; 

        n++; 

        pNode->fch=createNode(s); 

        pNode->sch=createNode(s); 

        pNode->tch=createNode(s); 

        pNode->lch=createNode(s); 
    } 

    else if (s[n]=='f') { 
        pNode->type=1; 

        n++; 
    } 

    else { 
        pNode->type=2; 

        n++; 
    } 

    return pNode; 

} 

        注意:通过全局变量或者引用的使用来改变n的值最为关键!

3. 例题分析

(1)例题一

Problem Description
已知二叉树的一个按先序遍历输入的字符序列,如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该二叉树。

        若题目给出空节点,则只需一个先序字符串就可以建树,然后递归求得中序后序;若求层次遍历,则需要用队列!若不给出空节点,则必须用两个遍历序列的字符串才能建树!

#include <iostream>
#include<queue>
#include<cstdio>
#include<vector>
using namespace std;
struct Node
{
    char ch;
    Node *lefted,*righted;
    Node():ch(0),lefted(NULL),righted(NULL) {}
};
Node *newnode()
{
    return new Node();
};
Node *Root;
Node *build(const char *s,int& p)
{

    char sign=s[p++];
    if(sign==',')
        return NULL;
    else
    {
        Node *root;
        root=newnode();
        root->ch=sign;
        root->lefted=build(s,p);
        root->righted=build(s,p);
        return root;
    }

}
void solveZ(Node *tree)
{
    if(tree)
    {
        solveZ(tree->lefted);
        cout<<tree->ch;
        solveZ(tree->righted);
    }
}
void solveH(Node *tree)
{
    if(tree)
    {
        solveH(tree->lefted);
        solveH(tree->righted);
        cout<<tree->ch;
    }
}
int main()
{
    char name[100];
    while(scanf("%s",name)!=EOF)
    {
        int m=0;
        Root=build(name,m);
        solveZ(Root);
        cout<<endl;
        solveH(Root);
        cout<<endl;
    }
    return 0;
}

(2)例题二

Problem Description
输入二叉树的先序遍历序列和中序遍历序列,输出该二叉树的后序遍历序列。

Input

第一行输入二叉树的先序遍历序列;

第二行输入二叉树的中序遍历序列。

Output

输出该二叉树的后序遍历序列。

Sample Input

ABDCEF

BDAECF

Sample Output

DBEFCA

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char pre_name[100];
char in_name[100];
struct Node
{
    char ch;
    Node *lefted,*righted;
    Node():ch(0),lefted(NULL),righted(NULL) {}
};
Node *Root;
Node *build(int L1,int R1,int L2,int R2)//前序找根,中序分割建树
{
    if(L2>R2)return NULL;
    Node *root;
    root=new Node();
    root->ch=pre_name[L1];
    int p=L2;
    while(in_name[p]!=root->ch)p++;
    int cnt=p-L2;
    root->lefted=build(L1+1,L1+cnt,L2,p-1);
    root->righted=build(L1+cnt+1,R1,p+1,R2);
    return root;
}
void select_post(Node *tree)
{
    if(tree)
    {
        select_post(tree->lefted);
        select_post(tree->righted);
        cout<<tree->ch;
    }
}
int main()
{
    scanf("%s%s",pre_name,in_name);
    int n=strlen(pre_name);
    Root=build(0,n-1,0,n-1);
    select_post(Root);
    cout<<endl;
    return 0;
}

(3)例题三

Problem Description

已知一个按先序输入的字符序列,如abd,,eg,,,cf,,,(其中,表示空结点)。请建立二叉树并求二叉树的层次遍历序列。

Input

输入数据有多行,第一行是一个整数t (t<1000),代表有t行测试数据。每行是一个长度小于50个字符的字符串。

Output

输出二叉树的层次遍历序列。

Sample Input

2
abd,,eg,,,cf,,,
xnl,,i,,u,,

Sample Output

abcdefg
xnuli

#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
char pre_name[100];//如果给出空节点的,则一个序列遍历就可建树,否则要两个序列!且层次遍历用队列,其他遍历用递归即可!
struct Node
{
    char ch;
    Node *lefted,*righted;
    Node():ch(0),lefted(NULL),righted(NULL) {}
};
Node *Root;
Node *build(const char *s,int &p)
{
    char sign=s[p++];
    if(sign==',')
        return NULL;
    else
    {
        Node *root;
        root=new Node();
        root->ch=sign;
        root->lefted=build(s,p);
        root->righted=build(s,p);
        return root;
    }
}
void serch(vector<char>&u)
{
    queue<Node*>que;
    u.clear();
    if(Root)//要考虑根节点为空的情况!!!!
    {
        que.push(Root);
    }
    while(!que.empty())//队列递归求层序遍历!!
    {
        Node *nodes=que.front();
        que.pop();
        u.push_back(nodes->ch);
        if(nodes->lefted!=NULL)que.push(nodes->lefted);
        if(nodes->righted!=NULL)que.push(nodes->righted);
    }
}
int main()
{
    int T;
    cin>>T;
    getchar();
    while(T--)
    {
        scanf("%s",pre_name);
        int m=0;
        Root=build(pre_name,m);
        vector<char>ans;
        serch(ans);
        for(int i=0; i<ans.size(); i++)
            cout<<ans[i];
        cout<<endl;
    }
    return 0;
}

五. 二叉树的层序与宽度

1. 二叉树的层序遍历

1.1 基本概念

        层序遍历就是按照二叉树的层次高低遍历,优先遍历第一层的所有节点,然后遍历第二层等待,以此类推。下图的层序遍历结果为:F CE ADHG BM

二叉树的三种遍历的数据顺序_数据结构树的遍历[通俗易懂]

1.2 实现方式

        利用队列先入先出特点,放入顺序正好按照层序从上至下。

(1)数组方式

void LevelorderTraversal( BinTree BT ){
   int head = 0;
   int last = 0;
   if(BT==NULL)return;
   BinTree NodeList[1000];
   NodeList[last++] = BT;
   while(head<last){
        BinTree node = NodeList[head++];
        printf(" %c",node->Data);
        if(node->Left)
             NodeList[last++] = node->Left;
        if(node->Right)
             NodeList[last++] = node->Right;
   }
}

(2)队列方式

void LevelorderTraversal( BinTree BT ){//²ãÐò±ãÀû
    queue<BinTree> que;
    que.push(BT);
    while(!que.empty()){
        BinTree T = que.front();
        que.pop();
        printf(" %c",T->Data);
        if(!T->Left)que.push(T->Left);
        if(!T->Right)que.push(T->Right);
    }
}

2. 二叉树的宽度

        简而言之,二叉树的宽度是二叉树每一层中的最大节点数。可以结合二叉树层序遍历的特点来求解二叉树的宽度,具体方法如下:

(1)数组记录

        每个节点记录自己所在层数,用数组记录每个层数的节点数,取最值即可。

int getWidth(BTree T){
    memset(sum,0,sizeof(sum));
    queue<BTree> que;
    T->Rank = 1;
    que.push(T);
    int MaxWid = 0;
    while(!que.empty()){
        BTree t = que.front();
        que.pop();
        sum[t->Rank]++;
        MaxWid = max(MaxWid,sum[t->Rank]);
        if(t->lefted!=NULL){
            t->lefted->Rank = t->Rank+1;
            que.push(t->lefted);
        }
        if(t->righted!=NULL){
            t->righted->Rank = t->Rank + 1;
            que.push(t->righted);
        }
    }
    return MaxWid;
}

(2)队列长度

        队列里面只存储当前层节点,队列长度就是当前层节点数目。

int GetWidth(BTree T){
    queue<BTree> que;
    que.push(T);
    int MaxWid = 0;
    while(1){
        int len = que.size();
        MaxWid = max(MaxWid,len);
        if(len==0)break;
        while(len > 0){
            BTree t = que.front();
            que.pop();
            len--;
            if(t->lefted!=NULL)que.push(t->lefted);
            if(t->righted!=NULL)que.push(t->righted);
        }
    }
    return MaxWid;
}

今天的文章二叉树的三种遍历的数据顺序_数据结构树的遍历[通俗易懂]分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/74786.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注