编写一个程序,btree.cpp实现二叉树的基本运算
时间: 2023-11-30 19:40:21 浏览: 153
btree.cpp实现了二叉树的基本运算,包括创建二叉树、查找节点、获取左右子节点、获取二叉树高度等操作。具体实现可以参考以下代码:
```cpp
#include <stdio.h>
#include "btree.h"
// 创建二叉树
void CreateBTNode(BTNode *&b, char *str) {
BTNode *St[MaxSize], *p = NULL;
int top = -1, k, j = 0;
char ch = str[j];
b = NULL;
while (ch != '\0') {
switch (ch) {
case '(':
top++;
St[top] = p;
k = 1;
break;
case ')':
top--;
break;
case ',':
k = 2;
break;
default:
p = (BTNode *) malloc(sizeof(BTNode));
p->data = ch;
p->lchild = p->rchild = NULL;
if (b == NULL) {
b = p;
} else {
switch (k) {
case 1:
St[top]->lchild = p;
break;
case 2:
St[top]->rchild = p;
break;
}
}
}
j++;
ch = str[j];
}
}
// 查找节点
T *FindNode(BTNode *b, T x) {
if (b == NULL) {
return NULL;
} else if (b->data == x) {
return &(b->data);
} else {
T *p;
p = FindNode(b->lchild, x);
if (p != NULL) {
return p;
} else {
return FindNode(b->rchild, x);
}
}
}
// 获取左子节点
T *LchildNode(BTNode *p) {
if (p != NULL && p->lchild != NULL) {
return &(p->lchild->data);
} else {
return NULL;
}
}
// 获取右子节点
T *RchildNode(BTNode *p) {
if (p != NULL && p->rchild != NULL) {
return &(p->rchild->data);
} else {
return NULL;
}
}
// 获取二叉树高度
int BTNodeHeight(BTNode *b) {
if (b == NULL) {
return 0;
} else {
int l = BTNodeHeight(b->lchild);
int r = BTNodeHeight(b->rchild);
return (l > r ? l : r) + 1;
}
}
```
阅读全文