c/c++二叉树的创建与遍历(非递归遍历左右中,破坏树结构)
程序员文章站
2022-06-27 22:32:32
二叉树的创建与遍历(非递归遍历左右中,破坏树结构) 创建 二叉树的递归3种遍历方式: 1,先中心,再左树,再右树 2,先左树,再中心,再右树 3,先左树,再右树,再中心 二叉树的非递归4种遍历方式: 1,先中心,再左树,再右树 2,先左树,再中心,再右树 3,先左树,再右树,再中心 4,层级遍历 二 ......
二叉树的创建与遍历(非递归遍历左右中,破坏树结构)
创建
二叉树的递归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); } //非递归 先左树,再右树,再中心(虽然实现了遍历,但是破坏了树的结构) 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(NULL != tmp->data->leftChild){ //中心节点 push(&stack, tmp->data); if(NULL != tmp->data->rightChild){ push(&stack, tmp->data->rightChild); } push(&stack, tmp->data->leftChild); //把中心节点的左右节点的指针设置成NULL tmp->data->rightChild = tmp->data->leftChild = NULL; } else{ if(NULL == tmp->data->rightChild){ printf("%c ", tmp->data->data); } else{ //中心节点 push(&stack, tmp->data); push(&stack, tmp->data->rightChild); //把中心节点的左右节点的指针设置成NULL tmp->data->rightChild = tmp->data->leftChild = NULL; } } } } //非递归 先左树,再右树,再中心(虽然实现了遍历,但是破坏了树的结构) 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 struct Node{ ElemType2 data; 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->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); }