1.递归口是什么,为什么? 2.2i,2i+1,为什么这样设计。 bt->lchild =CreateBTree(str,2i); bt->rchild =CreateBTree(str,2i+1); typedef struct node BTree; typedef struct node{ char data; BTree lchild; BTree rchild; }TNode; BTree CreateBTree(string str,int i){ int len; BTree bt; bt=new TNode; len=str.size(); if(i>len-1 || i<=0) return NULL; if(str[i]=='#') return NULL; bt->data =str[i]; bt->lchild =CreateBTree(str,2i); bt->rchild =CreateBTree(str,2*i+1); return bt; }
时间: 2023-06-09 10:03:36 浏览: 67
1. 递归口是指递归程序中结束递归的条件,通常是判断递归到达了最小的可处理问题,也即递归到了某种边界。在本程序中,递归口是当输入字符串下标i超出范围或为0时,返回空指针(NULL),结束递归。
2. 2i,2i+1 是因为在二叉树中,父节点和其左右子节点的编号关系为:父节点编号i,左子节点编号2i,右子节点编号2i+1。因此在本程序中,创建左子树时传递的是2i,创建右子树时传递的是2i+1,以满足二叉树的结构。
相关问题
```c++ TreeNode* BuildTree(char c[],int s,int e){ //当s==e时,数组只剩一个元素,而且必是操作数值 if(s==e){ TreeNode *node = new TreeNode; node->rChild = node->lChild = NULL; node->val = c[s]; return node; } //从后向前找+- 从后开始遍历纯粹是为了好看 for(int i=e;i>=s;i--){ if(c[i]=='+'||c[i]=='-'){ //这个+-做根节点 TreeNode *node = new TreeNode; node->lChild = node->rChild = NULL;//左右子置空 node->val = c[i];//将操作符赋值给该节点 node->lChild = BuildTree(c,s,i-1);//分开的左子树,s到i-1是+-号左边的那部分 node->rChild = BuildTree(c,i+1,e); //分开的右子树,i+1到e是+-号右边的内容 return node;//返回到上一级给左右子,或者给根 } } for(int j=s;j<=e;j++){ if(c[j]=='*'){ //没有+-后运算符*作根 TreeNode *node = new TreeNode; node->lChild = node->rChild = NULL; node->val = c[j]; node->lChild = BuildTree(c,s,j-1); node->rChild = BuildTree(c,j+1,e); return node; } } for(int j=e;j>=s;j--){ if(c[j]=='/'){ //没有+-后运算符/作根 //因为优先级问题从后面读起 TreeNode *node = new TreeNode; node->lChild = node->rChild = NULL; node->val = c[j]; node->lChild = BuildTree(c,s,j-1); node->rChild = BuildTree(c,j+1,e); return node; } } }将这段代码更改为 c 语言
把代码中的 TreeNode* 替换为 struct TreeNode*,同时需要加上头文件和结构体定义,代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
char val;
struct TreeNode* lChild;
struct TreeNode* rChild;
};
struct TreeNode* BuildTree(char c[], int s, int e) {
//当s==e时,数组只剩一个元素,而且必是操作数值
if (s == e) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->rChild = node->lChild = NULL;
node->val = c[s];
return node;
}
//从后向前找+- 从后开始遍历纯粹是为了好看
for (int i = e; i >= s; i--) {
if (c[i] == '+' || c[i] == '-') {
//这个+-做根节点
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->lChild = node->rChild = NULL; //左右子置空
node->val = c[i]; //将操作符赋值给该节点
node->lChild = BuildTree(c, s, i - 1); //分开的左子树,s到i-1是+-号左边的那部分
node->rChild = BuildTree(c, i + 1, e); //分开的右子树,i+1到e是+-号右边的内容
return node; //返回到上一级给左右子,或者给根
}
}
for (int j = s; j <= e; j++) {
if (c[j] == '*') {
//没有+-后运算符*作根
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->lChild = node->rChild = NULL;
node->val = c[j];
node->lChild = BuildTree(c, s, j - 1);
node->rChild = BuildTree(c, j + 1, e);
return node;
}
}
for (int j = e; j >= s; j--) {
if (c[j] == '/') {
//没有+-后运算符/作根
//因为优先级问题从后面读起
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->lChild = node->rChild = NULL;
node->val = c[j];
node->lChild = BuildTree(c, s, j - 1);
node->rChild = BuildTree(c, j + 1, e);
return node;
}
}
}
```
找出这个代码的错误并进行纠正:#include<stdio.h> #include<malloc.h> #include<conio.h> typedef struct tree { int data; struct tree*lchild; struct tree*rchild; }TREE; typedef struct stack { TREE*t; int flag; struct stack*link; }STACK; int push(STACK**top,TREE*tree) { STACK*p; p=(STACK*)malloc(sizeof(STACK)); p->t=tree; p->link=*top; *top=p; } int pop(STACK**top,TREE**tree) { STACK*p; if(*top==NULL) *tree=NULL; else { *tree=(*top)->t; p=*top; *top=(*top)->link; free(p); } } int SearchNode(TREE*tree, int key, TREE**pkpt, TREE**kpt) { *pkpt=NULL; *kpt=tree; while(*kpt!=NULL) { if((*kpt)->data==key) return 0; *pkpt=*kpt; if(key<(*kpt)->data) *kpt=(*kpt)->lchild; else *kpt=(*kpt)->rchild; } } int InsertNode(TREE**tree,int key) { TREE*p,*q,*r; SearchNode(*tree,key,&p,&q); if(q!=NULL) return 1; if((r=(TREE*)malloc(sizeof(TREE)))==NULL) return-1; r->data=key; r->lchild=r->rchild=NULL; if(p==NULL) *tree=r; else if(p->data>key) p->lchild=r; else p->rchild=r; return 0; } int DeleteNode(TREE**tree,int key) { TREE*p,*q,*r; SearchNode(*tree,key,&p,&q); if(q==NULL) return 1; if(p==NULL) if(q->lchild==NULL) *tree=q->rchild; else { *tree=q->lchild; r=q->lchild; while(r->rchild!=NULL) r=r->rchild; r->rchild=q->rchild; } else if(q->lchild==NULL) if(q==p->lchild) p->lchild=q->rchild; else p->rchild=q->rchild; else { r=q->lchild; r->rchild=q->rchild; if(q==p->lchild) p->lchild=q->lchild; else p->rchild=q->lchild; } free(q); return 0; }
这段代码存在以下错误:
1. push函数和pop函数的返回类型应该为void,因为它们没有返回值。
2. 在SearchNode函数中,如果key小于等于当前节点的值,应该将kpt指向左子节点,不然应该将kpt指向右子节点。
3. 在DeleteNode函数中,当q为要删除的节点时,如果p为NULL,应该将q的左子节点连接到q的右子节点的最左边节点,而不是最右边节点。
下面是修改后的代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct tree {
int data;
struct tree *lchild;
struct tree *rchild;
} TREE;
typedef struct stack {
TREE *t;
int flag;
struct stack *link;
} STACK;
void push(STACK **top, TREE *tree) {
STACK *p;
p = (STACK*)malloc(sizeof(STACK));
p->t = tree;
p->link = *top;
*top = p;
}
void pop(STACK **top, TREE **tree) {
STACK *p;
if(*top == NULL) {
*tree = NULL;
}
else {
*tree = (*top)->t;
p = *top;
*top = (*top)->link;
free(p);
}
}
void SearchNode(TREE *tree, int key, TREE **pkpt, TREE **kpt) {
*pkpt = NULL;
*kpt = tree;
while(*kpt != NULL) {
if((*kpt)->data == key) {
return;
}
*pkpt = *kpt;
if(key <= (*kpt)->data) {
*kpt = (*kpt)->lchild;
}
else {
*kpt = (*kpt)->rchild;
}
}
}
int InsertNode(TREE **tree, int key) {
TREE *p, *q, *r;
SearchNode(*tree, key, &p, &q);
if(q != NULL) {
return 1;
}
if((r = (TREE*)malloc(sizeof(TREE))) == NULL) {
return -1;
}
r->data = key;
r->lchild = r->rchild = NULL;
if(p == NULL) {
*tree = r;
}
else if(p->data > key) {
p->lchild = r;
}
else {
p->rchild = r;
}
return 0;
}
int DeleteNode(TREE **tree, int key) {
TREE *p, *q, *r;
SearchNode(*tree, key, &p, &q);
if(q == NULL) {
return 1;
}
if(p == NULL) {
if(q->lchild == NULL) {
*tree = q->rchild;
}
else {
*tree = q->lchild;
r = q->lchild;
while(r->rchild != NULL) {
r = r->rchild;
}
r->rchild = q->rchild;
}
}
else if(q->lchild == NULL) {
if(q == p->lchild) {
p->lchild = q->rchild;
}
else {
p->rchild = q->rchild;
}
}
else {
r = q->lchild;
r->rchild = q->rchild;
if(q == p->lchild) {
p->lchild = q->lchild;
}
else {
p->rchild = q->lchild;
}
}
free(q);
return 0;
}
```