可能編譯時會有些語法小錯誤（比如分號，->，等），很容易就自己糾正了哦，思路絕對是完全正確的，所以用的話就自己試著改改吧，直接復制粘貼，就正確，豈不是太沒寫代碼體驗了，自己改改才印象更加深刻的呢(▽)~~~~；
//中序遍歷的遞回與非遞回演算法
#include<iostream>
using namespace std;
#define MAXQSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef struct BiNode{ //二叉鏈表定義
char data;
struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;
/************************************* 佇列 ***************************************/
typedef BiTree QElemType;
typedef struct{
QElemType *base;//初始化時動態分配存盤空間
int front;//頭指標
int rear;//尾指標
int last;
}SqQueue;
//演算法3.13 回圈佇列的初始化
Status InitQueue(SqQueue &Q)
{ // 構造一個空佇列Q
Q.base = new QElemType[MAXQSIZE];
if(!Q.base)
{
return OVERFLOW; // 存盤分配失敗
}
Q.front = 0;
Q.rear = 0;
return OK;
}
//演算法3.14 求回圈佇列的長度
int QueueLength(SqQueue Q)
{// 回傳Q的元素個數，即佇列的長度
return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
int QueueEmpty(SqQueue &Q)
{
if (Q.front==Q.rear) return OK;
else return ERROR;
}
//演算法3.15 回圈佇列的入隊
Status EnQueue(SqQueue &Q,QElemType e)
{// 插入元素e為Q的新的隊尾元素
if((Q.rear+1)%MAXQSIZE == Q.front)
{
return ERROR;//尾指標在回圈意義上加1后等于頭指標，表明隊滿
}
Q.base[Q.rear] = e;
Q.rear = (Q.rear+1)%MAXQSIZE;
return OK;
}
//演算法3.16 回圈佇列的出隊
Status DeQueue(SqQueue &Q,QElemType &e)
{
if(Q.rear == Q.front)
{
return ERROR;
}
e = Q.base[Q.front];
Q.front = (Q.front+1)%MAXQSIZE;
return OK;
}
BiTree GetHead(SqQueue Q)
{//回傳Q的佇列元素，不修改隊頭指標
if(Q.front!=Q.rear) //佇列非空
return Q.base[Q.front]; //回傳隊頭元素的值，隊頭指標不變
}
/************************************************************************************/
//用演算法5.3 先序遍歷的順序建立二叉鏈表
void CreateBiTree(BiTree &T){
//按先序次序輸入二叉樹中結點的值（一個字符），創建二叉鏈表表示的二叉樹T
char ch;
cin >> ch;
if(ch=='#') T=NULL; //遞回結束，建空樹
else{
T=new BiTNode;
T->data=https://www.cnblogs.com/ygjzs/p/ch; //生成根結點
CreateBiTree(T->lchild); //遞回創建左子樹
CreateBiTree(T->rchild); //遞回創建右子樹
} //else
} //CreateBiTree
void InOrderTraverse(BiTree T){
//中序遍歷二叉樹T的遞回演算法
if(T){
InOrderTraverse(T->lchild);
cout << T->data;
InOrderTraverse(T->rchild);
}
}
//實作按層遍歷二叉樹的非遞回演算法（佇列）
void HierarchyTraverse(BiTree T)
{
BiTree bt = T;
SqQueue Q;
InitQueue(Q);
if(!bt){
return;
}
EnQueue(Q,bt);
while(Q.rear!=Q.front){
DeQueue(Q,bt);
cout<data;
if(bt->lchild!=NULL){
EnQueue(Q,bt->lchild);
}
if(bt->rchild!=NULL){
EnQueue(Q,bt->rchild);
}
}
}
//統計二叉樹中的葉子結點個數
int LeafNodeCount(BiTree T){
if(T==NULL) return 0;
else if(T->lchild==NULL&&T->rchild==NULL)
return 1;
else
return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);
}
//-------------------
int Depth(BiTree T)
{
int m,n;
if(T == NULL ) return 0; //如果是空樹，深度為0，遞回結束
else
{
m=Depth(T->lchild); //遞回計算左子樹的深度記為m
n=Depth(T->rchild); //遞回計算右子樹的深度記為n
if(m>n) return(m+1); //二叉樹的深度為m 與n的較大者加1
else return (n+1);
}
}
int LevelWidth(BiTree root,int level)//find the width of a level(amounts of nodes in the level).
{
if(!root)return 0;
else
{
if(level==1)return 1;
level=LevelWidth(root->lchild,level-1)+LevelWidth(root->rchild,level-1);
}
return level;
}
int Width(BiTree root)//find the maximum width of the btree.
{
int width,i;
int w[20];
for(i=0;i<20;i++)w[i]=0;
if(!root)width=0;
else
{
for(i=0;i<=Depth(root);i++)w[i]=LevelWidth(root,i+1);
}
i=0;
while(w[i])
{
if(w[i]>width)width=w[i];
i++;
}
return width;
}
// // -------------------
nt main(){
BiTree tree;
cout<<"請輸入建立二叉鏈表的序列：\n";
CreateBiTree(tree);
cout<<"中序遍歷的結果為：\n";
InOrderTraverse(tree);
cout<<endl;
//按層遍歷二叉樹
cout<<"按層遍歷的結果為：\n";
HierarchyTraverse(tree);
cout<<endl;
cout<<"二叉樹的寬度為"<<Width(tree)<<endl;
//統計葉子結點樹
cout<<"葉子結點數為"<<LeafNodeCount(tree);
cout<<"\n";
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/124290.html
標籤：其他
上一篇：交換左右子樹