bitree BuTrPM ( sqlist s1, sqlist s2){ intj ,l1,I2,h1,h2; char c ; node * p ; I1=s1.low;l2=s2.low;h1=s1.high;h2=s2.high; if (l1>h1||l2>h2) return (0); c =s1.ch[s1.low]; p = new ( node ); p -> data = c ; for ( j =s2.low; j <=s2.high: j ++) if ( c ==s2.ch[ j ]) break ; s1.low=l1+1;s1.high=l1+ j -l2;s2.low=l2;s2.high= j -1; p -> Ichild = BuTrPM (s1,s2); s1.low=l1+ j -l2+1;s1.high=h1;s2.low= j +1;s2.high=h2; p -> rchild = BuTrPM (s1,s2); return ( p ):
时间: 2023-06-13 11:02:45 浏览: 40
这段代码实现了根据两个字符序列构建二叉树的功能。其中,参数s1和s2分别表示两个字符序列,函数返回一个二叉树的根节点。
该算法的实现思路是,先在s1中取出第一个元素作为根节点,在s2中找到该元素的位置,将s2分成左子树和右子树的两个部分,分别递归构造左子树和右子树。
具体实现过程如下:
1. 首先判断s1和s2是否为空,如果有一个为空,则返回0,表示构建失败。
2. 取出s1中第一个元素作为根节点的值,创建一个新的节点p,并将该值赋给p的data域。
3. 在s2中从头开始遍历,找到第一个与根节点值相等的元素位置j。
4. 将s1和s2分成左右两部分,分别为s1[l1...j-l2]和s2[l2...j-1],s1[j-l2+1...h1]和s2[j+1...h2],其中l1、l2、h1、h2分别表示s1和s2的起始和结束位置。
5. 递归构造左子树,即调用BuTrPM函数,将s1[l1...j-l2]和s2[l2...j-1]作为参数,返回左子树根节点的指针,将该指针赋给p的Ichild域。
6. 递归构造右子树,即调用BuTrPM函数,将s1[j-l2+1...h1]和s2[j+1...h2]作为参数,返回右子树根节点的指针,将该指针赋给p的rchild域。
7. 最后返回根节点p的指针。
需要注意的是,该算法中采用了递归的方式构建二叉树,因此在实际应用中需要注意栈溢出的问题。
相关问题
)遍历一个二又树 查找 给出 以X节点为根的树的高度 void find( BiTree *T , int X ) I,用C语言写
以下是用C语言实现遍历二叉树查找以X节点为根的树的高度的代码:
```c
typedef struct BiTNode {
int data; // 数据域
struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
/* 计算以P为根节点的树的高度 */
int getHeight(BiTree p) {
if (!p) { // 如果节点为空,返回0
return 0;
} else { // 否则递归计算左右子树的高度,取较大值并加1
int leftHeight = getHeight(p->lchild);
int rightHeight = getHeight(p->rchild);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
}
/* 查找以X节点为根的树的高度 */
void find(BiTree T, int X) {
if (!T) { // 如果树为空,直接返回
return;
}
if (T->data == X) { // 如果当前节点为X节点,计算以X为根的树的高度并输出
int height = getHeight(T);
printf("以%d节点为根的树的高度为%d\n", X, height);
}
find(T->lchild, X); // 递归查找左子树
find(T->rchild, X); // 递归查找右子树
}
```
使用方法:
假设有一颗二叉树如下:
```
1
/ \
2 3
/ \
4 5
```
我们要查找以节点2为根的树的高度,可以这样调用find函数:
```c
BiTree T = createBiTree(); // 先创建一颗二叉树
find(T, 2); // 查找以2节点为根的树的高度
```
输出结果为:
```
以2节点为根的树的高度为2
```
上面的问题中为什么不在int main里定义BiTree *bt传入&bt
这是因为在C语言中,参数传递是值传递,即函数内部的形参是实参的一个副本,对形参的修改不会影响到实参的值。如果在`int main`函数中定义`BiTree *bt`并传入`&bt`,在函数内部修改`bt`的值是无效的,因为只是修改了副本的值,而没有修改实参的值。因此,在函数内部需要通过修改指针所指向的地址的值来改变实参的值,因此需要传入`&bt`的地址。