二叉树的创建与遍历（非递归遍历左右中，不破坏树结构）

创建

二叉树的递归3种遍历方式：

1，先中心，再左树，再右树
2，先左树，再中心，再右树
3，先左树，再右树，再中心

二叉树的非递归4种遍历方式：

1，先中心，再左树，再右树
2，先左树，再中心，再右树
3，先左树，再右树，再中心

4，层级遍历

二叉树的查找，求高度，求个数，求父节点，复制二叉树，释放二叉树

编译方法，用gcc编译不过去，用g++编译，命令如下：
g++ -g nodestack.c nodequeue.c bintree.c bintreemain.c

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);

//二叉树的查找方法1
int get_size1(BinTree* tr);
//二叉树的查找方法2
int get_size2(BinTree* tr);
//求二叉树的高度
int get_height(BinTree* tr);
//查找二叉树
BinTreeNode* search(BinTree* tr, ElemType key);
//求某个节点的父节点
BinTreeNode* get_parent(BinTree* tr, BinTreeNode* p);
//树是否为空
bool isBintreeEmpty(BinTree* tr);
//复制一课二叉树
void copy(BinTree* tr1, BinTree* tr2);
//释放二叉树
void bintree_clear(BinTree* tr);

//先中心，再左树，再右树
void display_clr(BinTree* tr);
//先左树，再中心，再右树
void display_lcr(BinTree* tr);
//先左树，再右树，再中心
void display_lrc(BinTree* tr);
//先左树，再右树，再中心
void display_lrc1(BinTree* tr);

#endif

bintree.c

#include "bintree.h"
#include "nodequeue.h"
#include "nodestack.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