高分求二叉树的建立例题，以及三种遍历
我上机报告的代码和截图
#include《iostream》
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char BiElemType;
// 二叉树的数据结构定义
typedef struct BiNode
{
BiElemType data;
BiNode *lchild,*rchild;
}BiNode,*BiTree;
//构造一棵二叉树，并且按照前序遍历的方式赋值
Status CreateBiTree(BiTree &T)
{
BiElemType ch;
cin》》ch;
if(ch==’#’)T=NULL;
else
{
if(!(T=(BiNode *)malloc(sizeof(BiNode))))exit(OVERFLOW);
T-》data=ch;
CreateBiTree(T-》lchild);
CreateBiTree(T-》rchild);
}
return OK;
}
//先序遍历
Status preorder(BiTree T)
{
if(T)
{
if(cout《《T-》data《《’ ’)
if(preorder(T-》lchild))
if(preorder(T-》rchild))return OK;
return ERROR;
}
else return OK;
}
//中序遍历
Status inorder(BiTree T)
{
if(T)
{
if(inorder(T-》lchild))
if(cout《《T-》data《《’ ’)
if(inorder(T-》rchild))return OK;
return ERROR;
}
else return OK;
}
//后序遍历
Status postorder(BiTree T)
{
if(T)
{
if(postorder(T-》lchild))
if(postorder(T-》rchild))
if(cout《《T-》data《《’ ’)return OK;
return ERROR;
}
else return OK;
}
int main()
{
BiTree BiT;
cout《《“以先序顺序输入二叉树的数据，以#表示空节点：“《《endl;
CreateBiTree(BiT);
cout《《“以中序遍历输出：“;
inorder(BiT);
cout《《endl;
cout《《“以先序遍历输出：“;
preorder(BiT);
cout《《endl;
cout《《“以后序遍历输出：“;
postorder(BiT);
cout《《endl;
return 0;
}
两个二叉树遍历选择题
第一个题目我觉得后序遍历比较的说法比较牵强，有耐性的可以看看我的说法，欢迎交流，呵呵。
我是这么想：按题目的要求，互换左右子树的位置，要么从根开始，逐层互换，这当然就层次遍历了，在每一层将该层结点的左右子树位置都互换，这个不难理解，但是你想想，一层互换完了，下一层怎么开始互换呢？这就需要每层的结点的交换操作完毕后，记录该层所有的结点的地址，将他们保存起来(因为是二叉链表，保存地址是必要的)，要不然下一层互换就没法开始吧？！每一层的要开始互换，都要上一层的某个地址来获得到当前需要互换的结点地址，然后这个进行互换的结点的地址也要暂存，如此循环咯；
另外一种方法自然就是从叶子开始，自下而上了，采用前序遍历，这种属于自下而上交换的做法了，一定需要堆栈递归，抽象地说，访问二叉树的时候，把根压栈，继续访问左子树，直到碰到左叶子，之前路径上的结点都压栈嘛，这时左叶子就不压栈了，返回左叶子的双亲结点后访问它的右孩子为根的子树，做法同上，递归返回上一层的时候发现左右孩子都访问过了，进行一次位置的互换，然后再继续递归的返回(这个过程就是前序遍历啦，别看题目说什么后序遍历，二叉链表哦，分明就是要先把根结点压栈，先访问根结点，才能访问左右嘛，什么后序遍历，扯蛋)。当然题目才告诉我二叉树，我还分不出哪个方法最优，哥觉得题目比较扯蛋，关键还是楼主你自己要理解做法，多动脑筋而别去迷信题目答案。
第二个题目，只有中序遍历线索可以找到直接前驱和直接后继，这也是线索化的目的所在，但是前序线索化无法仅通过线索找到直接前驱，后序线索化无法通过仅通过线索找到直接后继，试想一下某个有左孩子又有右孩子的非根的中间结点就明白了。
-二叉树的遍历例题
二叉树的层次遍历算法
二叉树的层次遍历算法有如下三种方法：
给定一棵二叉树，要求进行分层遍历，每层的节点值单独打印一行，下图给出事例结构：
对此二叉树遍历的结果应该是：
1，
2 ， 3
4， 5， 6
7， 8
第一种方法，就是利用递归的方法，按层进行打印，我们把根节点当做第0层，之后层次依次增加，如果我们想打印第二层怎么办呢，利用递归的代码如下：
[cpp] view plaincopy
int print_at_level(Tree T, int level) {
if (!T || level 《 0)
return 0;
if (0 == level) {
cout 《《 T-》data 《《 “ “;
return 1;
}
return print_at_level(T-》lchild, level - 1) + print_at_level(T-》rchild, level - 1);
如果我们成功的打印了给定的层次，那么就返回非0的正值，如果失败返回0。有了这个思路，我们就可以应用一个循环，来打印这颗树的所有层的节点，但是有个问题就是我们不知道这棵二叉树的深度，怎么来控制循环使其结束呢，仔细看一下print_at_level，如果指定的Tree是空的，那么就直接返回0，当返回0的时候，我们就结束循环，说明没有节点可以打印了。-二叉树
[cpp] view plaincopy
void print_by_level_1(Tree T) {
int i = 0;
for (i = 0; ; i++) {
if (!print_at_level(T, i))
break;
}
cout 《《 endl;
}
以上的方法可以很清楚的看出，存在重复访问的情况，就是第0层访问的次数最多，第1层次之。所以这个递归的方法不是很有效的方法。
第二种方法：我们可以设置两个队列，想象一下队列的特点，就是先进先出，首先把第0层保存在一个队列中，然后按节点访问，并把已经访问节点的左右孩子节点放在第二个队列中，当第一个队列中的所有节点都访问完成之后，交换两个节点。这样重复下去，知道所有层的节点都被访问，这样做的代价就是空间复杂度有点高。-二叉树的遍历例题
[cpp] view plaincopy
void print_by_level_2(Tree T) {
deque《tree_node_t*》 q_first, q_second;
q_first.push_back(T);
while(!q_first.empty()) {
while (!q_first.empty()) {
tree_node_t *temp = q_first.front();
q_first.pop_front();
cout 《《 temp-》data 《《 “ “;
if (temp-》lchild)
q_second.push_back(temp-》lchild);
if (temp-》rchild)
q_second.push_back(temp-》rchild);
}
cout 《《 endl;
q_first.swap(q_second);
}
}
第三种方法就是设置双指针，一个指向访问当层开始的节点，一个指向访问当层结束节点的下一个位置：
这是第一层访问的情况，当访问第0层之后的结构如下，把第0层的所有子节点加入之后：
访问完第1层之后：
之后大家就可以自己画图了，下面给出程序代码：
[cpp] view plaincopy
void print_by_level_3(Tree T) {
vector《tree_node_t*》 vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur 《 vec.size()) {
end = vec.size();
while (cur 《 end) {
cout 《《 vec[cur]-》data 《《 “ “;
if (vec[cur]-》lchild)
vec.push_back(vec[cur]-》lchild);
if (vec[cur]-》rchild)
vec.push_back(vec[cur]-》rchild);
cur++;
}
cout 《《 endl;
}
}
最后给出完成代码的测试用例：124##57##8##3#6##
[cpp] view plaincopy
#include《iostream》
#include《vector》
#include《deque》
using namespace std;
typedef struct tree_node_s {
char data;
struct tree_node_s *lchild;
struct tree_node_s *rchild;
}tree_node_t, *Tree;
void create_tree(Tree *T) {
char c = getchar();
if (c == ’#’) {
*T = NULL;
} else {
*T = (tree_node_t*)malloc(sizeof(tree_node_t));
(*T)-》data = c;
create_tree(&(*T)-》lchild);
create_tree(&(*T)-》rchild);
}
}
void print_tree(Tree T) {
if (T) {
cout 《《 T-》data 《《 “ “;
print_tree(T-》lchild);
print_tree(T-》rchild);
}
}
int print_at_level(Tree T, int level) {
if (!T || level 《 0)
return 0;
if (0 == level) {
cout 《《 T-》data 《《 “ “;
return 1;
}
return print_at_level(T-》lchild, level - 1) + print_at_level(T-》rchild, level - 1);
}
void print_by_level_1(Tree T) {
int i = 0;
for (i = 0; ; i++) {
if (!print_at_level(T, i))
break;
}
cout 《《 endl;
}
void print_by_level_2(Tree T) {
deque《tree_node_t*》 q_first, q_second;
q_first.push_back(T);
while(!q_first.empty()) {
while (!q_first.empty()) {
tree_node_t *temp = q_first.front();
q_first.pop_front();
cout 《《 temp-》data 《《 “ “;
if (temp-》lchild)
q_second.push_back(temp-》lchild);
if (temp-》rchild)
q_second.push_back(temp-》rchild);
}
cout 《《 endl;
q_first.swap(q_second);
}
}
void print_by_level_3(Tree T) {
vector《tree_node_t*》 vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur 《 vec.size()) {
end = vec.size();
while (cur 《 end) {
cout 《《 vec[cur]-》data 《《 “ “;
if (vec[cur]-》lchild)
vec.push_back(vec[cur]-》lchild);
if (vec[cur]-》rchild)
vec.push_back(vec[cur]-》rchild);
cur++;
}
cout 《《 endl;
}
}
int main(int argc, char *argv) {
Tree T = NULL;
create_tree(&T);
print_tree(T);
cout 《《 endl;
print_by_level_3(T);
cin.get();
cin.get();
return 0;
}
