//轉(zhuǎn)載請(qǐng)標(biāo)明出處拉庵，原文地址：http://blog.csdn.net/hackbuteer1/article/details/6583988

#include

#include

#include

usingnamespacestd;

//二叉樹結(jié)點(diǎn)的描述

typedefstructBiTNode

{

chardata;

structBiTNode?*lchild,?*rchild;//左右孩子

}BiTNode,*BiTree;

//按先序遍歷創(chuàng)建二叉樹

//BiTree?*CreateBiTree()?????//返回結(jié)點(diǎn)指針類型

//void?CreateBiTree(BiTree?&root)??????//引用類型的參數(shù)

voidCreateBiTree(BiTNode?**root)//二級(jí)指針作為函數(shù)參數(shù)

{

charch;//要插入的數(shù)據(jù)

scanf("\n%c",?&ch);

//cin>>ch;

if(ch=='#')

*root?=?NULL;

else

{

*root?=?(BiTNode?*)malloc(sizeof(BiTNode));

(*root)->data?=?ch;

printf("請(qǐng)輸入%c的左孩子：",ch);

CreateBiTree(&((*root)->lchild));

printf("請(qǐng)輸入%c的右孩子：",ch);

CreateBiTree(&((*root)->rchild));

}

}

//前序遍歷的算法程序

voidPreOrder(BiTNode?*root)

{

if(root==NULL)

return;

printf("%c?",?root->data);//輸出數(shù)據(jù)

PreOrder(root->lchild);//遞歸調(diào)用，前序遍歷左子樹

PreOrder(root->rchild);//遞歸調(diào)用，前序遍歷右子樹

}

//中序遍歷的算法程序

voidInOrder(BiTNode?*root)

{

if(root==NULL)

return;

InOrder(root->lchild);//遞歸調(diào)用葡公，前序遍歷左子樹

printf("%c?",?root->data);//輸出數(shù)據(jù)

InOrder(root->rchild);//遞歸調(diào)用，前序遍歷右子樹

}

//后序遍歷的算法程序

voidPostOrder(BiTNode?*root)

{

if(root==NULL)

return;

PostOrder(root->lchild);//遞歸調(diào)用，前序遍歷左子樹

PostOrder(root->rchild);//遞歸調(diào)用，前序遍歷右子樹

printf("%c?",?root->data);//輸出數(shù)據(jù)

}

/*

二叉樹的非遞歸前序遍歷蜒车，前序遍歷思想：先讓根進(jìn)棧，只要棧不為空幔嗦，就可以做彈出操作酿愧，

每次彈出一個(gè)結(jié)點(diǎn)，記得把它的左右結(jié)點(diǎn)都進(jìn)棧邀泉，記得右子樹先進(jìn)棧嬉挡，這樣可以保證右子樹在棧中總處于左子樹的下面。

*/

voidPreOrder_Nonrecursive(BiTree?T)//先序遍歷的非遞歸

{

if(!T)

return;

stack?s;

s.push(T);

while(!s.empty())

{

BiTree?temp?=?s.top();

cout<data<<"?";

s.pop();

if(temp->rchild)

s.push(temp->rchild);

if(temp->lchild)

s.push(temp->lchild);

}

}

voidPreOrder_Nonrecursive1(BiTree?T)//先序遍歷的非遞歸

{

if(!T)

return;

stack?s;

BiTree?curr?=?T;

while(curr?!=?NULL?||?!s.empty())

{

while(curr?!=?NULL)

{

cout<data<<"??";

s.push(curr);

curr?=?curr->lchild;

}

if(!s.empty())

{

curr?=?s.top();

s.pop();

curr?=?curr->rchild;

}

}

}

voidPreOrder_Nonrecursive2(BiTree?T)//先序遍歷的非遞歸

{

if(!T)

return;

stack?s;

while(T)//?左子樹上的節(jié)點(diǎn)全部壓入到棧中

{

s.push(T);

cout<data<<"??";

T?=?T->lchild;

}

while(!s.empty())

{

BiTree?temp?=?s.top()->rchild;//?棧頂元素的右子樹

s.pop();//?彈出棧頂元素

while(temp)//?棧頂元素存在右子樹汇恤，則對(duì)右子樹同樣遍歷到最下方

{

cout<data<<"??";

s.push(temp);

temp?=?temp->lchild;

}

}

}

voidInOrderTraverse1(BiTree?T)//?中序遍歷的非遞歸

{

if(!T)

return;

BiTree?curr?=?T;//?指向當(dāng)前要檢查的節(jié)點(diǎn)

stack?s;

while(curr?!=?NULL?||?!s.empty())

{

while(curr?!=?NULL)

{

s.push(curr);

curr?=?curr->lchild;

}//while

if(!s.empty())

{

curr?=?s.top();

s.pop();

cout<data<<"??";

curr?=?curr->rchild;

}

}

}

voidInOrderTraverse(BiTree?T)//?中序遍歷的非遞歸

{

if(!T)

return;

stack?s;

BiTree?curr?=?T->lchild;//?指向當(dāng)前要檢查的節(jié)點(diǎn)

s.push(T);

while(curr?!=?NULL?||?!s.empty())

{

while(curr?!=?NULL)//?一直向左走

{

s.push(curr);

curr?=?curr->lchild;

}

curr?=?s.top();

s.pop();

cout<data<<"??";

curr?=?curr->rchild;

}

}

voidPostOrder_Nonrecursive1(BiTree?T)//?后序遍歷的非遞歸

{

stack?S;

BiTree?curr?=?T?;//?指向當(dāng)前要檢查的節(jié)點(diǎn)

BiTree?previsited?=?NULL;//?指向前一個(gè)被訪問的節(jié)點(diǎn)

while(curr?!=?NULL?||?!S.empty())//?椗痈郑空時(shí)結(jié)束

{

while(curr?!=?NULL)//?一直向左走直到為空

{

S.push(curr);

curr?=?curr->lchild;

}

curr?=?S.top();

//?當(dāng)前節(jié)點(diǎn)的右孩子如果為空或者已經(jīng)被訪問，則訪問當(dāng)前節(jié)點(diǎn)

if(curr->rchild?==?NULL?||?curr->rchild?==?previsited)

{

cout<data<<"??";

previsited?=?curr;

S.pop();

curr?=?NULL;

}

else

curr?=?curr->rchild;//?否則訪問右孩子

}

}

voidPostOrder_Nonrecursive(BiTree?T)//?后序遍歷的非遞歸?????雙棧法

{

stack?s1?,?s2;

BiTree?curr?;//?指向當(dāng)前要檢查的節(jié)點(diǎn)

s1.push(T);

while(!s1.empty())//?椧蚧眩空時(shí)結(jié)束

{

curr?=?s1.top();

s1.pop();

s2.push(curr);

if(curr->lchild)

s1.push(curr->lchild);

if(curr->rchild)

s1.push(curr->rchild);

}

while(!s2.empty())

{

printf("%c?",?s2.top()->data);

s2.pop();

}

}

intvisit(BiTree?T)

{

if(T)

{

printf("%c?",T->data);

return1;

}

else

return0;

}

voidLeverTraverse(BiTree?T)//方法一基括、非遞歸層次遍歷二叉樹

{

queue??Q;

BiTree?p;

p?=?T;

if(visit(p)==1)

Q.push(p);

while(!Q.empty())

{

p?=?Q.front();

Q.pop();

if(visit(p->lchild)?==?1)

Q.push(p->lchild);

if(visit(p->rchild)?==?1)

Q.push(p->rchild);

}

}

voidLevelOrder(BiTree?BT)//方法二、非遞歸層次遍歷二叉樹

{

BiTNode?*queue[10];//定義隊(duì)列有十個(gè)空間

if(BT==NULL)

return;

intfront,rear;

front=rear=0;

queue[rear++]=BT;

while(front!=rear)//如果隊(duì)尾指針不等于對(duì)頭指針時(shí)

{

cout<data<<"??";//輸出遍歷結(jié)果

if(queue[front]->lchild!=NULL)//將隊(duì)首結(jié)點(diǎn)的左孩子指針入隊(duì)列

{

queue[rear]=queue[front]->lchild;

rear++;//隊(duì)尾指針后移一位

}

if(queue[front]->rchild!=NULL)

{

queue[rear]=queue[front]->rchild;//將隊(duì)首結(jié)點(diǎn)的右孩子指針入隊(duì)列

rear++;//隊(duì)尾指針后移一位

}

front++;//對(duì)頭指針后移一位

}

}

intdepth(BiTNode?*T)//樹的深度

{

if(!T)

return0;

intd1,d2;

d1=depth(T->lchild);

d2=depth(T->rchild);

return(d1>d2?d1:d2)+1;

//return?(depth(T->lchild)>depth(T->rchild)?depth(T->lchild):depth(T->rchild))+1;

}

intCountNode(BiTNode?*T)

{

if(T?==?NULL)

return0;

return1+CountNode(T->lchild)+CountNode(T->rchild);

}

intmain(void)

{

BiTNode?*root=NULL;//定義一個(gè)根結(jié)點(diǎn)

intflag=1,k;

printf("?????????????????????本程序?qū)崿F(xiàn)二叉樹的基本操作蓝角。\n");

printf("可以進(jìn)行建立二叉樹阱穗，遞歸先序、中序使鹅、后序遍歷，非遞歸先序昌抠、中序遍歷及非遞歸層序遍歷等操作患朱。\n");

while(flag)

{

printf("\n");

printf("|--------------------------------------------------------------|\n");

printf("|????????????????????二叉樹的基本操作如下:?????????????????????|\n");

printf("|????????????????????????0.創(chuàng)建二叉樹??????????????????????????|\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.二叉樹的結(jié)點(diǎn)個(gè)數(shù)????????????????????|\n");

printf("|????????????????????????10.退出程序????????????????????????????|\n");

printf("|--------------------------------------------------------------|\n");

printf("????????????????????????請(qǐng)選擇功能：");

scanf("%d",&k);

switch(k)

{

case0:

printf("請(qǐng)建立二叉樹并輸入二叉樹的根節(jié)點(diǎn)：");

CreateBiTree(&root);

break;

case1:

if(root)

{

printf("遞歸先序遍歷二叉樹的結(jié)果為：");

PreOrder(root);

printf("\n");

}

else

printf("??????????二叉樹為空！\n");

break;

case2:

if(root)

{

printf("遞歸中序遍歷二叉樹的結(jié)果為：");

InOrder(root);

printf("\n");

}

else

printf("??????????二叉樹為空炊苫！\n");

break;

case3:

if(root)

{

printf("遞歸后序遍歷二叉樹的結(jié)果為：");

PostOrder(root);

printf("\n");

}

else

printf("??????????二叉樹為空裁厅！\n");

break;

case4:

if(root)

{

printf("非遞歸先序遍歷二叉樹：");

PreOrder_Nonrecursive1(root);

printf("\n");

}

else

printf("??????????二叉樹為空冰沙！\n");

break;

case5:

if(root)

{

printf("非遞歸中序遍歷二叉樹：");

InOrderTraverse1(root);

printf("\n");

}

else

printf("??????????二叉樹為空！\n");

break;

case6:

if(root)

{

printf("非遞歸后序遍歷二叉樹：");

PostOrder_Nonrecursive(root);

printf("\n");

}

else

printf("??????????二叉樹為空执虹！\n");

break;

case7:

if(root)

{

printf("非遞歸層序遍歷二叉樹：");

//LeverTraverse(root);

LevelOrder(root);

printf("\n");

}

else

printf("??????????二叉樹為空拓挥！\n");

break;

case8:

if(root)

printf("這棵二叉樹的深度為：%d\n",depth(root));

else

printf("??????????二叉樹為空！\n");

break;

case9:

if(root)

printf("這棵二叉樹的結(jié)點(diǎn)個(gè)數(shù)為：%d\n",CountNode(root));

else

printf("??????????二叉樹為空袋励！\n");

break;

default:

flag=0;

printf("程序運(yùn)行結(jié)束侥啤，按任意鍵退出！\n");

}

}

system("pause");

return0;

}