本文共 1740 字，大约阅读时间需要 5 分钟。

二叉树的基本操作

以下代码通过先序法创建一个二叉树，然后运用递归思想实现对二叉树的先序、中序、后序的遍历。

#include 
   
    #include 
    
     using namespace std;   /* * 二叉树的二叉链表结构的创建与相关操作 * 1.先序法创建二叉树 * 2.先序遍历 * 3.中序遍历 * 4.后序遍历 * 说明：如果结点为叶子结点，只需将左右孩子的值置为'#',(即紧邻之后的两个输入为'#'); * 例如：输入：a b # # c # # ,得到以a为根结点，b为左孩子，c为右孩子的二叉树。 *///二叉树结点结构体typedef struct BTNode{
       char data;    struct BTNode *pLchild,*pRchild;}BTNode,*BinTree;//声明函数void CreatBTree(BinTree&);       //创建二叉树void PreTraverseTree(BinTree);   //先序遍历void InTraverseTree(BinTree);    //中序遍历void PostTraverseTree(BinTree);  //后序遍历//main函数int main(){
       BTNode* pBintree=NULL;    CreatBTree(pBintree);    cout<<"先序遍历：";    PreTraverseTree(pBintree);    cout<<"\n中序遍历：";    InTraverseTree(pBintree);    cout<<"\n后序遍历：";    PostTraverseTree(pBintree);    return 0;}//先序建立二叉树void CreatBTree(BinTree& bt){
       char val;    cout<<"请输入结点值：";        cin>>val;    if(val=='#')    {
           return;    }    if(bt==NULL)    {
           bt=(BTNode*)malloc(sizeof(BTNode));        bt->data=val;        bt->pLchild=NULL;        bt->pRchild=NULL;    }    CreatBTree(bt->pLchild);    CreatBTree(bt->pRchild);}//先序遍历void PreTraverseTree(BinTree bt){
       if(bt!=NULL)    {
           cout<
     
      data<<"->";        PreTraverseTree(bt->pLchild);        PreTraverseTree(bt->pRchild);    }    else        return;}//中序遍历void InTraverseTree(BinTree bt){
       if(bt!=NULL)    {
           InTraverseTree(bt->pLchild);        cout<
      
       data<<"->";        InTraverseTree(bt->pRchild);    }    else        return;}//后序遍历void PostTraverseTree(BinTree bt){
       if(bt!=NULL)    {
           PostTraverseTree(bt->pLchild);        PostTraverseTree(bt->pRchild);        cout<
       
        data<<"->";    }   else        return;}
       
      
     
    
   

转载地址：http://adyki.baihongyu.com/