层次遍历创建二叉树

  1. 树种结点的输入顺序:层序创建–>按树的从上至下从左右的顺序输入,各层的空结,点输入数值0。在构造二叉树过程中,需要一个队列暂时存储各结点的地址。
  2. 创建过程:
    1)输入第一个数据:
    若为0,表示是此树为空,将空指针赋值给根指针,树构 造完毕。
    若不为0,动态分配一个结点单元,并存入数据,同时将该结点地址放入队列。
    2)若队列不为空,从队列中取出一个结点地址,并建立该结点的左孩子:
    从输入序列中读入下一数据:
    若读入的数据为0,将出队结点的左孩子指针置空;否则,分配一个结点单元,存入所读数值,并将其置为出队结点的左孩子,同时将此孩子地址入队;
    接着再从输入序列中读入下一个数据:
    若读入的数据为0,将出队结点的右孩子指针置空;否则分配一个结点单元,存入所读数值,并将其置为出队结点的右孩子,同时将此孩子地址入队。
    3)重复 2)过程,直到队列为空,再无结点出队,构造过程到此结束。
    4)返回根结点地址
#include <iostream>
using namespace std;

typedef struct TNode *Position;
typedef Position BinTree;//新定义二叉树类型
typedef ElementType int;
//用0表示没有结点
#define NoInfo 0 

struct TNode{ 
    ElementType data;
    BinTree left;
    BinTree Right;
};

BinTree CreateBinTree(){ 
    ElementType data;
    BinTree BT, T;//BT用来创建新的结点, T用来接收出队结点
    Queue Q = CreateQueue();//创建空队列
    
    //建立第一个结点,即根结点
    scanf("%d", &data);
    
    if(data != NoInfo){ 
        //分配根结点单元,并将结点地址入队
        BT = (BinTree)malloc(sizeof(struct TNode));
        BT->data = data;
        BT->left = BT->Right = NULL;
        
        AddQ(Q, BT);
    }
    else
        return NULL;//若第一个数据是0,就返回空树
    
    while(!IsEmpty(Q)){ //队列不空时,循坏
        T = Delete(Q);//从队列中取出一结点地址
        scanf("%d", &data);//读取T的左孩子
        if(data == NoInfo) 
            T->left = NULL;
        else{ //分配新结点,出队结点的最孩子;新结点入队
            T->left = (BinTree)malloc(sizeof(struct TNode));
            T->left->data = data;
            T->left->left = T->left->right = NULL;
            AddQ(Q, T->left);
        }
        
         scanf("%d", &data);//读取T的右孩子
        if(data == NoInfo) 
            T->right = NULL;
        else{ //分配新结点,出队结点的最孩子;新结点入队
            T->right = (BinTree)malloc(sizeof(struct TNode));
            T->right->data = data;
            T->right->left = T->right->right = NULL;
            AddQ(Q, T->right);
        }
        
    }
    
    return BT;//返回头结点地址
    
}
    原文作者:忧郁猫^
    原文地址: https://blog.csdn.net/weixin_43790360/article/details/108434426
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞