精选_二叉树应用_源码打包

# 二叉树应用 # 1 项目要求 - 建立一棵二叉树 - 前序、中序、层次非递归遍历该二叉树 - 判断该二叉树是否为二叉排序树 - 如果是二叉排序树，进行结点的插入或删除 - 输出结果 # 2 解题思路 首先设计一个结构体，确定需要输入的数据类型，再设计一个结构体，用来存放左右孩子的指针。输入数据建立一个二叉树，首先输入左子树的数据，以‘0’以表示最后的数据作为叶子结点，再输入右子树，并以同样的方式结尾，构成二叉树。接下来进行二叉树的非递归的先序、中序、层次遍历。然后判断该树是否为二叉排序树，则先判断是否是空树，是则不是二叉排序树，不是则递归调用并且遍历左子树，检查左子树是否符合二叉排序树，一旦发现有数据大于根节点，则不是二叉排序树；若没有，则遍历右子树，检查右子树是否符合二叉排序树特征，有发现数据小于根节点，则不是二叉排序树，如果两者都不是，此二叉树就是二叉排序树。在判断为二叉排序树后，调用查找函数，插入数据，以及删除数据。 # 3 函数调用图  # 4 数据介绍 ## 4.1 各函数功能 ```c++ // 创建二叉树 int createTree(BitTree *T); // 非递归先序遍历 int preOrder(BitTree T); // 非递归先序遍历 int preOrder(BitTree T); // 非递归层次遍历 int levelPrint(BitTree T); // 判断是否为二叉树 int judge(BitTree T); // 查找节点 int searchBst(BitTree T, BitTree G, Elemtype key, BitTree *p); // 二叉排序树插入 int insertBst(BitTree T, Elemtype key); // 删除二叉排序树 int deleteBst(BitTree *T, int key); // 删除节点 int Delete(BitTree *p); // 主函数，流程控制 int main(); ``` # 5 测试           # 6 源代码 ```c++ # include<stdio.h> # include<stdlib.h> # include<malloc.h> # include<stdbool.h> typedef int Elemtype; typedef struct { Elemtype e; }Elem; typedef struct BitTree { Elem data; /*定义数据*/ struct BitTree *lChild, *rChild; /*定义左右孩子指针*/ }BitNode, *BitTree; BitNode *T = NULL; int createTree(BitTree *T) { /*创建二叉树*/ Elemtype ch; scanf("%d", &ch); if(ch == 0) { /*0表示空树*/ *T = NULL; } else { *T = (BitTree)malloc(sizeof(BitNode)); if (!T) { exit(1); } (*T) -> data.e = ch; /*生成根节点*/ createTree(&(*T) -> lChild); /*构造左子树*/ createTree(&(*T) -> rChild); /*构造右子树*/ } return 1; } int preOrder(BitTree T) { /*非递归先序遍历*/ BitTree stack[100]; /*基于栈进行遍历*/ int front = 0, rear = 0; BitNode *p; if(T != NULL) { stack[rear] = T; /*将根节点入栈*/ rear = (rear + 1) % 100; } while (front != rear) { p = stack[front]; front = (front + 1) % 100; printf("%5d", p -> data); /*输出节点*/ if(p -> lChild != NULL) { /*左子树不为空就输出左子树*/ stack[rear] = p -> lChild; /*左子树入栈*/ rear = (rear + 1) % 100; } if(p -> rChild != NULL) { /*最后是右子树*/ stack[rear] = p -> rChild; /*右子树入栈*/ rear = (rear + 1) % 100; } } return; } int inOrder(BitTree T) { /*非递归中序遍历*/ BitNode *stack[100]; int top; BitNode *p; top = 0; p = T; while(p != NULL || top > 0) { while(p != NULL) { /*遍历到最左端的节点*/ stack[top++] = p; p = p -> lChild; } if(top > 0) { /*出栈，选择当前节点的右子树*/ p = stack[--top]; printf("%5d", p -> data); p = p -> rChild; } } } int levelPrint(BitTree T) { /*非递归层次遍历*/ BitTree queue[100]; BitNode *p; int front = -1, rear = -1; rear++; queue[rear] = T; while(front != rear) { front = (front + 1) % 100; p = queue[front]; printf("%5d", p -> data); if(p -> lChild != NULL) { rear = (rear + 1) % 100; queue[rear] = p -> lChild; } if(p -> rChild != NULL) { rear = (rear + 1) % 100; queue[rear] = p -> rChild; } } } int judge(BitTree T) { /*判断是否为二叉树*/ if(!T) { /*返回1代表是二叉排序树*/ return 1; } else if(!(T -> lChild)&&!(T -> rChild)) { /*左右子树都没有*/ return 1; } else if((T -> lChild)&&!(T -> rChild)) { /*只有左子树*/ if((T->lChild->data.e)>(T->data.e)) { return 0; /*返回0代表无二叉树*/ } else { return(judge(T -> lChild)); /*继续寻找子节点*/ } } else if(!(T -> lChild)&&(T -> rChild)) { /*只有右子树*/ if((T->rChild -> data.e) < (T -> data.e)) { return 0; } else { return(judge(T -> rChild)); } } else { /*如果左右子树都存在*/ if((T -> lChild -> data.e) > (T -> data.e)||(T -> rChild -> data.e) < (T -> data.e)) { return 0; } else { return (judge(T -> lChild) && judge(T -> rChild)); } } } int searchBst(BitTree T, BitTree G, Elemtype key, BitTree *p) { /*查找节点*/ if(!T) { /*判断原树是否存在*/ *p = G; return 0; } else if(key == T -> data.e) { *p = T; return 1; } else if(key < T -> data.e) { return searchBst(T -> lChild, T, key, p); } else { return searchBst(T -> rChild, T, key, p); } return 1; } int insertBst(BitTree T, Elemtype key) { /*二叉排序树插入*/ BitTree p, N; if(searchBst(T, NULL, key, &p)) { return 0; } else { N = (BitTree)malloc(sizeof(BitNode)); N -> data.e = key; N -> lChild = NULL; N -> rChild = NULL; if(!p) { T = N; } else if(key < p -> data.e) { p -> lChild = N; } else { p -> rChild = N; } } return 1; } int deleteBst(BitTree *T, int key) { /*删除二叉排序树*/ if(!(*T)) { return 0; } else { if(key == (*T) -> data.e) { Delete(T); /*找到指定节点，删除*/ } else if(key < (*T) -> data.e) { return deleteBst(&(*T)->lChild, key); } else { return deleteBst(&(*T)->rChild, key); } } } int Delete(BitTree *p) { /*删除节点*/ BitTree q, N; if(!(*p) -> lChild && !(*p) -> rChild) { *p = NULL; } else if(!(*p) -> lChild) { q = *p; free(q); } else i