/* ****************二叉树有关算法*************** */
/*********设计目标：教学演示**********************/
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#define stackinitsize 100
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int TElemType
typedef int Status
//一一一一一二叉树的二叉链表存储表示一一一一一
typedef struct BiTNode{
TElemType data
struct BiTNode *lchild,*rchild //左右孩子指针
}BiTnode,*SElemType,*BiTree
typedef struct{
//该堆栈的元素是指针类型的
//base和top均是指向指针的指针
SElemType *base
SElemType *top
int stacksize
int tag
}sqstack//堆栈结构
//一一一一一基本 *** 作的函数原型说明（部分）一一一一一
Status CreateBitree(BiTree &T)
//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。
//构造二叉链表表示的二叉树T.
void PreOrder(BiTree T)
//采用二叉链表存储结构，先序遍历二叉树T,对每个结点的访问就是输出它的值
void Inorder(BiTree T)
//采用二叉链表存储结构，中序遍历二叉树T,对每个结点的访问就是输出它的值
void Postorder(BiTree T)
//采用二叉链表存储结构，后序遍历二叉树T,对每个结点的访问就是输出它的值。
void InitStack(sqstack &s)//初始化堆栈
{
s.base=(SElemType*)malloc(100*sizeof(SElemType))
if(!s.base) return
s.top=s.base
s.stacksize=100
return
}
int StackEmpty(sqstack s) //栈空判别
{return(s.top==s.base)
}
void Pop(sqstack &s,SElemType &e)//d栈
{
e=*--s.top
}
Status GetTop(sqstack s,SElemType &e)
{
if(s.top==s.base) return ERROR
e=*(s.top-1)
return OK
}
void Push(sqstack &s,SElemType e)//将元素压入堆栈
{
*s.top++=e
}
Status CreateBiTree(BiTree &T){
//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。
//构造二叉链表表示的二叉树T.
char ch
ch=getche()
if(ch==' ') T=NULL
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) return(OVERFLOW)
T->data=ch//生成根结点
CreateBiTree(T->lchild)//构造左子树
CreateBiTree(T->rchild)//构造右子树
}
return OK
}//CreateBiTree
void PreOrder(BiTree T)
//采用二叉链表存储结构，先序遍历二叉树T,对每个结点的访问就是输出它的值
{
if(T)
{
printf("%c",T->data)
PreOrder(T->lchild)
PreOrder(T->rchild)
}
}//preOrderTraVerse
void InOrder(BiTree T)
//采用二叉链表存储结构，中序遍历二叉树T,对每个结点的访问就是输出它的值
{
if(T)
{
InOrder(T->lchild)
printf("%c",T->data)
InOrder(T->rchild)
}
}//inOrderTraVerse
void PostOrder(BiTree T)
//采用二叉链表存储结构，后序遍历二叉树T,对每个结点的访问就是输出它的值
{
if(T)
{
PostOrder(T->lchild)
PostOrder(T->rchild)
printf("%c",T->data)
}
}//posOrderTraVerse
void preord1(BiTree T)
//采用二叉链表存储结构，先序遍历二叉树T的非递归算法。
{sqstack s
BiTree p
InitStack(s)
if(T)
{
Push(s,T) //根结点入栈
while(!StackEmpty(s))//栈不为空时循环
{Pop(s,p)
printf("%c",p->data) //退栈并访问该结点
if(p->rchild) Push(s,p->rchild )//右孩子入栈
if(p->lchild) Push(s,p->lchild )//左孩子入栈
}
}
}
void inord1(BiTree T)
//采用二叉链表存储结构，中序遍历二叉树T的非递归算法。
{
return
}//Inord1
void inord2(BiTree T)
//采用二叉链表存储结构，visit是对数据元素 *** 作的应用函数。
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数visit。
{
}//Inord1
void posord1(BiTree T)
//采用二叉链表存储结构，后序遍历二叉树T的非递归算法。
{
BiTree p
BiTree stack[100]
int tag[100],top=0
p=T
do
{
while(p)//扫描左子树
{
top++
stack[top]=p
tag[top]=0
p=p->lchild
}
while(top>0&&tag[top]==1)
{ //p所指结点为无左子树的结点或其左子树已经遍历过
p=stack[top]
top--
printf("%c",p->data )//访问结点
}
if(top>0)
{
p=stack[top]
p=p->rchild //扫描右子树
tag[top]=1//表示当前的右子树已访问过
}
else break
}while(p||top!=0)
}
void main()
{
BiTree t
printf("\n请按先序遍历输入二叉树（当左右子树为空时用空格输入）\n")
CreateBiTree(t)
printf("\n该二叉树的先序遍历为：\n")
PreOrder(t)
printf("\n该二叉树的先序遍历为：(用非递归调用)\n")
preord1(t)
printf("\n该二叉树的中序遍历为：\n")
InOrder(t)
printf("\n该二叉树的中序遍历为：(用非递归调用1)\n")
inord1(t)
printf("\n该二叉树的中序遍历为：(用非递归调用2)\n")
inord2(t)
printf("\n该二叉树的后序遍历为：\n")
PostOrder(t)
printf("\n该二叉树的递归后序遍历为：\n")
posord1(t)
}
以word 2007为例，方法如下：1、依次单击“插入”、插图框中的“SmartArt”，在出现的对话框中选择“层次结构”、在右边出现的“组织结构图”中选中竖排或横排的结构图例，双击出现的“文本”，填写家谱姓氏辈份等信息。
2、家族人丁兴旺的可以在不同的辈份（行或列）添加多个文本，具体方法是点击想要添加位置附近文本框，在菜单栏中点击“添加形状”，在子菜单中选择在后、前、上、下添加即可。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）