描述
设二叉树中每个结点的元素均为一个字符,按先序遍历的顺序建立二叉链表,编写递归算法计算二叉树的高度。
输入
多组数据。每组数据一行,为二叉树的前序序列(序列中元素为‘0’时,表示该结点为空)。当输入只有一个“0”时,输入结束。
输出
每组数据分别输出一行,为二叉树的高度。
输入样例 1
abcd00e00f00ig00h00
abd00e00cf00g00
0
输出样例 1
4
3
用两个int maxi和max1来分别记录总体最大值和当前走过的最大值。
错误思路:
若bt走到了NULL,说明已经遍历到一个枝条的结尾了,这个时候比较maxi和max1,更新maxi的值,并令max1=0,否则令max1++并继续遍历。
n个节点二叉树的高度怎么算?错误就在于不应该让max1=0,因为回退一次之后,再走其他的节点是 在这个节点路径的基础之上的,就相当于“站在前人的肩膀上”,如果因为当前节点走到头了就把之前走过的路径全部清空,再从它的parent遍历其他分支的时候,就会存在parent以上的节点没有被计算进总路径的问题!
错误代码:
#include <iostream>
using namespace std;
typedef struct BNode
{char data;struct BNode* lchild, *rchild;
}*BTree, BNode;
int max1 = 0, maxi = 0;
void Create(BTree& bt)
{char c;cin >> c;if (c == '0')bt = NULL;else{bt = new BNode;bt->data = c;Create(bt->lchild);Create(bt->rchild);}
}
void Create(BTree& bt,char c)
{if (c == '0')bt = NULL;else{bt = new BNode;bt->data = c;Create(bt->lchild);Create(bt->rchild);}
}
void Traverse(BTree bt)
{if (bt == NULL){maxi = max1 > maxi ? max1 : maxi;max1 = 0;return;}else{max1++;Traverse(bt->lchild);Traverse(bt->rchild);}
}
int main()
{while (1){char c;cin >> c;if (c == '0')break;BTree b;Create(b, c);Traverse(b);cout << maxi << endl;maxi = 0;}return 0;
}
正确思路:
设置maxi和max1的思路是对的,这个计算长度和DFS迷宫问题的思路有些相似了,就是先从当前节点出发走遍所有的可能节点,再回退遍历其他路径,比较两种路径的大小取最大值即可。所以就要让max1在每次遍历完回退之后都--(就是回退到自己这一步,再尝试其他的路)。
真是要学会举一反三呀,不能学了DFS就把思路都局限在迷宫问题上了!
计算一个二叉树的最小高度?正确代码如下:
#include <iostream>
using namespace std;
typedef struct BNode
{char data;struct BNode* lchild, * rchild;
}*BTree, BNode;
int max1 = 0, maxi = 0;//不能写max,max是内置函数的名字
void Create(BTree& bt)
{char c;cin >> c;if (c == '0')bt = NULL;else{bt = new BNode;bt->data = c;Create(bt->lchild);Create(bt->rchild);}
}
void Create(BTree& bt, char c)
{if (c == '0')bt = NULL;else{bt = new BNode;bt->data = c;Create(bt->lchild);Create(bt->rchild);}
}
void Traverse(BTree bt)
{if (bt){max1++;Traverse(bt->lchild);Traverse(bt->rchild);maxi = max1 > maxi ? max1 : maxi;//更新maxi的值max1--;//max1回退到之前的位置,假设这一步没走过}
}
int main()
{while (1){char c;cin >> c;if (c == '0')break;BTree b;Create(b, c);Traverse(b);cout << maxi << endl;maxi = 0;max1 = 0;}return 0;
}
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态