二叉树的创建与遍历

二叉树的创建与遍历

创建

二叉树的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*);

#endif

nodequeue.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;
}