二叉树的创建与遍历（非递归遍历左右中，不破坏树结构）
创建
二叉树的递归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->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);
}
//--------------------分界线--------------------
//取得树中节点个数
void get_node_size1(BinTreeNode* n, int* p){
if (NULL == n)return;
else{
*p = *p + 1;
get_node_size1(n->leftChild, p);
get_node_size1(n->rightChild, p);
}
}
//取得树中节点个数
int get_size1(BinTree* tr){
int size = 0;
get_node_size1(tr->root, &size);
return size;
}
int get_node_size2(BinTreeNode* p){
if(NULL == p) return 0;
else{
return get_node_size2(p->leftChild) + get_node_size2(p->rightChild) + 1;
}
}
int get_size2(BinTree* tr){
return get_node_size2(tr->root);
}
//分别求左右树的高度，哪个高，哪就是树的高度
void get_node_height(BinTreeNode* n, int* p){
if(NULL == n) return;
*p = *p + 1;
int t1 = 0, t2 = 0;
get_node_height(n->leftChild, &t1);
get_node_height(n->rightChild,&t2);
if(t1 > t2)
*p = *p + t1;
else
*p = *p + t2;
}
int get_height(BinTree* tr){
int size = 0;
if(tr->root != NULL) size++;
int t1 = 0, t2 = 0;
get_node_height(tr->root->leftChild, &t1);
get_node_height(tr->root->rightChild, &t2);
return t1 > t2 ? t1 + size : t2 + size;
}
//递归查找节点，如果在左节点找到了，就不需要查找右节点了
BinTreeNode* search_node(BinTreeNode* n, ElemType key){
if (NULL == n || n->data == key){
return n;
}else{
BinTreeNode* tmp;
tmp = search_node(n->leftChild, key);
if(NULL == tmp){
tmp = search_node(n->rightChild, key);
}
return tmp;
}
}
BinTreeNode* search(BinTree* tr, ElemType key){
BinTreeNode* n = NULL;
n = search_node(tr->root, key);
return n;
}
//递归查找父节点，如果父节点的左节点已经为目标节点，就不需要再判断这个父节点的右节点了。
BinTreeNode* get_node_parent(BinTreeNode* n, BinTreeNode* target){
if(NULL == n || NULL == target) return NULL;
if(n->leftChild == target || n->rightChild == target){
return n;
}
else{
BinTreeNode* tmp = NULL;
tmp = get_node_parent(n->leftChild, target);
if(NULL == tmp){
tmp = get_node_parent(n->rightChild, target);
}
return tmp;
}
}
BinTreeNode* get_parent(BinTree* tr, BinTreeNode* target){
get_node_parent(tr->root, target);
}
bool isBintreeEmpty(BinTree* tr){
return NULL == tr->root;
}
void copy_node(BinTreeNode** n1, BinTreeNode* n2){
if(NULL == n2){
*n1 = NULL;
return;
}else{
BinTreeNode* p = (BinTreeNode*)malloc(sizeof(BinTreeNode*));
p->data = n2->data;
*n1 = p;
copy_node(&((*n1)->leftChild), n2->leftChild);
copy_node(&((*n1)->rightChild), n2->rightChild);
}
}
void copy(BinTree* tr1, BinTree* tr2){
copy_node(&(tr1->root), tr2->root);
}
void bintree_node_clear(BinTreeNode** n){
if(NULL == *n)return;
bintree_node_clear(&((*n)->leftChild));
bintree_node_clear(&((*n)->rightChild));
free(*n);
*n = NULL;
}
void bintree_clear(BinTree* tr){
bintree_node_clear(&(tr->root));
// init(tr, '#');
}
//非递归 先中心，再左树，再右树
//利用栈，先进后出
void display_node_clr(BinTreeNode* n){
if(NULL == n){
printf("是空树\n");
return;
}
nodestack stack;
init(&stack);
push(&stack, n);
Node* tmp = NULL;
while(0 != stack.size){
tmp = pop(&stack);
if(NULL == tmp) continue;
printf("%c ", tmp->data->data);
if(tmp->data->rightChild != NULL)
push(&stack, tmp->data->rightChild);
if(tmp->data->leftChild != NULL)
push(&stack, tmp->data->leftChild);
}
}
//非递归 先中心，再左树，再右树
void display_clr(BinTree* tr){
display_node_clr(tr->root);
}
//非递归 先左树，再中心，再右树
//利用栈，先进后出
void display_node_lcr(BinTreeNode* n){
if(NULL == n){
printf("是空树\n");
return;
}
nodestack stack;
init(&stack);
push(&stack, n);
Node* tmp = NULL;
while(0 != stack.size){
tmp = pop(&stack);
if(NULL != tmp->data->leftChild){
if(NULL != tmp->data->rightChild){
push(&stack, tmp->data->rightChild);
}
//中心节点
push(&stack, tmp->data);
push(&stack, tmp->data->leftChild);
}
else{
//再把中心节点pop出来
if(NULL == tmp->data->rightChild){
printf("%c ", tmp->data->data);
//pop出来的tmp为中心节点
tmp = pop(&stack);
if(NULL == tmp)continue;
printf("%c ", tmp->data->data);
}
else{
printf("%c ", tmp->data->data);
push(&stack, tmp->data->rightChild);
}
}
}
}
//非递归 先左树，再中心，再右树
void display_lcr(BinTree* tr){
display_node_lcr(tr->root);
}
//非递归 先左树，再右树，再中心
//利用栈，先进后出
//关键点，把有子树的父节点的tag设置成R。当pop出的节点有子节点，并且此节点的tag为R的话，就说明此节点的子节点已经入栈了，所以直接打印出来。
void display_node_lrc(BinTreeNode* n){
if(NULL == n){
printf("是空树\n");
return;
}
nodestack stack;
init(&stack);
push(&stack, n);
Node* tmp = NULL;
while(0 != stack.size){
tmp = pop(&stack);
if(tmp->tag == R){
printf("%c ", tmp->data->data);
continue;
}
if(NULL != tmp->data->leftChild){
//中心节点
push(&stack, tmp->data);
//把中心节点的属性设置成R
stack.top->tag = R;
if(NULL != tmp->data->rightChild){
push(&stack, tmp->data->rightChild);
}
push(&stack, tmp->data->leftChild);
}
else{
if(NULL == tmp->data->rightChild){
printf("%c ", tmp->data->data);
}
else{
//中心节点
push(&stack, tmp->data);
//把中心节点的属性设置成R
stack.top->tag = R;
push(&stack, tmp->data->rightChild);
}
}
}
}
//非递归 先左树，再右树，再中心
void display_lrc(BinTree* tr){
display_node_lrc(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);
//非递归遍历，中 左 右
display_clr(&tr1);
printf("\n");
//非递归遍历，左 中 右
display_lcr(&tr1);
printf("\n");
//非递归遍历，左 右 中
display_lrc(&tr1);
printf("\n");
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;
}
nodestack.h
#ifndef __NODESTACK__
#define __NODESTACK__
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include <memory.h>
#include <stdbool.h>
struct BinTreeNode;
typedef BinTreeNode* ElemType2;
typedef enum{L, R}Tag;
typedef struct Node{
ElemType2 data;
Tag tag;
struct Node *next;
}Node;
typedef struct nodestack{
int size;
Node *base;
Node *top;
}nodestack;
void init(nodestack*);
void push(nodestack*, ElemType2);
void show_list(nodestack*);
Node* pop(nodestack*);
int length(nodestack*);
void clear(nodestack*);
void destroy(nodestack*);
#endif
nodestack.c
#include "nodestack.h"
Node* createNode(ElemType2 val){
Node* n = (Node*)malloc(sizeof(Node));
n->data = val;
n->tag = L;
n->next = NULL;
return n;
}
void init(nodestack* stack){
stack->size = 0;
stack->top = NULL;
stack->base = NULL;
}
void push(nodestack* stack, ElemType2 x){
Node* n = createNode(x);
//当栈为空的时候
if(stack->base == NULL){
stack->top = stack->base = n;
n->next = NULL;
stack->size++;
return;
}
n->next = stack->top;
stack->top = n;
stack->size++;
}
void show_list(nodestack* stack){
Node* top = stack->top;
while(top != NULL){
printf("%d\n", top->data);
top = top->next;
}
}
Node* pop(nodestack* stack){
if(stack->size == 0)return NULL;
Node* n = stack->top;
stack->top = stack->top->next;
stack->size--;
return n;
}
int length(nodestack* stack){
return stack->size;
}
void clear(nodestack* stack){
Node* top = stack->top;
Node* tmp;
while(top != NULL){
tmp = top;
top = top->next;
free(tmp);
}
stack->top = stack->base = NULL;
stack->size = 0;
}
void destroy(nodestack* stack){
clear(stack);
}