二叉树的遍历以及遇到的一些问题
今天在学习二叉树的遍历，在源码实现过程中，出现的一些问题，这里做一个记录。
这里以二叉树的前序遍历为例。输入前序遍历的数据元素（以空格作为空元素），构造二叉树，然后遍历二叉树输出每个数据元素所在的层。
头文件tree.h
#pragma once
typedef char ElemType;
struct BiTNode
{
ElemType data;
BiTNode *left;
BiTNode *right;
BiTNode(ElemType val): data(val), left(NULL), right(NULL){}
};
//构建二叉树
void createBiTree(BiTNode *&node);
//前序遍历二叉树
void preOrderTraverse(BiTNode *node, int level);
//访问给定树结点
void visit(BiTNode node, int level);源程序文件BiTree.cpp
#pragma once
#include <iostream>
#include "tree.h"
using namespace std;
void createBiTree(BiTNode *&node)
{
char ch = cin.get();
if (' ' == ch)
{
node = NULL;
}
else
{
node = new BiTNode(ch);
createBiTree(node->left);
createBiTree(node->right);
}
}
void preOrderTraverse(BiTNode *node, int level)
{
if (node != NULL)
{
visit(*node, level);
preOrderTraverse(node->left, level + 1);
preOrderTraverse(node->right, level + 1);
}
}
void visit(BiTNode node, int level)
{
cout<<node.data<<" in "<<level<<" levle."<<endl;
}测试程序：
#include <iostream>
#include "tree.h"
using namespace std;
int main()
{
BiTNode *root = NULL;
cout<<"Please input charset in preorder:";
createBiTree(root);
preOrderTraverse(root, 0);
if (root != NULL)
{
delete root;
}
return 0;
}我主要的错误是我刚开始的时候构建二叉树的函数签名是这样的：void createBiTree(BiTNode *node)，那么这个和void createBiTree(BiTNode *&node)有什么区别吗？
因为这个错误，我搞了整整一天。
void createBiTree(BiTNode *node)是将结点的指针（地址）传递到函数中进行处理，而void createBiTree(BiTNode *&node)是将结点指针的引用传递到函数处理。一般来说，如果node不为NULL的话，都是操作地址，个人感觉差别不是很大。但是在这里因为main函数初始化root是NULL，所以如果直接传递的是地址的话，会导致createBiTree执行完以后root任然为NULL（因为传过去的是地址的一个拷贝，如果root不为NULL的话，即使传过去的是地址的拷贝，因为我们操作的是地址所指向的值，所以关系不大，但是这里偏偏root为NULL，我们重新new了一个地址所以导致最后root任然是NULL）。所以将程序改写成传递指针的引用，问题很快就解决了。
最后，晒晒结果：
对于这样一个二叉树
最后还有一点要说明的是，第一次一次性输入前序遍历的结果，cin对象会从缓冲中一次一次的读取，ch = cin.get()和cin.get(ch)的作用是一样的。
如果采用cin>>ch的话，cin遇到空格就结束了，所以我们这里不能使用cin>>ch.