实现二叉树的各种基本运算的算法
题目描述
编写二个程序biree.cpp,实现二叉树的基本运算,并在此基础上设计、exp7-1.cpp 完成以下功能。
(1)由如图7.1所示的二叉树创建对应的二叉链存储结构6,该二叉树的括号表示串为"A(B(D,E(H(J,K(1.MN))))CFGD))"
(2)输出二叉树b。
(3)输出'H'结点的左、右孩子结点值。
(4)输出二叉树6的高度。
(5)释放二叉树b。
算法如下：
btree.cpp程序,其中包含如下函数。
CreateBTree(BTNode*&b,char *str):由括号表示串 str创建二叉链6。
· FindNode(BTNode *b,ElemType x):返回 data 域为x的结点指针
·LchildNode(BTNode*p):返回户结点的左孩子结点指针。
·RchildNode(BTNode*p):返回户结点的右孩子结点指针
·BTHeight(BTNode *b):返回二叉树b的高度。
·DispBTree(BTNode*b):以括号表示法输出二叉树6
·DestroyBTree(BTNode*&b):释放二叉树b的所有结点。
运行代码
btree.cpp
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>#define MaxSize 100
typedef char ElenType;// 定义二叉树节点结构体
typedef struct BiTNode {ElenType data;struct BiTNode* lchild;struct BiTNode* rchild;
} BTNode;// 创建二叉树函数
void CreateBTree(BTNode** b, const char* str) {// 创建一个栈用于存储节点BTNode* St[MaxSize];int top = -1;int k = 0;int j = 0;char ch;// 初始化二叉树为空*b = NULL;ch = str[j];BTNode* p = NULL; // 在这里初始化 pwhile (ch != '\0') {switch (ch) {// 遇到左括号case '(':top++;St[top] = p;k = 1;break;// 遇到逗号case ',':k = 2;break;// 遇到右括号case ')':top--;break;default:// 分配新节点内存p = (BTNode*)malloc(sizeof(BTNode));p->data = ch;p->lchild = p->rchild = NULL;if (*b == NULL) {// 如果是根节点*b = p;}else {// 根据标志 k 判断连接左子树或右子树if (k == 1) {St[top]->lchild = p;}else {St[top]->rchild = p;}}break;}j++;ch = str[j];}
}// 销毁二叉树函数
void DestroyBTree(BTNode** b) {if (*b != NULL) {// 先销毁左子树DestroyBTree(&((*b)->lchild));// 再销毁右子树DestroyBTree(&((*b)->rchild));// 释放当前节点内存free(*b);// 将当前节点置为空指针*b = NULL;}
}
// 查找值为 x 的节点函数
BTNode* FindNode(BTNode* b, ElenType x) {BTNode* p;if (b == NULL) {return NULL;}else if (b->data == x) {return b;}else {// 在左子树中查找p = FindNode(b->lchild, x);if (p != NULL) {return p;}else {// 在右子树中查找return FindNode(b->rchild, x);}}
}// 返回节点 p 的左孩子节点指针函数
BTNode* LchildNode(BTNode* p) {return p->lchild;
}
// 返回节点 p 的右孩子节点指针函数
BTNode* RchildNode(BTNode* p) {return p->rchild;
}
// 求二叉树高度函数
int BiTreeHeight(BTNode* b) {int lchildh, rchildh;if (b == NULL) {return 0;}// 递归求左子树高度lchildh = BiTreeHeight(b->lchild);// 递归求右子树高度rchildh = BiTreeHeight(b->rchild);// 返回较大子树高度加一return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1);
}// 以括号表示法输出二叉树函数
void DispBTree(BTNode* b) {if (b != NULL) {// 输出当前节点数据printf("%c", b->data);if (b->lchild != NULL || b->rchild != NULL) {// 有子树时输出左括号printf("(");// 递归输出左子树DispBTree(b->lchild);if (b->rchild != NULL) {// 有右子树时输出逗号printf(",");}// 递归输出右子树DispBTree(b->rchild);// 有子树时输出右括号printf(")");}}
}excp7-1.cpp
#include <stdio.h>
#include "btree.cpp"
int main() {BTNode* b = NULL;BTNode* p = NULL;BTNode* lp = NULL;BTNode* rp = NULL;printf("二叉树的基本运算如下:\n");printf("(1)创建二叉树\n");CreateBTree(&b, "A(B(D,E(H(J,K(L,M)))),C(F,G(I)))");printf("(2)输出二叉树:");DispBTree(b);printf("\n");printf("(3)查找结点:");p = FindNode(b, 'H');if (p == NULL) {printf("未找到指定节点");}else {lp = LchildNode(p);if (lp != NULL) {printf("左孩子为%c ", lp->data);}else {printf("无左孩子");}rp = RchildNode(p);if (rp != NULL) {printf("右孩子为%c", rp->data);}else {printf("无右孩子");}}printf("\n");printf("(4)二叉树 b 的高度:%d\n", BiTreeHeight(b));printf("(5)释放二叉树 b\n");DestroyBTree(&b);return 0;
}代码思路
-
CreateBTree函数：根据给定的字符串创建二叉树。- 遇到右括号时，弹出栈顶元素。
- 遇到逗号时，设置标志
k为 2，表示接下来的节点为右子树节点。 - 遇到左括号时，将当前节点压入栈中，并设置标志
k为 1，表示接下来的节点为左子树节点。 - 遇到普通字符时，创建新节点，并根据栈的状态和标志
k确定将新节点连接到父节点的左子树或右子树。 - 通过遍历输入字符串，根据不同的字符（左括号、逗号、右括号和普通字符）进行不同的操作。
- 使用栈
St来辅助创建二叉树，栈中存储二叉树节点指针。
-
DestroyBTree函数：销毁二叉树，释放所有节点的内存。采用递归的方式，先销毁左子树，再销毁右子树，最后释放当前节点的内存，并将当前节点指针置为NULL。 -
FindNode函数：在二叉树中查找值为x的节点。- 否则，先在左子树中递归查找，如果左子树中未找到，则在右子树中递归查找。
- 如果当前节点的数据等于
x，则返回当前节点指针。 - 如果二叉树为空，则返回
NULL。
-
直接返回节点的左孩子或右孩子指针。LchildNode和RchildNode函：分别返回给定节点的左孩子节点指针和右孩子节点指。 -
BiTreeHeight函数：求二叉树的高度。- 递归求左子树高度和右子树高度，然后返回较大子树高度加一。
- 如果二叉树为空，则高度为 0。
-
DispBTree函数：以括号表示法输出二叉树。- 最后输出右括号。
- 如果当前节点有右子树，则在输出左子树后输出逗号，再递归输出右子树。
- 如果当前节点有子树，则输出左括号，然后递归输出左子树。
- 如果当前节点不为空，先输出当前节点的数据。