博客

//很久以前自己整理的代码，也有部分参考了网络上前辈的经验
#include <stdio.h>
#include <stdlib.h>
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define MAX 100
#include <math.h>
#include <windows.h>

//typedef enum { Link, Thread } PointerThr;  // Link==0:指针，Thread==1:线索

typedef struct BiThrNode{
   int data;
   struct BiThrNode  *lchild, *rchild;  // 左右指针
   int         LTag, RTag;    // 左右标志
} BiThrNode, *BiThrTree;

typedef struct QNode
{
 BiThrNode *data;
 struct QNode *next;
}QNode, *QueuePtr;

typedef struct
{
 QueuePtr front;
 QueuePtr rear;
}LinkQueue;

//以下为队列操作，用于层序遍历输出树形结构
//构造一个空队列Q
int InitQueue(LinkQueue &Q)
{
 Q.front = Q.rear = (QNode *)malloc(sizeof(QNode));
 if(!Q.front)
  return 0;
 Q.front->next = NULL;
 return OK;
}

//进队操作函数
int EnQueue(LinkQueue &Q, BiThrNode *e)
{
 QNode *p;
 p = (QNode *)malloc(sizeof(QNode));
 if(!p)
  return 0;
 p->data = e;
 p->next = NULL;
 Q.rear->next = p;
 Q.rear = p;
 return OK;
}

//出队操作
BiThrNode * DeQueue(LinkQueue &Q)
{
 QNode *p;
 BiThrNode *e;
 if(Q.front == Q.rear)
  return NULL;
 p = Q.front->next;
 e = p->data;
 Q.front->next = p->next;
 if(Q.rear == p)
  Q.rear = Q.front;
 free(p);
 return e;
}

//二叉树深度
int FindDepth(BiThrTree pRoot)
{
    if(pRoot == NULL) 
    return 0; 
    else 
 {
        int a = FindDepth(pRoot->lchild); 
        int b = FindDepth(pRoot->rchild); 
        return (a>b?a:b)+1; 
 } //所以，如果给出二叉树的根结点，带入这个函数就能求出其深度了
}

//打印二叉树树形结构
void PrintBiTree(BiThrTree T)
{
 int row = FindDepth(T);
 BiThrNode *p = T;
 LinkQueue Q;
 InitQueue(Q);

 EnQueue(Q, T);//根进队
 for(int i = 0; i < row; i++)//层序遍历，分层打印
 {
  printf("=");//左边缘
  for(int k = 0; k < pow(2,i); k++)
  {
   for(int j = 0; j < (pow(2,row - i - 1) - 1); j++)//从第一行开始缩进2^(row - i -1) - 1个空格
    printf("=");
   p = DeQueue(Q);//出队
   if(p)
    printf("%c",p->data);//当出队的结点存在时打印p->data
   else
    printf("@");//当结点不存在时打印@

   if(!p)//当出对的元素为NULL时，入队2个NULL，模拟其的左右孩子（下次就会打印出@，最后一行的左右孩子无需再打印）
   {
    EnQueue(Q,NULL);
    EnQueue(Q,NULL);
   }
   else
   {
    if(p->lchild)//当结点的左右孩子存在时，左右孩子入队，不存在时NULL入队（下次出队时输出数据或@）
     EnQueue(Q,p->lchild);
    else
     EnQueue(Q,NULL);
    
    if(p->rchild)
     EnQueue(Q,p->rchild);
    else
     EnQueue(Q,NULL);
   }  
   for(j = 0; j <= (pow(2,row - i - 1) - 1); j++)
    printf("=");
  }  
  printf("\n");//每打完一层换行
 }


}
//建立二叉树

//先序建立二叉树
void CreateBiTree(BiThrTree &pRoot) 
{
    char ch;
    scanf("%c",&ch);   
 getchar();
    if(ch == '@')        //输入0 时代表空（叶子节点左右子树为空）
 { 
        pRoot = NULL; 
 }
    else //如果不是叶子结点
 {
        pRoot = (BiThrNode *)malloc(sizeof(BiThrNode)); 
        pRoot->data = ch; 
  pRoot->lchild =NULL;
  pRoot->rchild =NULL;         
  pRoot->LTag=0;
  pRoot->RTag=0;
        CreateBiTree(pRoot->lchild); //以这个结点的左孩子结点为根结点，以同样的方法再建立二叉树
        CreateBiTree(pRoot->rchild); //左子树建立好后，以这个结点的右孩子结点为根结点，再建立二叉树
 } //pRoot的左右子树都建立好后，整个二叉树就建立好了，函数结束
}

// 先序遍历二叉树
void PreTravelBiTree(BiThrTree pRoot) //这里的参数没有用引用，当然也可以用引用
{
    if(pRoot == NULL) //如果当前结点为空
       return ;      
    else              //如果访结点不为空
 {
        printf("%c ",pRoot->data);       //那么先输入这个结点里保存的数据，先做这一步，也是体现了“先序遍历”  
        PreTravelBiTree(pRoot->lchild); //再以这个结点的左孩子为根结点，同样的方法访问其左子树
        PreTravelBiTree(pRoot->rchild); //访问右子树
 } 
} 

// 中序遍历二叉树
void MidTravelBiTree(BiThrTree pRoot)
{
    if(pRoot == NULL)
      return ;
    else
 {
        MidTravelBiTree(pRoot->lchild); //对当前结点pRoot来说，要先访问其左子树
        printf("%c ",pRoot->data);       //再输出当前结点pRoot中保存的内容
        MidTravelBiTree(pRoot->rchild); //再访问其右子树
 }
}

// 后序遍历二叉树
void PostTravelBiTree(BiThrTree pRoot)
{
    if(pRoot == NULL)
      return ;
    else
 {
        PostTravelBiTree(pRoot->lchild); //对当前结点pRoot来说，要先访问其左子树
        PostTravelBiTree(pRoot->rchild); //再访问其右子树
        printf("%c ",pRoot->data);        //输出当前结点pRoot中保存的内容;
 }
}


//释放二叉树
void FreeBiTree(BiThrTree pRoot)
{
    if(!pRoot) 
       return; 
    free(pRoot->lchild); //如果没有返回，则说明该结点不为空，那么释放其左子树
    free(pRoot->rchild); 
    free(pRoot);             
} 

BiThrTree pre = NULL;//设置前驱 

//将二叉树p中序线索化（确定各个节点之间的pre关系）
void InOrderThreading(BiThrTree p) 
{ 
 if(p) 
    { 
        InOrderThreading(p -> lchild);   //左子树中序线索化 
  if(p->lchild==NULL)  p->LTag=1;    //左孩子为NULL,建立左线索标志
  if(p->rchild==NULL)  p->RTag=1;    
  if(pre!=NULL)//pre存在，即要满足以下要求：
  {
   if(pre->RTag==1)               // 当当前节点p无右子树
    pre->rchild=p;             //（用pre空余的rchild指针（代表后继）指向p）即Pre为p的前驱
   if(p->LTag==1)                 //当当前节点p无左子树
    p->lchild=pre;             //即p的前驱为pre
  }
        pre = p;    //从而达到保持pre指向p的前驱的要求 
        InOrderThreading(p -> rchild); //右子树中序线索化 
     } 
 }
 
//查找中序的后继节点
BiThrTree InOrderNext(BiThrTree p)
{
 BiThrTree q;
 if(p->RTag==1)               //优先确定是否可以直接找到后继（标志为1即有后继，右孩子为空）
  return(p->rchild);       //直接返回后继即可
 else                         
 {                            //p无法直接找到后继（RTag = 0）
  q=p->rchild;             //从p的右孩子开始查找
  while(q->LTag==0)        //找到其最左孩子返回（中序遍历需要从最左开始）
   q=q->lchild;
  return(q);
 }
}

//中序遍历中序线索二叉树（即利用节点pre关系遍历输出，和普通的遍历有所区别）
void InOrderTraverse_Thr(BiThrTree p)
{
 printf("中序遍历中序线索化二叉树: ");
 if(p!=NULL)                  //非空树
 {
  while(p->LTag==0)        //有左孩子就一直找下去（查找中序序列的开始结点）
   p=p->lchild;
  do
  {
   printf("%c ",p->data);   //访问结点p
   p=InOrderNext(p);            //查找p的中序后继结点
  } while(p!=NULL);
 }
 printf("\n\n");
}
#include "X.h"


void main()
{
    BiThrTree pRoot = NULL,Thrt = NULL;
    printf("先序建立二叉树(字符@表示空)：\n");
    CreateBiTree(pRoot);

 printf("\n树形结构：\n");
 PrintBiTree(pRoot);
 printf("\n二叉树的深度为：%d ",FindDepth(pRoot)); 
    printf("\n前序遍历结果："); 
    PreTravelBiTree(pRoot); 
    printf("\n中序遍历结果：");
    MidTravelBiTree(pRoot); 
    printf("\n后序遍历结果：");
    PostTravelBiTree(pRoot); 
    
    //FreeBiTree(pRoot); 
    printf("\n\n");
    //将二叉树T改变为其中序线索二叉树        
    InOrderThreading(pRoot);
    InOrderTraverse_Thr(pRoot); 
}