/*一下总结一些二叉树的常见操作：包括建立二叉树  先/中/后序遍历二叉树  求二叉树的叶子节点个数 
求二叉树的单分支节点个数  计算二叉树双分支节点个数  计算二叉树的高度  计算二叉树的所有叶子节点数*/
#include<stdio.h> //c语言的头文件
#include<stdlib.h>//c语言的头文件 stdlib.h千万别写错了
#define Maxsize 100
/*创建二叉树的节点*/
typedef struct BTNode            //结构体  struct 是关键字不能省略  结构体名字可以省略（为无名结构体） 
                                //成员类型可以是基本型或者构造形，最后的为结构体变量。
{
    char data;
    struct BTNode *lchild,*rchild;
}*Bitree;
/*使用先序建立二叉树*/
Bitree Createtree()  //树的建立
{
    char ch;
    Bitree T;
    ch=getchar(); //输入一个二叉树数据
    if(ch==' ') //' '中间有一个空格的。
   
        T=NULL;
    else
    { T=(Bitree)malloc(sizeof(Bitree)); //生成二叉树  (分配类型 *)malloc(分配元素个数 *sizeof(分配类型))
    T->data=ch;
      T->lchild=Createtree();  //递归创建左子树
      T->rchild=Createtree();  //地柜创建右子树
    }
    return T;//返回根节点
}
/*下面先序遍历二叉树*/
/*void preorder(Bitree T)  //先序遍历
{ 
    if(T) 
    {   
        printf("%c-",T->data); 
        preorder(T->lchild); 
        preorder(T->rchild); 
    } 
} */
/*下面先序遍历二叉树非递归算法设计*/
void preorder(Bitree T)  //先序遍历非递归算法设计
{
    Bitree st[Maxsize];//定义循环队列存放节点的指针
    Bitree p;
    int top=-1;  //栈置空
    if(T)
    {
        top++;
        st[top]=T;  //根节点进栈
        while(top>-1)  //栈不空时循环
        {
            p=st[top];  //栈顶指针出栈
            top--;
            printf("%c-",p->data );
            if(p->rchild !=NULL)  //右孩子存在进栈
            {
                top++;
                st[top]=p->rchild ;
            }
            if(p->lchild !=NULL)  //左孩子存在进栈
            {
                top++;
                st[top]=p->lchild ;
            }
        }
        printf("\n");
    }
}
/*下面中序遍历二叉树*/
/*void inorder(Bitree T)  //中序遍历
{ 
    if(T) 
    {   
        inorder(T->lchild);
        printf("%c-",T->data); 
        inorder(T->rchild); 
    } 
} 
*/
/*下面中序遍历二叉树非递归算法设计*/
void inorder(Bitree T)  //中序遍历
{
    Bitree st[Maxsize];  //定义循环队列，存放节点的指针
    Bitree p;
    int top=-1;
    if(T)
    {
        p=T;
        while (top>-1||p!=NULL)          //栈不空或者*不空是循环
        {
            while(p!=NULL)              //扫描*p的所有左孩子并进栈
            {
                top++;
                st[top]=p;
                p=p->lchild ;
            }
            if(top>-1)
            {
                p=st[top];              //出栈*p节点，它没有右孩子或右孩子已被访问。
                top--;
                printf("%c-",p->data );  //访问
                p=p->rchild ;            //扫描*p的右孩子节点
            }
先序中序后序遍历二叉树
        }
        printf("\n");
    }
}
     
/*下面后序遍历二叉树*/
/*void postorder(Bitree T)  //后序遍历
{ 
    if(T) 
    {   
        postorder(T->lchild);   
        postorder(T->rchild);
        printf("%c-",T->data);
    } 
} 
*/
/*二叉树后序遍历非递归算法设计*/
void postorder(Bitree T) //后序遍历非递归
{
    Bitree st[Maxsize];
    Bitree p=T,q;
    int flag;        //作为一个标志处理栈定时候用
    int top=-1;    //栈置空
    if(T)
    {
        do
        {
            while(p)  //将*p所在的左节点进栈
            {
                top++;
                st[top]=p;
                p=p->lchild ;
            }
            q=NULL;
            flag=1;  //设置flag=1表示处理栈顶节点
            while(top!=-1&&flag==1)
            {
                p=st[top];
                if(p->rchild==q)  //右孩子不存在或者右孩子已被访问，访问之
                {
                    printf("%c-",p->data );
                    top--;
                    q=p;    //让q指向刚被访问的节点
                }
                else
                {
                    p=p->rchild ;  //p指向右孩子
                    flag=0;  //设置flag=0表示栈顶节点处理完毕
                }
            }
        }while(top!=-1) ;//栈不空是循环

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。