二叉樹的創建與遍歷 創建 二叉樹的4種遍歷方式： 1，先中心，再左樹，再右樹 2，先左樹，再中心，再右樹 3，先左樹，再右樹，再中心 4，層級遍歷 bintree.h bintree.c bintreemain.c nodequeue.h nodequeue.c ...
二叉樹的創建與遍歷
創建
二叉樹的4種遍歷方式：
1，先中心，再左樹，再右樹
2，先左樹，再中心，再右樹
3，先左樹，再右樹，再中心
4，層級遍歷
bintree.h
#ifndef __BINTREE__
#define __BINTREE__
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#define ElemType char
typedef struct BinTreeNode{
ElemType data;
struct BinTreeNode* leftChild;
struct BinTreeNode* rightChild;
}BinTreeNode;
typedef struct BinTree{
BinTreeNode* root;
ElemType ref;
}BinTree;
void init(BinTree* tr, ElemType val);
void createBinTree(BinTree* bt);
void createBinTree_str(BinTree* bt, char** str);
//先中心，再左樹，再右樹
void show_clr(BinTree* tr);
//先左樹，再中心，再右樹
void show_lcr(BinTree* tr);
//先左樹，再右樹，再中心
void show_lrc(BinTree* tr);
//層級遍歷
void show_level(BinTree* tr);
#endif
bintree.c
include "bintree.h"
#include "nodequeue.h"
void init(BinTree* tr, ElemType val){
tr->root = NULL;
tr->ref = val;
}
void createRoot(BinTree* bt, BinTreeNode** t){
ElemType item;
scanf("%c", &item);
if(item == bt->ref){
*t = NULL;
}
else{
*t = (BinTreeNode*)malloc(sizeof(BinTreeNode));
assert(*t != NULL);
(*t)->data = item;
createRoot(bt, &((*t)->leftChild));
createRoot(bt, &((*t)->rightChild));
}
}
void createBinTree(BinTree* bt){
createRoot(bt, &(bt->root));
}
void createNode_str(BinTree* bt, BinTreeNode** t, char** str){
if(**str == '\0'){
return;
}
if(**str == bt->ref){
*t = NULL;
*str = *str + 1;
}
else{
*t = (BinTreeNode*)malloc(sizeof(BinTreeNode));
(*t)->data = **str;
*str = *str + 1;
createNode_str(bt, &((*t)->leftChild), str);
createNode_str(bt, &((*t)->rightChild), str);
}
}
void createBinTree_str(BinTree* bt, char** str){
createNode_str(bt, &(bt->root), str);
}
//先中心，再左樹，再右樹
void show_node_clr(BinTreeNode* n){
if(NULL == n)return;
else{
printf("%c ", n->data);
show_node_clr(n->leftChild);
show_node_clr(n->rightChild);
}
}
//先中心，再左樹，再右樹
void show_clr(BinTree* tr){
show_node_clr(tr->root);
}
//先左樹，再中心，再右樹
void show_node_lcr(BinTreeNode* n){
if(NULL == n)return;
else{
show_node_lcr(n->leftChild);
printf("%c ", n->data);
show_node_lcr(n->rightChild);
}
}
//先左樹，再中心，再右樹
void show_lcr(BinTree* tr){
show_node_lcr(tr->root);
}
//先左樹，再右樹，再中心
void show_node_lrc(BinTreeNode* n){
if(NULL == n)return;
else{
show_node_lrc(n->leftChild);
show_node_lrc(n->rightChild);
printf("%c ", n->data);
}
}
//先左樹，再右樹，再中心
void show_lrc(BinTree* tr){
show_node_lrc(tr->root);
}
//層級遍歷,利用隊列原理，先進先出
void show_node_level(BinTreeNode* n){
if(NULL == n) return;
NodeQueue queue;
init_queue(&queue);
enQueue(&queue, n);
BinTreeNode* tmp;
while(!isQueueEmpty(&queue)){
if(getHead(&queue) == NULL)break;
tmp = getHead(&queue)->data;
deQueue(&queue);
printf("%c ", tmp->data);
if(tmp->leftChild != NULL)
enQueue(&queue, tmp->leftChild);
if(tmp->rightChild != NULL)
enQueue(&queue, tmp->rightChild);
}
printf("\n");
}
//層級遍歷
void show_level(BinTree* tr){
show_node_level(tr->root);
}
bintreemain.c
#include "bintree.h"
int main(){
BinTree tr;
init(&tr, '#');
//ABC##DE##F##G##H##
//createBinTree(&tr);
char* a = "ABC##DE##F##G#H##";
//char* a = "AB##C##";
BinTree tr1;
init(&tr1, '#');
createBinTree_str(&tr1, &a);
show_clr(&tr1);
printf("\n");
show_lcr(&tr1);
printf("\n");
show_lrc(&tr1);
printf("\n");
show_level(&tr1);
return 0;
}
nodequeue.h
#ifndef __NODEQUEUE__
#define __NODEQUEUE__
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include <memory.h>
#include <stdbool.h>
struct BinTreeNode;
#define ElemType1 BinTreeNode*
typedef struct Node{
ElemType1 data;
struct Node* next;
}Node;
typedef struct NodeQueue{
Node* front;
Node* tail;
size_t size;
}NodeQueue;
void init_queue(NodeQueue*);
void enQueue(NodeQueue*, ElemType1);
void deQueue(NodeQueue*);
void show_list(NodeQueue*);
int length(NodeQueue*);
void clear(NodeQueue*);
void destroy(NodeQueue*);
Node* getHead(NodeQueue*);
bool isQueueEmpty(NodeQueue*);
#endifnodequeue.c
#include "nodequeue.h"
void init_queue(NodeQueue* queue){
queue->front = queue->tail = (Node*)malloc(sizeof(Node));
queue->tail->next = NULL;
queue->size = 0;
}
//入隊(尾插)
void enQueue(NodeQueue* queue, ElemType1 val){
Node* p = (Node*)malloc(sizeof(Node));
p->data = val;
if(queue->front->next == NULL){
queue->front->next = p;
}
else{
queue->tail->next = p;
}
queue->tail = p;
p->next = NULL;
queue->size++;
}
//出隊(頭刪)
void deQueue(NodeQueue* queue){
if(queue->size == 0)return;
Node* tmp = queue->front->next;
queue->front->next = queue->front->next->next;
free(tmp);
queue->size--;
}
nt length(NodeQueue* queue){
return queue->size;
}
void show_list(NodeQueue* queue){
Node* p = queue->front;
while(p->next != NULL){
printf("%d\n", p->next->data);
p = p->next;
}
}
void clear(NodeQueue* queue){
if(queue->size == 0)return;
Node* p = queue->front;
Node* tmp;
while(p->next != NULL){
tmp = p->next;
p = p->next;
free(tmp);
}
queue->tail = queue->front;
queue->tail->next = NULL;
queue->size = 0;
}
void destroy(NodeQueue* queue){
clear(queue);
free(queue->front);
}
Node* getHead(NodeQueue* queue){
return queue->front->next;
}
bool isQueueEmpty(NodeQueue* queue){
return queue->front == queue->tail;
}
