二叉树的遍历解决思路

二叉树的遍历

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<Windows.h>

typedef struct node
{
char data;
struct node *Lchild;
struct node *Rchild;
}tree;

void init_tree(tree *base)
{
base->data = '0';
tree *p1 = (tree *)malloc(sizeof(tree));
p1->data = '1';
base->Lchild = p1;

tree *p2 = (tree *)malloc(sizeof(tree));
p2->data = '2';
base->Rchild = p1;

tree *p3 = (tree *)malloc(sizeof(tree));
p3->data = '3';
p1->Lchild = p3;
p3->Lchild = NULL;
p3->Rchild = NULL;

tree *p4 = (tree *)malloc(sizeof(tree));
p4->data = '4';
p1->Rchild = p4;
p4->Lchild = NULL;
p4->Rchild = NULL;

tree *p5 = (tree *)malloc(sizeof(tree));
p5->data = '5';
p2->Lchild = p5;
p5->Lchild = NULL;
p5->Rchild = NULL;

tree *p6 = (tree *)malloc(sizeof(tree));
p6->data = '6';
p2->Rchild = p2;
p6->Lchild = NULL;
p6->Rchild = NULL;
}

void front_search(tree *base)
{
if (base != NULL)
{
printf("%c    ", base->data);
front_search(base->Lchild);
front_search(base->Rchild);
}
}

void middle_search(tree *base)
{
if (base != NULL)
{
front_search(base->Lchild);
printf("%c    ", base->data);
front_search(base->Rchild);
}
}

void next_search(tree *base)
{
if (base != NULL)
{
front_search(base->Lchild);
        front_search(base->Rchild);
printf("%c    ", base->data);
}
}

int main(int argc, char argv[])
{
tree *b;
init_tree(b);
front_search(b);
printf("\n");
    middle_search(b);
printf("\n");
    next_search(b);
printf("\n");
system("pause");

return 0;
}

这样居然会报错，而且还很多，类似于下面这样的错误：
错误1error C2275: “tree”: 将此类型用作表达式非法c:\documents and settings\maji\my documents\visual studio 2010\projects\zuihou\zuihou\main.c171ZUIHOU

错误23error C2223: “->Rchild”的左侧必须指向结构/联合c:\documents and settings\maji\my documents\visual studio 2010\projects\zuihou\zuihou\main.c291ZUIHOU

错误47error C2065: “p6”: 未声明的标识符c:\documents and settings\maji\my documents\visual studio 2010\projects\zuihou\zuihou\main.c431ZUIHOU

错误47error C2065: “p5”: 未声明的标识符c:\documents and settings\maji\my documents\visual studio 2010\projects\zuihou\zuihou\main.c431ZUIHOU

错误47error C2065: “p4”: 未声明的标识符c:\documents and settings\maji\my documents\visual studio 2010\projects\zuihou\zuihou\main.c431ZUIHOU

错误47error C2065: “p4”: 未声明的标识符c:\documents and settings\maji\my documents\visual studio 2010\projects\zuihou\zuihou\main.c431ZUIHOU

错误47error C2065: “p3”: 未声明的标识符c:\documents and settings\maji\my documents\visual studio 2010\projects\zuihou\zuihou\main.c431ZUIHOU

错误47error C2065: “p2”: 未声明的标识符c:\documents and settings\maji\my documents\visual studio 2010\projects\zuihou\zuihou\main.c431ZUIHOU

错误47error C2065: “p1”: 未声明的标识符c:\documents and settings\maji\my documents\visual studio 2010\projects\zuihou\zuihou\main.c431ZUIHOU



但是我觉得那样初始化p1,p2,p3,p4,p5,p6没有什么错误啊。 二叉树 遍历 指针 链表 结构体
[解决办法]
tree *b = NULL; 

如何为base->data = '0';   
[解决办法]
mian函数中tree *b没有分配内存，在init_tree()函数中，仍没有为tree *base,因此给base赋值并作为根节点是不行的，可以在main()中为其分配内存，也可以在init_tree()中为其分配内存，但此时函数形式应为init_tree(tree *&base);
另外，楼主p1,p2,p3,p4...的定义方式理论上是可以的，在我电脑上也没问题，我是vs2010
[解决办法]
分享一下我写的代码：

#include<stdio.h>
#include<malloc.h>

#define FALSE 1
#define ERROR 0
#define OK 1
#define ON 0

typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;

typedef int Status;
BiTree T;

Status CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c",&ch);
    if (ch==' ')
        *T = NULL;
    else
    {
        if (!((*T) = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
        (*T)->data = ch;
        CreateBiTree(&((*T)->lchild));   // 构造左子树
        CreateBiTree(&((*T)->rchild));   // 构造右子树
    }
    return OK;
} // CreateBiTree

int vi(char c)
{
    printf("%c ",c);
    return OK;
}

//先序遍历的递归
void PreOrder(BiTree T)
{
    if(T)
    {
        vi(T->data);      //访问结点
        PreOrder(T->lchild);       //遍历左子树
        PreOrder(T->rchild);       //遍历右子树
    }
}

//中序遍历的递归
void InOrder(BiTree T)
{
    // 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
    // 中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。
    if(T)
    {
    InOrder(T->lchild);
    vi(T->data);
    InOrder(T->rchild);
    }
} // InOrderTraverse

//后序遍历的递归
void PostOrder(BiTree T)
{
    // 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
    // 中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。 
 
    if(T)
    {
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    vi(T->data);
    }
} // InOrderTraverse
int main()
{
    printf("先序输入二叉树(空格代表空节点)：\n");
    CreateBiTree(&T);
    printf("先序输出二叉树：\n");
    PreOrder(T);
    printf("\n");
    printf("中序输出二叉树：\n");
    InOrder(T);
    printf("\n");
    printf("后序输出二叉树：\n");
    PostOrder(T);
    printf("\n");
    return 0;
}

[解决办法]
tree b;
init_tree(&b);
这样比较好
[解决办法]
我来贴上我曾经写的二叉树，用C++封装的，希望对你有用：

#pragma once
#include"BinTreeNode.h"
#include<queue>
#include <algorithm>
#include<iostream>
#include<fstream>//文件流 重载输入
using namespace std;
template<class T>
class BinTree
{
protected:
BT_Node<T> *root;//一个二叉树的根结点 被封装
T endflag_value;//二叉树的输入结束标志
protected:
//bool Insert_(BT_Node<T> *subTree,const T& x);//插入 参数(sunTree 为子树的意思)
void Destroy_(BT_Node<T> *subTree);//删除

BT_Node<T> * Copy_(BT_Node<T> *orignNode);//复制 返回根结点指针参数(复制 结点)
BT_Node<T> * Find_(BT_Node<T> *subTree,const T& x)const;//常函数 不允许改动类中的数据 查找
int Height_(BT_Node<T> *subTree);//求一棵二叉树的高度或是深度
int Size_(BT_Node<T> *subTree);//求一棵二叉树的结点个数
BT_Node<T> * Parent_(BT_Node<T> *subTree,BT_Node<T> *current);//寻找父结点 参数(子树 当前需要被找的结点)

void PreOrder_(BT_Node<T> *subTree,void(* )(BT_Node<T> *));//前序遍历 后一个参数是函数指针
void InOrder_(BT_Node<T> *subTree,void(* )(BT_Node<T> *));//中序遍历
void PostOrder_(BT_Node<T> *subTree,void(* )(BT_Node<T> *));//后序遍历

void Output_(ostream& out,BT_Node<T> *subTree);//输出一棵二叉树 
void CreateBinTree_(ifstream& in,BT_Node<T> * &subTree);//私有函数后带有_标志，建树被封装
void CreateBinTree_(istream& in,BT_Node<T> * &subTree);//私有函数后带有_标志，建树被封装

public:

BinTree();//无参构造函数
BinTree(T value);//带参 初始化输入结束标志
BinTree(BinTree<T> &Tree);//深复制函数
~BinTree();//析构函数

bool isEmpty();//判树空
BT_Node<T> * & Get_Root();//返回树的根结点
BT_Node<T> * Get_Parent(BT_Node<T> *current);//返回父结点 用于对外接口 只接受一个指针参数
BT_Node<T> * Get_Leftchild(BT_Node<T> *subTree);//返回该结点的左孩子
BT_Node<T> * Get_Rightchild(BT_Node<T> *subTree);//返回该结点的右孩子

int Get_Height();//返回树的高度或是深度 对外无参接口
int Get_Size();//返回树的结点个数 对外无参接口

void PreOrder(void (* visit)(BT_Node<T> *));//前序遍历 无参对外接口内部使用根结点封装
void InOrder(void (* visit)(BT_Node<T> *));//中序遍历
void PostOrder(void (* visit)(BT_Node<T> *));//后序遍历
void LevelOrder(void (* )(BT_Node<T> *));//按层遍历 
 

void Destroy();//删除 对外无参接口 同析构一样作用
//int Insert(const T &item);//插入新元素 在二叉树的下一个合法结点位置处
BT_Node<T> * Find(const T &item)const;//搜索

template<class T> friend ifstream& operator>> (ifstream& input,BinTree<T> &Tree);//友元 文件流重载 输入
template<class T> friend istream& operator>> (istream& input,BinTree<T> &Tree);//友元，标准输入流重载
template<class T> friend ostream& operator<< (ostream& output,BinTree<T> &Tree);//输出重载

void operator= (BinTree<T> &BT);
};
/******************   私有函数域   ******************/
template<class T>
void BinTree<T>::Destroy_(BT_Node<T> *subTree)//删除
{
if(subTree != NULL)//当前指针不为空 说明有子树
{
Destroy_(subTree->leftchild);//则递归下去
Destroy_(subTree->rightchild);
delete subTree;//最后删除
}
//当前指针为NULL时 会不执行语句直接返回上一层
}

template<class T>
BT_Node<T> * BinTree<T>::Find_(BT_Node<T> *subTree,const T& x)const //查找
{

if(subTree == NULL)
return NULL;
if(subTree->data == x)//找到
{
return subTree;
}

BT_Node<T> *temp;
if((temp = Find_(subTree->leftchild,x)) != NULL)//若当前不相等 则递归下去
return temp;
else
return Find_(subTree->rightchild,x);
}

template<class T>
BT_Node<T> * BinTree<T>::Copy_(BT_Node<T> *orignNode)//复制 返回根结点指针参数(复制 结点)
{
if(orignNode == NULL)
return NULL;//如果当前指针为空则不执行后面的复制语句

BT_Node<T> *temp = new BT_Node<T>;//创立一个新的结点
temp->data = orignNode->data;//复制数据域
temp->leftchild = Copy_(orignNode->leftchild);
temp->rightchild = Copy_(orignNode->rightchild);

return temp;//最后的效果是 返回根结点指针
}

template<class T>
void BinTree<T>::operator= (BinTree<T> &BT)
{
root = Copy_(BT.root);
}

template<class T>
int BinTree<T>::Height_(BT_Node<T> *subTree)//求一棵二叉树的高度或是深度
{
if(subTree == NULL)
return 0;//如果递归到底 则返回0到上一层

else
{
int left_H = Height_(subTree->leftchild);//当前指针不为NULL 递归下去
int right_H = Height_(subTree->rightchild);
return ( (left_H < right_H) ? (right_H + 1) : (left_H + 1) ); //左右子树的深度进行比较 返回较大值 并且加1
}
}

template<class T>
int BinTree<T>::Size_(BT_Node<T> *subTree)//求一棵二叉树的结点个数
{
if(subTree == NULL)
return 0;//递归到底 则返回0

else
{
return ( 1 + Size_(subTree->leftchild) + Size_(subTree->rightchild));
//否则一直计算下一个左右子树的结点树 +1 为统计核心
}

}

template<class T>
BT_Node<T> * BinTree<T>::Parent_(BT_Node<T> *subTree,BT_Node<T> *current)
{                                        //寻找父结点 参数(子树 当前需要被找的结点) 
 
if(subTree == NULL)
return NULL;
if(subTree->leftchild == current 
[解决办法]
 subTree->rightchild == current)//找到父结点
return subTree;//返回父结点
BT_Node<T> *temp;//临时存储指针变量
if( (temp = Parent_(subTree->leftchild,current)) != NULL)
return temp;//递归左子树
else
return Parent_(subTree->rightchild,current);//递归右子树
}

template<class T>
void BinTree<T>::PreOrder_(BT_Node<T> *subTree,void (* )(BT_Node<T> *))//前序遍历
{
if(subTree != NULL)//当前指针不为空时指向一下语句
{
visit(subTree);//对当前指针指向的对象的任意操作
PreOrder_(subTree->leftchild,visit);//递归 左子树
PreOrder_(subTree->rightchild,visit);//递归右子树
}
//当前指针为空则直接不执行 返回上一层
}

template<class T>
void BinTree<T>::InOrder_(BT_Node<T> *subTree,void (* )(BT_Node<T> *))//中序遍历
{
if(subTree != NULL)
{
InOrder_(subTree->leftchild,visit);
visit(subTree);
InOrder_(subTree->rightchild,visit);
}
}

template<class T>
void BinTree<T>::PostOrder_(BT_Node<T> *subTree,void (* )(BT_Node<T> *))//后序遍历
{
if(subTree != NULL)
{
PostOrder_(subTree->leftchild,visit);
PostOrder_(subTree->rightchild,visit);
visit(subTree);
}
}

template<class T>
void BinTree<T>::CreateBinTree_(ifstream& in,BT_Node<T> * &subTree) //文件流输入重载 适用于从文件中读进内存
{
T item;
if(!in.eof())//不到文件的末尾 执行
{
in>>item;
if(item != endflag_value)
{
subTree = new BT_Node<T>(item);//调用含参 构造函数 指针域为NULL
if(subTree == NULL)
{
cout<<"内存分配错误!"<<endl;
exit(1);//强制结束进程
}
CreateBinTree_(in,subTree->leftchild);//递归调用 建立当前结点为根结点的左右子树
CreateBinTree_(in,subTree->rightchild);
}
else
subTree = NULL;//把当前参数中的指针置为NULL 封闭子树指针域
}
}

template<class T>
void BinTree<T>::CreateBinTree_(istream& in,BT_Node<T> * &subTree) //标准输入流重载 适用于从键盘上读进内存
{
T item;
in>>item;
if(item != endflag_value)
{
subTree = new BT_Node<T>(item);//调用含参 构造函数 指针域为NULL
if(subTree == NULL)
{
cout<<"内存分配错误!"<<endl;
exit(1);//强制结束进程
}
CreateBinTree_(in,subTree->leftchild);//递归调用 建立当前结点为根结点的左右子树
CreateBinTree_(in,subTree->rightchild);
}
if(item == endflag_value)
{
subTree = NULL;//把当前参数中的指针置为NULL 封闭子树指针域
}
}

template<class T>
void BinTree<T>::Output_(ostream& out,BT_Node<T> *subTree)//输出一棵二叉树 假定使用前序遍历方式
{
if(subTree != NULL)
{
out<<"#: "<<subTree->data<<endl;//输出当前指针指向的对象数据
Output_(out,subTree->leftchild);//递归左子树
Output_(out,subTree->rightchild);//递归右子树
}
}
/******************   私有函数域   ******************/


/******************   对外接口域   ******************/
template<class T>
BinTree<T>::BinTree()
{
root = NULL;//根结点被赋为空 不理会输入结束标志 一般用不到
}

template<class T> 
 
BinTree<T>::BinTree(T value)
{
root = NULL;
endflag_value = value;
}

template<class T>
BinTree<T>::BinTree(BinTree<T> &Tree)//深复制函数
{
root = Copy_(Tree.root);//调用内部函数 生成一棵树后把根结点给当前对象的root
}

template<class T>
BinTree<T>::~BinTree()
{
Destroy_(root);//调用内部函数 释放一个树的所有的结点的内存
}

template<class T>
bool BinTree<T>::isEmpty()//判树空
{
return ((root == NULL) ? true : false);
}

template<class T>
BT_Node<T> * & BinTree<T>::Get_Root()//返回树的根结点
{
return root;
}

template<class T>
BT_Node<T> * BinTree<T>::Get_Parent(BT_Node<T> *current)//返回父结点 用于对外接口 只接受一个指针参数
{
return ( Parent_(root,current) );//调用内部函数 返回父结点指针
}

template<class T>
BT_Node<T> * BinTree<T>::Get_Leftchild(BT_Node<T> *subTree)//返回该结点的左孩子
{
if(subTree != NULL)//不为空 返回左孩子指针
return subTree->leftchild;
else
return NULL;//否则返回NULL
}

template<class T>
BT_Node<T> * BinTree<T>::Get_Rightchild(BT_Node<T> *subTree)//返回该结点的右孩子
{
if(subTree != NULL)
return subTree->rightchild;
else
return NULL;
}

template<class T>
int BinTree<T>::Get_Height()//返回树的高度或是深度 对外无参接口
{
return ( Height_(root) );//返回树的深度
}

template<class T>
int BinTree<T>::Get_Size()//返回树的结点个数 对外无参接口
{
return ( Size_(root) );//返回树结点数目
}

template<class T>
void BinTree<T>::Destroy()
{
Destroy_();
}

template<class T>
void BinTree<T>::PreOrder(void (* visit)(BT_Node<T> *))//前序遍历 无参对外接口内部使用根结点封装
{
PreOrder_(root,visit);//调用内部函数 前序遍历
}

template<class T>
void BinTree<T>::InOrder(void (* visit)(BT_Node<T> *))//中序遍历
{
InOrder_(root,visit);
}

template<class T>
void BinTree<T>::PostOrder(void (* visit)(BT_Node<T> *))//后序遍历
{
PostOrder_(root,visit);
}

template<class T>
void BinTree<T>::LevelOrder(void (* )(BT_Node<T> *))//按层遍历 要用到队列 逐层访问类问题
{
queue<BT_Node<T> *> qu; //STL中的队列 ,存储树结点指针
BT_Node<T> *current = root;
qu.push(current); //STL中的进队列就是PUSH
while(!qu.empty())
{
current = qu.front(); //获取对头元素的引用
visit(current);
qu.pop(); //删除对头元素 无返回值 ,所以要先返回引用再删除
if(current->leftchild != NULL)
qu.push(current->leftchild);
if(current->rightchild != NULL)
qu.push(current->rightchild);
}
}

template<class T>
BT_Node<T> * BinTree<T>::Find(const T &item) const//搜索
{
return Find_(root,item);
}

template<class T>
ifstream& operator>> (ifstream& input,BinTree<T> &Tree)//友元 重载 输入
{
Tree.CreateBinTree_(input,Tree.Get_Root());
return input;
}
template<class T>
istream& operator>> (istream& input,BinTree<T> &Tree) 
 
{
Tree.CreateBinTree_(input,Tree.root);
return input;
}

template<class T>
ostream& operator<< (ostream& output,BinTree<T> &Tree)//这里的输出是一个全局函数，与类无关
{
Tree.Output_(output,Tree.Get_Root());
return output;
}

[解决办法]
其实程序思路还可以，就是太粗心了，写完代码后应该仔细看下的，比如你写的

tree *p1 = (tree *)malloc(sizeof(tree));
    p1->data = '1';
    base->Lchild = p1;
 
    tree *p2 = (tree *)malloc(sizeof(tree));
    p2->data = '2';
    base->Rchild = p1;

你写的左右指针均指向p1了，又如

void middle_search(tree *base)
{
    if (base != NULL)
    {
        front_search(base->Lchild);
        printf("%c    ", base->data);
        front_search(base->Rchild);
    }
}
 
void next_search(tree *base)
{
    if (base != NULL)
    {
        front_search(base->Lchild);
        front_search(base->Rchild);
        printf("%c    ", base->data);    
    }
}

这递归怎么能写成函数调用呢。其实写完后仔细看下不用编译都能发现大部分明显的错误。

查看更多 下一篇