【二叉树的创建与遍历】

二叉树是由一个根结点和两棵互不相交的、分别称为左右子树的二叉树组成

结构体定义：

// 定义树中的结点结构
typedef struct BTNode {

    char element;
    struct BTNode left;
    struct BTNode right;
}*BTNodePtr,BTNode;
// 循环队列表示结点顺序
typedef struct BTNodePtrQueue {
    BTNodePtr* nodePtrs;
    int front;
    int rear;
}BTNodePtrQueue,*QueuePtr;

队列的初始化：

QueuePtr initQueue() {
    QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(QueuePtr));
    resultQueuePtr->nodePtrs = (BTNodePtr*)malloc(sizeof(BTNodePtr)*QUEUE_SIZE);
    resultQueuePtr->front = 0;
    resultQueuePtr->rear = 1;
    return resultQueuePtr;
}

判断队列是否为空：

int isQueueEmpty(QueuePtr paraQueuePtr) {
    if((paraQueuePtr->front+1)%QUEUE_SIZE==(paraQueuePtr->rear)){
        return 1;
    }
    return 0;
}

结点入队：

void enqueue(QueuePtr paraQueuePtr,BTNodePtr paraBTNodePtr){
    printf("front=%d,rear=%drn",paraQueuePtr->front,paraQueuePtr->rear);
    if((paraQueuePtr->rear+1)%QUEUE_SIZE==paraQueuePtr->front%QUEUE_SIZE){
        printf("error,trying to enqueue %c,queue fullrn",paraBTNodePtr->element);
        return;
    }
    paraQueuePtr->nodePtrs[paraQueuePtr->rear]=paraBTNodePtr;
    paraQueuePtr->rear=(paraQueuePtr->rear+1)%QUEUE_SIZE;
    printf("enqueue %c endsrn",paraBTNodePtr->element);   
}

结点出队，并返回该结点：

BTNodePtr dequeue(QueuePtr paraQueuePtr){
    if(isQueueEmpty(paraQueuePtr)){
        printf("Error,empty queuern");
        return NULL;
    }
    paraQueuePtr->front = (paraQueuePtr->front+1)%QUEUE_SIZE;

    printf("dequeue %c endsrn",paraQueuePtr->nodePtrs[paraQueuePtr->front]->element);
    return paraQueuePtr->nodePtrs[paraQueuePtr->front];
}

构造一个结点：

BTNodePtr constructBTNode(char paraChar){
    BTNodePtr resultPtr = (BTNodePtr)malloc(sizeof(BTNode));
    resultPtr->element = paraChar;
    resultPtr->left = NULL;
    resultPtr->right = NULL;
    return resultPtr;
}

将字符串转化为二叉树：

BTNodePtr StringToBTree(char* paraString){
    int i=0;
    char ch;
    QueuePtr tempQueuePtr = initQueue();
    BTNodePtr resultHeader;
    BTNodePtr tempParent,tempLeftChild,tempRightChild;

    ch = paraString[i];
    resultHeader = constructBTNode(ch);
    enqueue(tempQueuePtr,resultHeader);

    while(!isQueueEmpty(tempQueuePtr)){
        tempParent = dequeue(tempQueuePtr);
        i++;
        ch=paraString[i];

        if(ch=='#'){
            tempParent->left=NULL;
        }else{
            tempLeftChild=constructBTNode(ch);
            enqueue(tempQueuePtr,tempLeftChild);
            tempParent->left=tempLeftChild;
        }

        i++;
        ch = paraString[i];

        if(ch == '#'){
            tempParent->right=NULL;
        }else{
            tempRightChild=constructBTNode(ch);
            enqueue(tempQueuePtr,tempRightChild);
            tempParent->right=tempRightChild;
        }
    }
    return resultHeader;
}

遍历：
1、层序遍历：从根结点开始访问，利用队列从上而下逐层遍历，再同一层中，按从左到右的顺序对结点逐个访问
2、前序遍历：先访问根节点，然后前序遍历左子树，再前序遍历右子树
3、中序遍历：先中序遍历根结点的左子树，再访问根结点，最后中序遍历右子树
4、后序遍历：按照从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点

// 层次遍历
void levelwise(BTNodePtr paraTreePtr){
    char tempString[100];
    int i;
    QueuePtr tempQueuePtr=initQueue();
    BTNodePtr tempNodePtr;
    enqueue(tempQueuePtr,paraTreePtr);

    while(!isQueueEmpty(tempQueuePtr)){
        tempNodePtr=dequeue(tempQueuePtr);
        tempString[i]=tempNodePtr->element;
        i++;

        if(tempNodePtr->left!=NULL){
            enqueue(tempQueuePtr,tempNodePtr->left);
        }

        if(tempNodePtr->right!=NULL){
            enqueue(tempQueuePtr,tempNodePtr->right);
        }
    }
    tempString[i]='';
    printf("Leverwise:%srn",tempString);
}
// 前序遍历
void preorder(BTNodePtr tempPtr){
    if(tempPtr==NULL){
        return;
    }
    printf("%c",tempPtr->element);
    preorder(tempPtr->left);
    preorder(tempPtr->right);
}
// 中序遍历
void inorder(BTNodePtr tempPtr){
    if(tempPtr==NULL){
        return;
    }
    inorder(tempPtr->left);
    printf("%c",tempPtr->element);
    inorder(tempPtr->right);
}
// 后序遍历
void postorder(BTNodePtr tempPtr){
    if(tempPtr==NULL){
        return;
    }
    postorder(tempPtr->left);
    postorder(tempPtr->right);
    printf("%c",tempPtr->element);
}

总代码：

#include
#include

#define QUEUE_SIZE 5
// 定义树中的结点结构
typedef struct BTNode {

    char element;
    struct BTNode left;
    struct BTNode right;
}*BTNodePtr,BTNode;
// 循环队列表示结点顺序
typedef struct BTNodePtrQueue {
    BTNodePtr* nodePtrs;
    int front;
    int rear;
}BTNodePtrQueue,*QueuePtr;
// 队列的初始化
QueuePtr initQueue() {
    QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(QueuePtr));
    resultQueuePtr->nodePtrs = (BTNodePtr*)malloc(sizeof(BTNodePtr)*QUEUE_SIZE);
    resultQueuePtr->front = 0;
    resultQueuePtr->rear = 1;
    return resultQueuePtr;
}
// 判断队列是否为空
int isQueueEmpty(QueuePtr paraQueuePtr) {
    if((paraQueuePtr->front+1)%QUEUE_SIZE==(paraQueuePtr->rear)){
        return 1;
    }
    return 0;
}
// 结点入队
void enqueue(QueuePtr paraQueuePtr,BTNodePtr paraBTNodePtr){
    printf("front=%d,rear=%drn",paraQueuePtr->front,paraQueuePtr->rear);
    //判断队列是否满了
    if((paraQueuePtr->rear+1)%QUEUE_SIZE==paraQueuePtr->front%QUEUE_SIZE){
        printf("error,trying to enqueue %c,queue fullrn",paraBTNodePtr->element);
        return;
    }
    //添加结点
    paraQueuePtr->nodePtrs[paraQueuePtr->rear]=paraBTNodePtr;
    paraQueuePtr->rear=(paraQueuePtr->rear+1)%QUEUE_SIZE;
    printf("enqueue %c endsrn",paraBTNodePtr->element);   
}
// 结点出队，并返回该结点
BTNodePtr dequeue(QueuePtr paraQueuePtr){
    if(isQueueEmpty(paraQueuePtr)){
        printf("Error,empty queuern");
        return NULL;
    }
    paraQueuePtr->front = (paraQueuePtr->front+1)%QUEUE_SIZE;

    printf("dequeue %c endsrn",paraQueuePtr->nodePtrs[paraQueuePtr->front]->element);
    return paraQueuePtr->nodePtrs[paraQueuePtr->front];
}
// 构造一个结点
BTNodePtr constructBTNode(char paraChar){
    BTNodePtr resultPtr = (BTNodePtr)malloc(sizeof(BTNode));
    resultPtr->element = paraChar;
    resultPtr->left = NULL;
    resultPtr->right = NULL;
    return resultPtr;
}
// 将字符串转化为二叉树
BTNodePtr StringToBTree(char* paraString){
    int i=0;
    char ch;
    QueuePtr tempQueuePtr = initQueue();
    BTNodePtr resultHeader;
    BTNodePtr tempParent,tempLeftChild,tempRightChild;

    ch = paraString[i];
    resultHeader = constructBTNode(ch);
    enqueue(tempQueuePtr,resultHeader);

    while(!isQueueEmpty(tempQueuePtr)){
        tempParent = dequeue(tempQueuePtr);
        i++;
        ch=paraString[i];

        if(ch=='#'){
            tempParent->left=NULL;
        }else{
            tempLeftChild=constructBTNode(ch);
            enqueue(tempQueuePtr,tempLeftChild);
            tempParent->left=tempLeftChild;
        }

        i++;
        ch = paraString[i];

        if(ch == '#'){
            tempParent->right=NULL;
        }else{
            tempRightChild=constructBTNode(ch);
            enqueue(tempQueuePtr,tempRightChild);
            tempParent->right=tempRightChild;
        }
    }
    return resultHeader;
}
// 层次遍历
void levelwise(BTNodePtr paraTreePtr){
    char tempString[100];
    int i;
    QueuePtr tempQueuePtr=initQueue();
    BTNodePtr tempNodePtr;
    enqueue(tempQueuePtr,paraTreePtr);

    while(!isQueueEmpty(tempQueuePtr)){
        tempNodePtr=dequeue(tempQueuePtr);
        tempString[i]=tempNodePtr->element;
        i++;

        if(tempNodePtr->left!=NULL){
            enqueue(tempQueuePtr,tempNodePtr->left);
        }

        if(tempNodePtr->right!=NULL){
            enqueue(tempQueuePtr,tempNodePtr->right);
        }
    }
    tempString[i]='';
    printf("Leverwise:%srn",tempString);
}
// 前序遍历
void preorder(BTNodePtr tempPtr){
    if(tempPtr==NULL){
        return;
    }
    printf("%c",tempPtr->element);
    preorder(tempPtr->left);
    preorder(tempPtr->right);
}
// 中序遍历
void inorder(BTNodePtr tempPtr){
    if(tempPtr==NULL){
        return;
    }
    inorder(tempPtr->left);
    printf("%c",tempPtr->element);
    inorder(tempPtr->right);
}
// 后序遍历
void postorder(BTNodePtr tempPtr){
    if(tempPtr==NULL){
        return;
    }
    postorder(tempPtr->left);
    postorder(tempPtr->right);
    printf("%c",tempPtr->element);
}
int main(){
	BTNodePtr tempHeader;
	tempHeader = constructBTNode('c');
	printf("There is only one node. Preorder visit: ");
	preorder(tempHeader);
	printf("rn");

	char* tempString = "acde#bf######";

	tempHeader = stringToBTree(tempString);
	printf("Preorder: ");
	preorder(tempHeader);
	printf("rn");
	printf("Inorder: ");
	inorder(tempHeader);
	printf("rn");
	printf("Postorder: ");
	postorder(tempHeader);
	printf("rn");
	printf("Levelwise: ");
	levelwise(tempHeader);
	printf("rn");

	return 1;
}

我们用图形的方式表现树的结构，非常直观容易理解，但对于计算机来说，它只会处理线性序列，上面的四种遍历方法，其实是在把树中的结点变成某种意义上的线性序列，这就给程序的实现带来了好处