二叉树的遍历，c++

71 阅读 0 评论 47 点赞

我是靠谱客的博主潇洒水杯，最近开发中收集的这篇文章主要介绍二叉树的遍历，c++，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

 注：完整代码主页资源抽取
     【实验名称】 二叉树的基本操作实验 
     
     【实验学时】 2学时 
     
     【实验目的】  
      
      1.掌握二叉链表的存储结构形式及其描述。 
     
     2.掌握二叉树的先序、中序、后序遍历算法，将遍历方法熟练应用到建立二叉链表、统计叶子节点，统计节点个数，求二叉树高度和输出节点信息的算法中。 
     
      
    
        
     【实验类型】  验证型实验 
     
     【实验原理】   
     
          二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 
     
         特点：⑴ 每个结点最多有两棵子树； 
     
               ⑵ 二叉树是有序的，其次序不能任意颠倒。  
     
     用C语言声明二叉树的二叉链表结点的存储表示如下：  
     
     typedef struct BiTNode 
     
     { 
     
     TElemType  data;  
     
     struct BiTNode  *lchild, *rchild; //左右孩子指针 
     
     }BiTNode,  *BiTree;  
     
      
    
        
       
     
     定义二叉链表的头指针： 
     
      BitTree T； 
     
     定义指向二叉链表任意结点的指针： 
     
      BiTNode  *p； 
     
     引用数据元素：p->data 
     
     引用指针域：p->lchild, p->rchild; 
     
      
    
        
     【实验内容】  
     
     1．建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序）、打印输出遍历结果。 
     
     2．编写函数，统计二叉树中结点的个数。 
     
     3．编写函数, 统计叶子结点的个数。 
     
     4．*编写函数,，求二叉树的高度。 
     
     5．*编程实现：二叉树采用二叉链表存储，要求建立一棵二叉树，按树状形式打印出相应编号的程序。

代码实现

1.头文件的定义

#include<iostream>
#include<stdlib.h>
using namespace std;
typedef char eleltype;
int lifecount=0;
int unudecount=0;

  2.数据存储定义（结构体）

typedef struct bitnode
{
   elemtype data;//数据类型
   struct bitnode *lchild,*rchild;//左右子树的首地址
   
   
   
}bitnode,*bitree;//树节点的首地址，以及节点名称

3.二叉树的建立（申请空间）

void fun::createbitree(bitree *T)//传入数的首地址
{
elemtype ch;
cin>>ch;
if(ch==' ')//如果为空格节点为null
     *T=NULL;
 else//否则建造节点
 {
   *T=(bitnode)malloc(sizeof(bitnode));//开辟结构体类型节点空间
   （*T）->data=ch;
   createbitree(&(*T)->lchild)；//迭代生成其他节点
    createbitree(&(*T)->rchild);


 }

}

3.前序遍历

void fun::preorder(bitree T)
{
    if(T!=NULL)
       cout<<T->data;
       preorder(T->lchild);迭代调用pre
        preorder(T->rchild);
      

}

4.中序遍历

void fun::inorder(bitree T)
{
      if(T!=NULL)
      inorder(T->lchild);
      cout<<T->data;
       inorder(T->rchild);
      
      


}

5.后序遍历

void fun::postorder(bitree T)
{ 
     if(T!=NULL)
        postorder(T->lchild);
        postorder(T->rchild);
        cout<<T->data;

}

6.叶子节点计算

void fun::left(bitree T)
{
   if(T!=NULL)
   if(T->lchild==NULL&&T->rchild==NULL)
   liefcount++;
   leaf(bitree T->lchild);
    leaf(bitree T->rchild);
   

}

7非叶子节点计算

void unodecount(bitree T)
{
   if(T!=NULL)
   if(!(T->lchild==NULL&&T->rchild==NULL))
        unudecount++;
        unodecount(bitree T->lchild);
        unodecount(bitree T->rchild);

}

8.按树形输出

void fun::printtree(bitree T,int layer)
{ nudecount++;
if(T!=NULL)
printtree(T-rchild,layer+1);
for(int i=0;i<layer;i++)
cout<<"  ";
cout<<T->data;
printtree(T->lchild,layer+1);
}

9.主函数

int main()
{

 fun A;
 int laval=1;
 birtee T;
  cout << "请以前序遍历的方式输入扩展二叉树："; 
  A.createbitree(&T);
  cout << "非叶子节点数：";
    A. unodecount( T);
    cout<<unodecount<<endl;
   cout << "叶子节点数："; 
     A.left( T);
     cout<<"递归前序遍历输出为：" << endl;
     A.preorder(T);
     cout<<endl;
     A.inorder(T);
     cout<<endl;
     A.postorder(T);
     cout<<endl;
    return 0;
     



}