要求先用struct treeNode{char data;treeNode *lchild,*rchild;}; //定義一個節點 然后用類class binaryTree{private: treeNode *T;public:binaryTree(); //構造函數int createTree();//創建樹int preTravel();//先序遍歷樹int inTravel();//中序遍歷樹};void main(){……}這個空指針用#輸入表示大概就這樣吧麻煩下大家幫我完成下不要用模板template請用類實現，并且只要創建二叉樹，先序遍歷，中序遍歷，后序遍歷中的2種遍歷即可，如果有現成的程序可以直接摘抄過來，但是只需要完成這幾種功能的函數皆可，其余的不要
3 回答
夢里花落0921
TA貢獻1772條經驗 獲得超6個贊
說明：輸入時按前序遍歷方式依次輸入各節點值，默認的結束符為0。即當一個節點為葉子節點時，把它的左子節點和右子節點都輸為0，當然你可以自己修改為加別的值。例如某棵樹的形狀如下：
A
/ \
B C
/ \ \
D E F
則按如下輸入：ABD00E00C0F00。
程序運行后結果如下：
前序遍歷結果：
ABDECF
中序遍歷結果：
DBEACF
程序源文件：
#include <stdio.h>
#include <stdlib.h>
struct treeNode
{
char data;
struct treeNode *lchild;
struct treeNode *rchild;
}; //定義一個節點
class binaryTree
{
private:
struct treeNode *T;
public:
binaryTree() {T = NULL;}; //構造函數
int createTree(); //創建樹
int preTravel(); //先序遍歷樹
int inTravel(); //中序遍歷樹
};
struct treeNode * createBT(struct treeNode *bt, int k)
{
char b;
struct treeNode *p, *t;
b = getchar();
if (b != '0')
{
p = (struct treeNode *)malloc(sizeof(struct treeNode));
p->data = b;
p->lchild = NULL;
p->rchild = NULL;
if (k == 0) t = p;
if (k == 1) bt->lchild = p;
if (k == 2) bt->rchild = p;
createBT(p, 1);
createBT(p, 2);
}
return t;
}
void preTravelBT(struct treeNode *bt)
{
if (bt != NULL)
{
putchar(bt->data);
preTravelBT(bt->lchild);
preTravelBT(bt->rchild);
}
}
void inTravelBT(struct treeNode *bt)
{
if (bt != NULL)
{
inTravelBT(bt->lchild);
putchar(bt->data);
inTravelBT(bt->rchild);
}
}
int binaryTree::createTree()
{
printf("請輸入各節點數據：\n");
T = createBT(T, 0);
return 0;
}
int binaryTree::preTravel()
{
printf("前序遍歷結果：\n");
preTravelBT(T);
printf("\n");
return 0;
}
int binaryTree::inTravel()
{
printf("中序遍歷結果：\n");
inTravelBT(T);
printf("\n");
return 0;
}
void main()
{
binaryTree MyTree;
MyTree.createTree();
MyTree.preTravel();
MyTree.inTravel();
}
神不在的星期二
TA貢獻1963條經驗 獲得超6個贊
void PreOrder_Nonrecursive(Bitree T)//先序遍歷二叉樹的非遞歸算法
{//思路為利用自己的堆棧模擬函數遞歸調用時棧區的變化。
InitStack(S);//初始化堆棧。參照嚴蔚敏編《數據結構C語言版》實現堆棧的相關功能函數，這里會用到。
Push(S,T); //根指針進棧
while(!StackEmpty(S))
{
while(Gettop(S,p)&&p)//若棧頂元素不是空指針
{
visit(p->data);//訪問
push(S,p->lchild);//進入左子樹
} //向左走到盡頭
pop(S,p);將棧頂元素（實際上是空指針）丟棄
if(!StackEmpty(S))
{
pop(S,p);
push(S,p->rchild); //向右一步，從這個結點開始繼續進行先序遍歷
}
}//while
}//PreOrder_Nonrecursive
int NodeCount_BiTree(Bitree T)//求二叉樹中結點的數目
{
if(!T) return 0; //遞歸結束條件：空樹結點數為0
else return (NodeCount(T->lchild)+NodeCount(T->rchild)+1);//二叉樹中結點數＝左子樹的結點數＋右子樹的結點數＋根結點自己
}//NodeCount_BiTree
int LeafCount_BiTree(Bitree T)//求二叉樹中葉子結點的數目
{
if(!T) return 0; //空樹沒有葉子
else if(!T->lchild&&!T->rchild) return 1; //葉子結點
else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子樹的葉子數加上右子樹的葉子數
}//LeafCount_BiTree
若已知二叉樹的結點數為n，葉子的結點數為n0，那么n2=n0-1，n1=n-n2-n0=n-2n0+1。或者用以下算法
int n1=0;//定義全局變量n1
void Count_n1(Bitree T)
{//先序遍歷二叉樹過程中統計度為1的結點數
if(T)
{
if((T->lchild && !T->rchild) || (!T->lchild && T->rchild))//判斷是否是度為1的結點，實際上是異或
n1++;
Count_n1(T->lchild);
Count_n1(T->rchild);
}
}
int Get_Depth(Bitree T)//求二叉樹深度的遞歸算法
{
if(!T) return 0;//遞歸結束條件：空樹深度為0
else
{
m=Get_Depth(T->lchild);
n=Get_Depth(T->rchild);
return (m>n?m:n)+1;//二叉樹深度為其左右子樹較大深度＋1
}
}//Get_Depth
撒科打諢
TA貢獻1934條經驗 獲得超2個贊
/*
* main.cpp
*
* Created on: 2008-12-1
* Author: Admin
*/
#include<iostream>
using std::cout;
using std::cin;
struct treeNode
{
char data;
treeNode *lchild,*rchild;
}; //定義一個節點
class binaryTree
{
private:
treeNode *TreeRoot;
void subCreate(treeNode *,int,const char *);
void Free(treeNode *);
void subpreTravel(treeNode *);
void subinTravel(treeNode *);
public:
binaryTree(){TreeRoot=new treeNode;}//構造函數
void createTree();//創建樹
void preTravel(){subpreTravel(TreeRoot);cout<<"\n";}//先序遍歷樹
void inTravel(){subinTravel(TreeRoot);cout<<"\n";}//中序遍歷樹
~binaryTree(){Free(TreeRoot);}
};
void binaryTree::subCreate(treeNode * T,int root,const char * strNode)
{
static int longth=strlen(strNode);
int R=2*(root+1);
int L=2*(root+1)-1;
if(root ==0)
T->data=strNode[0];
if(L<longth)
{
T->lchild=new treeNode;
T->lchild->data=strNode[L];
subCreate(T->lchild,L,strNode);
}
else
T->lchild=NULL;
if(R<longth)
{
T->rchild=new treeNode;
T->rchild->data=strNode[R];
subCreate(T->rchild,R,strNode);
}
else
T->rchild=NULL;
}
void binaryTree::createTree()
{
subCreate(this->TreeRoot,0,"abcdefghijk");
}
void binaryTree::subpreTravel(treeNode * T)
{
if(T==NULL)
return;
cout<<T->data;
subpreTravel(T->lchild);
subpreTravel(T->rchild);
}
void binaryTree::subinTravel(treeNode * T)
{
if(T==NULL)
return;
subinTravel(T->lchild);
cout<<T->data;
subinTravel(T->rchild);
}
void binaryTree::Free(treeNode * T)
{
if(T==NULL)return;
if(T->lchild==NULL&&T->rchild==NULL)
delete T;
else
{
Free(T->lchild);
Free(T->rchild);
}
}
int main()
{
binaryTree BT;
BT.createTree();
BT.preTravel();
BT.inTravel();
return 0;
}
//用二叉堆的方式建樹
添加回答
舉報
0/150
提交
取消