问题描述

非递归利用队列创建二叉树

BinTree create_BinTree( TElemType endTag, TElemType arr[], int n ) {

BinTNode* T = new BinTNode;

if( T == NULL ) {
    cerr<<"存储分配失败!"<<endl;
    exit( 1 );
}
InitBTree( T );
LinkQueue Q;
InitQueue( Q );
BinTNode *p = NULL;
EnQueue( Q, T );
int i = 0;
while( i < n ) {
    DeQueue( Q, p );
    if( arr[i] != endTag ) {
        p->data = arr[i];
        p->left_child  = new BinTNode;
        p->right_child = new BinTNode;
        if( p->left_child == NULL || p->right_child == NULL ) {
            cerr<<"存储分配失败!"<<endl;
            exit( 1 );
        }
        //cout << T->data <<endl;
        EnQueue( Q, p->left_child );
        EnQueue( Q, p->right_child );
    }
    else {
        p = NULL;
    }
    i++;
}
//cout << T->data << endl;
return T;

};
非递归利用队列层序创建二叉树为什么返回的结点是最后一个结点的地址？

全部代码在下边：
#include
#include
typedef char TElemType;
typedef struct node {
TElemType data;
struct node *left_child;
struct node *right_child;
}BinTNode, *BinTree;

typedef BinTNode *QElemType;

typedef struct Node {
QElemType data;
struct Node *link;
} LinkNode;

typedef struct {
LinkNode *front, *rear;
} LinkQueue;

void InitQueue( LinkQueue &Q );
bool EnQueue( LinkQueue &Q, QElemType x );
bool DeQueue( LinkQueue &Q, QElemType &x );
//QElemType DeQueue( LinkQueue &Q );
void InitBTree( BinTree T ) {
T = NULL;
};

BinTree create_BinTree( TElemType endTag, TElemType arr[], int n ) {

BinTNode* T = new BinTNode;

if( T == NULL ) {
    cerr<<"存储分配失败!"<<endl;
    exit( 1 );
}
InitBTree( T );
LinkQueue Q;
InitQueue( Q );
BinTNode *p = NULL;
EnQueue( Q, T );
int i = 0;
while( i < n ) {
    DeQueue( Q, p );
    if( arr[i] != endTag ) {
        p->data = arr[i];
        p->left_child  = new BinTNode;
        p->right_child = new BinTNode;
        if( p->left_child == NULL || p->right_child == NULL ) {
            cerr<<"存储分配失败!"<<endl;
            exit( 1 );
        }
        //cout << T->data <<endl;
        EnQueue( Q, p->left_child );
        EnQueue( Q, p->right_child );
    }
    else {
        p = NULL;
    }
    i++;
}
//cout << T->data << endl;
return T;

};

/*
*前序遍历
*/
void PreOrder( BinTNode *T ) {
if( T != NULL ) {
cout<data<
PreOrder( T->left_child );
PreOrder( T->right_child );
}
};

/*
void PreOrder_S( BinTNode *T ) {
SeqStack S;
InitStack( S );
BinTNode *p = T;
Push( S, NULL );
while( p != NULL ) {
cout<< p->data <
if( p->right_child != NULL )
Push( S, p->right_child );
if( p->left_child != NULL )
p = p->left_child;
else
Pop( S, p );
}
};
*/

/*
*中序遍历
*/
void InOrder( BinTNode *T ) {
if( T!= NULL ) {
InOrder( T->left_child );
cout<< T->data << endl;
InOrder( T->right_child );
}
};

void InitQueue( LinkQueue &Q ) {

//书上的
/*
Q = new LinkNode;
if( Q == NULL ) {
    cerr<<"存储分配失败"<<endl;
    exit(1);
}
Q.front = Q.rear = Q;
*/

//我的
Q.front = Q.rear = new LinkNode;
if( !Q.front ) {
    cerr<<"存储分配失败"<<endl;
    exit(1);
}
Q.front->link = NULL;

}

bool EnQueue( LinkQueue &Q, QElemType x ) {
Q.rear->link = new LinkNode;
if( Q.rear->link == NULL ) {
cerr<<"存储分配失败"<
exit(1);
}
Q.rear = Q.rear->link;
Q.rear->data = x;
Q.rear->link = NULL;

return true;

}

bool DeQueue( LinkQueue &Q, QElemType &x ) {
if( Q.front->link == NULL )
return false;
LinkNode p = Q.front->link;
x = p->data;
Q.front->link = p->link;
delete p;
return true;
}
/

QElemType DeQueue( LinkQueue &Q ) {
QElemType x;
if( Q.front->link == NULL )
return NULL;
LinkNode *p = Q.front->link;
x = p->data;
Q.front->link = p->link;
delete p;
return x;
}
*/
bool QueueEmpty( LinkQueue &Q ) {
return Q.front->link == NULL;
}

void LevelOrder( BinTree BT ) {
LinkQueue Q;
InitQueue( Q );
BinTNode *p = BT;
EnQueue( Q , p );
while( !QueueEmpty ( Q ) ) {
DeQueue( Q, p );
cout << p->data << endl;
if( p->left_child != NULL ) EnQueue( Q, p->left_child );
if( p->right_child != NULL ) EnQueue( Q, p->right_child);
}
};
int main() {
TElemType endTag = '#';
//BinTNode T;
//BinTree root = &T;
//InitBTree( root );

TElemType arr[15] = { '1', '2', '3', '4', '5', '6', '7', '#', '#', '#', '#', '#', '#', '#', '#' };
//TElemType arr[7] = { '1', '2', '4', '5', '3', '6', '7' };
BinTree root = create_BinTree( endTag, arr, 15 );
cout << "层序遍历二叉树:"<<endl;
LevelOrder( root );

}