层次遍历创建二叉树

àì夳堔傛蜴生んèń 2022-12-04 07:49 183阅读 0赞

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;//返回头结点地址
        
    }