基本信息
源码名称：二叉树 入门级示例源码
源码大小：0.01M
文件格式：.cpp
开发语言：C/C++
更新时间：2018-05-10
友情提示：（无需注册或充值，赞助后即可获取资源下载链接）
嘿，亲！知识可是无价之宝呢，但咱这精心整理的资料也耗费了不少心血呀。小小地破费一下，绝对物超所值哦！如有下载和支付问题，请联系我们QQ(微信同号)：813200300
本次赞助数额为： 2 元×
微信扫码支付：2 元
×
请留下您的邮箱，我们将在2小时内将文件发到您的邮箱
源码介绍
#include<stdio.h>
#include<stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OVERFLOW -2
#define INFEASIBLE -1
#define ERROR 0
#define FALSE 0
#define TRUE 1
#define OK 1
typedef int Status;
typedef char TElemType;
//---------二叉树的二叉线索存储表示-------
typedef enum {Link, Thread}PointerTag; //Link==0:指针，Thread==1:线索
typedef struct BiThrNode{
TElemType data;
struct BiThrNode *lchild, *rchild; //左右孩子指针
PointerTag LTag,RTag; //左右标志
}BiThrNode, *BiThrTree;
typedef BiThrTree SElemType;
//------Stack的储存结构----------
typedef struct Stack
{
SElemType *base; //存储空间的基址,在栈构造之前和销毁之后，base的值为NULL
SElemType *top; //栈顶指针
int stacksize; //当前已分配的存储空间，以元素为单位
} SqStack; //顺序栈类型
//-------Stack的函数声明---------
Status InitStack(SqStack &S) //构造一个空栈
{
S.base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); //分配存储空间
if(!S.base)
{ printf("分配存储失败！\n");
exit(OVERFLOW);
}
S.top = S.base; //S为空栈，S.top=S.base等于0
S.stacksize = STACK_INIT_SIZE; //栈的空间初始容量值
return OK;
}
Status GetTop(SqStack S,SElemType &e) //若栈不空，用 e返回栈顶元素 (注意这里的应用，后面会用到)
{
if(S.top==S.base)
return ERROR;
e = *(S.top-1);
return OK;
}
Status Push(SqStack &S,SElemType e) //入栈
{
if(S.top-S.base >= S.stacksize) //栈满，追加存储空间
{
S.base = (SElemType*)realloc(S.base,
(S.stacksize STACKINCREMENT)*sizeof(SElemType)); //通过realloc动态扩容
if(!S.base) //判断扩容是否成功
{
printf("存储空间不足，且扩展失败！");
exit(OVERFLOW);
}
S.top = S.base S.stacksize; //更新栈顶指针
S.stacksize = STACKINCREMENT; //更新栈的存储空间大小
}
*S.top = e; //将元素入栈,使S.top加1
return OK;
}
Status Pop(SqStack &S, SElemType &e) //栈顶元素出栈，赋给元素e
{
if(S.top==S.base) //栈空
return ERROR;
e = * --S.top; //栈顶元素出栈，并将S.top减1
return OK;
}//Pop
Status StackEmpty(SqStack S) //判断栈是否为空
{
if(S.top == S.base)
return TRUE;
else
return FALSE;
}
BiThrTree pre; //全局变量始终指向刚刚访问过的节点
//---------二叉树函数实现----------
Status CreateBiThrTree(BiThrTree &T) //先序构造二叉树，字符表示树，空格字符表示空树
{ char ch;
ch=getchar();
if(ch=='#')T=NULL;
else{
if(!(T=(BiThrNode *)malloc(sizeof(BiThrNode))))
{
printf("存储分配失败！");
exit(OVERFLOW);
}
T->data = ch; //生成根节点
CreateBiThrTree(T->lchild); //构造左子树
CreateBiThrTree(T->rchild); //构造右子树
}
return OK;
}//CreatBiTree
Status visit(TElemType e) //访问节点
{
printf("%c",e);
return OK;
}
Status PreOrderTraverse(BiThrTree T,Status(*visit)(TElemType )) //先序遍历
{
if(T){
if(visit(T->data)) //访问根节点
if(PreOrderTraverse(T->lchild,visit)) //先序遍历左子树
if(PreOrderTraverse(T->rchild,visit)) //先序遍历右子树
return OK;
return ERROR;
}
else return OK;
}//PreOrderTraverse
Status InOrderTraverse(BiThrTree T, Status( *visit)(TElemType )) // 中序遍历
{
if (T) {
InOrderTraverse(T->lchild, visit); // 中序遍历左子树
(*visit)(T->data); // 访问根结点
InOrderTraverse(T->rchild, visit); // 中序遍历右子树
}
return OK;
}
Status PostOrderTraverse (BiThrTree T, Status( *visit)(TElemType )) // 后序遍历二叉树
{
if (T) {
PostOrderTraverse(T->lchild, visit); //后序遍历左子树
PostOrderTraverse(T->rchild, visit);//后序遍历右子树
(*visit)(T->data); // 访问根结点
}
return OK;
}
Status PreOrderTraverse_nr(BiThrTree T,Status(*visit)(TElemType e)) //非递归前序遍历
{
BiThrTree p;
p = T;
SqStack S; // 声明栈S
InitStack(S);
while (!StackEmpty(S)|| p) //边遍历边打印，并存入栈中，以后需要借助这些根节点进入右子树
{
if(p)
{
if(!visit(p->data))return ERROR;
Push(S,p);
p = p->lchild;
}
else //当p为空时，说明根和左子树都遍历完了，该进入右子树了
{
Pop(S,p); //s.pop();
p = p->rchild;
}//else
}//while
return OK;
}
Status InOrderTraverse_nr(BiThrTree T,Status(*visit)(TElemType e)) //非递归中序遍历(nr,nonrecursively，非递归地)
{
BiThrTree p;
p = T;
SqStack S; // 声明栈S
InitStack(S);
while (!StackEmpty(S)|| p) //边遍历边打印，并存入栈中，以后需要借助这些根节点进入右子树
{
if(p)
{
Push(S,p);
p = p->lchild;
}
else //当p为空时，说明根和左子树都遍历完了，该进入右子树了
{
Pop(S,p);
if(!visit(p->data))return ERROR;
p = p->rchild;
}//else
}//while
return OK;
}//InOrderTrayerse_nr
Status PostOrderTraverse_nr(BiThrTree T,Status(*visit)(TElemType e))//非递归后序遍历
{
SqStack S; // 声明栈S
InitStack(S);
BiThrTree pCur, pLastVisit; //pCur:当前访问节点，pLastVisit:上次访问节点
pCur = T;
pLastVisit = NULL;
while (pCur) //先把pCur移动到左子树最下边
{
Push(S,pCur);
pCur = pCur->lchild;
}
while (!StackEmpty(S))
{
//走到这里，pCur都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
Pop(S,pCur);
if (pCur->rchild == NULL || pCur->rchild == pLastVisit) //一个根节点被访问的前提是：无右子树或右子树已被访问过
{
if(!visit(pCur->data))return ERROR; //访问结点
pLastVisit = pCur; //修改最近被访问的节点
}
/*这里的else语句可换成带条件的else if:
else if (pCur->lchild == pLastVisit)//若左子树刚被访问过，则需先进入右子树(根节点需再次入栈)
因为：上面的条件没通过就一定是下面的条件满足。仔细想想！
*/
else
{
Push(S,pCur); //根节点再次入栈
pCur = pCur->rchild; //进入右子树，且可肯定右子树一定不为空
while (pCur)
{
Push(S,pCur);
pCur = pCur->lchild;
}
}
}
return OK;
}
Status CountLeaf(BiThrTree T) //返回指针T所指二叉树中所有叶子结点个数
{
int m,n;
if (!T ) return 0;
if (!T->lchild && !T->rchild) return 1;
else{
m = CountLeaf( T->lchild);
n = CountLeaf( T->rchild);
return (m n);
} //else
} // CountLeaf
Status Depth(BiThrTree T) // 返回二叉树的深度
{
int depthLeft=0,depthRight=0,depthval=0;
if ( !T )
depthval = 0;
else
{
depthLeft = Depth( T->lchild );
depthRight= Depth( T->rchild );
depthval = 1 (depthLeft > depthRight ?
depthLeft : depthRight);
}
return depthval;
}
Status InThreading(BiThrTree p) //中序线索化
{
if(p)
{
InThreading(p->lchild); //左子树线索化
if(!p->lchild) //若没有左孩子
{
p->LTag = Thread; //当前结点前驱线索
p->lchild = pre; //左孩子指针指向前驱
}
else
p->LTag = Link;
if(!pre->rchild) //前驱没有右孩子
{pre->RTag = Thread; //后继线索
pre->rchild = p; //前驱的右孩子指针指向后继（当前节点p）
}else
p->RTag = Link;
pre = p; //保持pre指向p的前驱
InThreading(p->rchild); //右子树线索化
}
return OK;
}// InThreading
Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) //中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。
{
if(!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode))))
{
printf("分配内存失败！\n");
exit(OVERFLOW);
}
Thrt->LTag = Link;
Thrt->RTag = Thread; //建立头结点
Thrt->rchild = Thrt; //左指针回指
if(!T)
Thrt->lchild = Thrt; //若二叉树为空，则左指针回指
else
{
Thrt->lchild = T;
pre = Thrt;
InThreading(T); //中序遍历进行中序线索化
pre->rchild = Thrt;
pre->RTag = Thread; //最后一个结点线索化
Thrt->rchild = pre;
}
return OK;
}//InOrderThreading
Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(TElemType)) //中序遍历二叉线索书T的非递归算法
{ //T指向头结点，头结点的左链lchild指向根节点
BiThrTree p2;
p2=T->lchild; //p指向根节点
while(p2!=T) //空树或遍历结束时，p==T
{
while(p2->LTag==Link)
p2=p2->lchild; //直到最左
if(!visit(p2->data)) //访问其左子树为空的结点
return ERROR;
while(p2->RTag==Thread && p2->rchild != T)//如果该结点的后继不是头结点，访问它的后继结点
{
p2 = p2->rchild; //p2->RTag线索， p2->rchild指向其后继
visit(p2->data); //访问后继结点
}
p2 = p2->rchild; //更新当前结点
}
return OK;
}//InOrderTraverse_Thr
void display()//登陆界面
{ int n,m=1;
BiThrTree T;
BiThrTree Thrt;
printf(" ◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇\n");
printf(" ◆ 欢迎使用 B126二叉树 ◆\n");
printf(" ◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇\n\n");
printf(" 测试二叉树：AB#CD###EFGH##K####\n");
printf("请按先序次序输入树(#代表空树)：\n");
CreateBiThrTree(T);
do{
printf("★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆\n");
printf("☆请输入你想操作的序号: ★\n");
printf("★ 0)退出 ☆\n");
printf("☆ 1)先序遍历 ★\n");
printf("★ 2)先序遍历（非递归） ☆\n");
printf("☆ 3)中序遍历 ★\n");
printf("★ 4)中序遍历（非递归） ☆\n");
printf("☆ 5)后序遍历 ★\n");
printf("★ 6)后序遍历（非递归） ☆\n");
printf("☆ 7)统计叶子结点个数 ★\n");
printf("★ 8)计算二叉树的深度 ☆\n");
printf("☆ 9)中序线索树二叉树 ★\n");
printf("★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆\n");
scanf("%d",&n);
if(n<0||n>9)
{
printf("您输入的序号不正确，请重新输入:\n");
scanf("%d",&n);
}
switch(n)
{
case 0:printf("Goodbye!\n");m =0 ;exit(0);break;
case 1:{printf("先序遍历一棵树：\n");PreOrderTraverse(T,visit);printf("\n");break;}
case 2:{printf("先续遍历一棵树(非递归实现)： \n");PreOrderTraverse_nr(T,visit);printf("\n");break;}
case 3:{printf("中续遍历一棵树： \n");InOrderTraverse(T,visit);printf("\n");break; }
case 4:{printf("中续遍历一棵树(非递归实现)： \n");InOrderTraverse_nr(T,visit);printf("\n");break;}
case 5:{printf("后续遍历一棵树： \n");PostOrderTraverse (T,visit);printf("\n"); break;}
case 6:{printf("后续遍历一棵树(非递归实现)： \n");PostOrderTraverse_nr(T,visit);printf("\n");break;}
case 7:{printf("统计叶子结点个数 \n");printf("%d\n",CountLeaf (T));break;}
case 8:{printf("计算二叉树的深度：\n");printf("%d\n", Depth(T));break;}
case 9:{printf("输出中序线索树二叉树的内容:\n");InOrderThreading(Thrt, T);InOrderTraverse_Thr(Thrt,visit);printf("\n");break;}
}
}
while(m!=0);
}
//
int main()
{
//BiThrTree T;
//BiThrTree Thrt;
display();
return 0;
}