计一个递归算法释放二叉树bt中的所有结点
对应的递归模型如下：
f(BT)=不做任何事情 当BT=NULL时
f(BT)=f(BT->lchild); f(BT)=f(BT->rchild) 其他情况
#include <iostream> using namespace std; //二叉树的结构 typedef struct BTNode { char data; struct BTNode *left; struct BTNode *right; }BTNode; //释放二叉树中所有的结点 void BTFree(BTNode *&BTNode) { if (BTNode!=NULL) { BTFree(BTNode->left); BTFree(BTNode->right); free(BTNode); } } //构建二叉树 //根据先序序列和中序序列递归创建二叉树 BTNode * BTCreate(char a[], char b[], int n) { int k; if (n == 0) { return NULL; } int root = a[0]; BTNode *BT = (BTNode *)malloc(sizeof(BTNode)); BT->data = root; //树根的值可以确定了 for (k = 0; k < n; k++) { //在b中查找b[k]=root的根节点 if (b[k] == root) { break; } } BT->left = BTCreate(a + 1, b, k); //递归创建左子树 BT->right = BTCreate(a + k + 1, b + k + 1, n - k - 1); //递归创建右子树 return BT; } void NOorYES(BTNode *BTNode) { if (BTNode!=NULL) { cout << "yes" << endl; } else { cout << "no" << endl; } } void PreOrder(BTNode *BTNode) { if (BTNode == NULL) return; cout << BTNode->data << " "; PreOrder(BTNode->left); //递归调用，先序遍历左子树 PreOrder(BTNode->right); //递归调用，先序遍历右子树 } int main() { int n = 0; cout << "请输入序列个数" << endl; cin >> n; char *a = new char[n]; cout << "请输入先序序列" << endl; for (int i = 0; i < n; i++) { cin >> a[i]; } char *b = new char[n]; cout << "请输入中序序列" << endl; for (int i = 0; i < n; i++) { cin >> b[i]; } BTNode *BT = NULL; BT = BTCreate(a, b, n); //创建成功 PreOrder(BT); BTFree(BT); system("pause"); return 0; }
