1. 建立二叉樹，層序、先序、中序、後序遍歷（ 用遞歸或非遞歸的方法都需要）以及中序線索化
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define Max 20 //結點的最大個數typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定義二叉樹的結點類型typedef BinTNode *BinTree; //定義二叉樹的指針int NodeNum,leaf; //NodeNum為結點數，leaf為葉子數
//==========基於先序遍歷演算法創建二叉樹==============
//=====要求輸入先序序列，其中加入虛結點"#"以示空指針的位置==========
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //讀入#，返回空指針
else{
T=(BinTNode *)malloc(sizeof(BinTNode)); //生成結點
T->data=ch;
T->lchild=CreatBinTree(); //構造左子樹
T->rchild=CreatBinTree(); //構造右子樹
return(T);
}
}
//========NLR 先序遍歷=============
void Preorder(BinTree T)
{
if(T) {
printf("%c",T->data); //訪問結點
Preorder(T->lchild); //先序遍歷左子樹
Preorder(T->rchild); //先序遍歷右子樹
}
}
//========LNR 中序遍歷===============
void Inorder(BinTree T)
{
if(T) {
Inorder(T->lchild); //中序遍歷左子樹
printf("%c",T->data); //訪問結點
Inorder(T->rchild); //中序遍歷右子樹
}
}
//==========LRN 後序遍歷============
void Postorder(BinTree T)
{
if(T) {
Postorder(T->lchild); //後序遍歷左子樹
Postorder(T->rchild); //後序遍歷右子樹
printf("%c",T->data); //訪問結點
}
}
//=====採用後序遍歷求二叉樹的深度、結點數及葉子數的遞歸演算法========
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求結點數
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度為0，即為葉子。
return(max+1);
}
else return(0);
}
//====利用"先進先出"（FIFO）隊列，按層次遍歷二叉樹==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定義結點的指針數組cq
cq[1]=T; //根入隊
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出隊
printf("%c",p->data); //出隊，輸出結點的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子樹入隊
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子樹入隊
}
}
}
//==========主函數=================
void main()
{
BinTree root;
int i,depth;
printf("\n");
printf("Creat Bin_Tree;Input preorder:"); //輸入完全二叉樹的先序序列，
// 用#代表虛結點，如ABD###CE##F##
root=CreatBinTree(); //創建二叉樹，返回根結點
//do { //從菜單中選擇遍歷方式，輸入序號。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t5: Level Depth\n"); //按層次遍歷之前，先選擇4，求出該樹的結點數。
printf("\t0: Exit\n");
printf("\t*******************************\n");
do { //從菜單中選擇遍歷方式，輸入序號。
scanf("%d",&i); //輸入菜單序號（0-5）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍歷
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍歷
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //後序遍歷
break;
case 4: depth=TreeDepth(root); //求樹的深度及葉子數
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5: printf("LevePrint Bin_Tree: ");
Levelorder(root); //按層次遍歷
break;
default: exit(1);
}
printf("\n");
} while(i!=0);
}
2. 數據結構考試，二叉樹的中序遍歷的非遞歸演算法是什麼
第一題：
boolInOrderTraverse(BinNode*Node,void(*fun)(BinNode*Node))
{
StackS;//聲明棧
InitBtStack(&);//初始化棧
while(!StackIsEmpty(&S)||Node)//棧空且節點為NULL是遍歷完成
{
while(Node->lchild)//如果<節點左子樹非空>則進棧,直到左子樹為空的節點
{
Push(&S,&Node);
Node=Node->lchild;
}//while
(*fun)(Node);//訪問該節點(左子樹為空的節點)
Node=Node->rchlid;//轉向其右子樹
while(!StackIsEmpty(&S)&&!Node)//如果棧非空且右子樹為空,彈出並退{//回棧頂節點,訪問之,一直到右子樹非空的節點
Pop(&S,&Node);
(*fun)(Node);//訪問之
Node=Node->rchlid;//轉向其右子樹(出棧節點的左子樹必然已被遍歷）
}//while
}//while
DestroyStack(&S);
returntrue;
}//InOrderTraverse
第二題：
第一個while是把棧S的中的元素臨時轉移到棧T中，直到遇到等於e的(e出棧S但沒有進棧T）。
第二個while是把棧T中的元素全部放回棧S中。
結果是：刪除了S棧中<離棧頂最近,值為e>的元素。
第三題：stack
第四題：
前序串的K應該是D。
樹的構型：
A
/
BF
/\
ECG
/
DHJ
I
後序序列：EDCBIHJGFA
根據後序序列易得線索：
E:lchild=NULLright=&D
C:lchild=&D
D:lchild=&Eright=&C
F:lchild=&G
H:lchild=&I
I:lchild=&Bright=&H
J:lchild=&Hright=&G