首頁猿問麻煩編出來的結(jié)果是一個完整的cpp...

麻煩編出來的結(jié)果是一個完整的cpp，可以直接運行，求高手指點～

算法與數(shù)據(jù)結(jié)構(gòu)

aluckdog 2023-04-01 13:10:43

要求先用struct treeNode{char data;treeNode *lchild,*rchild;}; //定義一個節(jié)點然后用類class binaryTree{private: treeNode *T;public:binaryTree(); //構(gòu)造函數(shù)int createTree();//創(chuàng)建樹int preTravel();//先序遍歷樹int inTravel();//中序遍歷樹};void main(){……}這個空指針用#輸入表示大概就這樣吧麻煩下大家?guī)臀彝瓿上虏灰媚０錿emplate請用類實現(xiàn)，并且只要創(chuàng)建二叉樹，先序遍歷，中序遍歷，后序遍歷中的2種遍歷即可，如果有現(xiàn)成的程序可以直接摘抄過來，但是只需要完成這幾種功能的函數(shù)皆可，其余的不要

查看完整描述

3 回答

夢里花落0921

TA貢獻1772條經(jīng)驗獲得超6個贊

說明：輸入時按前序遍歷方式依次輸入各節(jié)點值，默認的結(jié)束符為0。即當(dāng)一個節(jié)點為葉子節(jié)點時，把它的左子節(jié)點和右子節(jié)點都輸為0，當(dāng)然你可以自己修改為加別的值。例如某棵樹的形狀如下：
A
/ \
B C
/ \ \
D E F
則按如下輸入：ABD00E00C0F00。

程序運行后結(jié)果如下：

前序遍歷結(jié)果：
ABDECF
中序遍歷結(jié)果：
DBEACF

程序源文件：

#include <stdio.h>
#include <stdlib.h>

struct treeNode
{
char data;
struct treeNode *lchild;
struct treeNode *rchild;
}; //定義一個節(jié)點

class binaryTree
{
private:
struct treeNode *T;
public:
binaryTree() {T = NULL;}; //構(gòu)造函數(shù)
int createTree(); //創(chuàng)建樹
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("請輸入各節(jié)點數(shù)據(jù)：\n");
T = createBT(T, 0);
return 0;
}

int binaryTree::preTravel()
{
printf("前序遍歷結(jié)果：\n");
preTravelBT(T);
printf("\n");
return 0;
}

int binaryTree::inTravel()
{
printf("中序遍歷結(jié)果：\n");
inTravelBT(T);
printf("\n");
return 0;
}

void main()
{
binaryTree MyTree;
MyTree.createTree();
MyTree.preTravel();
MyTree.inTravel();
}

反對回復(fù) 2023-04-05

神不在的星期二

TA貢獻1963條經(jīng)驗獲得超6個贊

void PreOrder_Nonrecursive(Bitree T)//先序遍歷二叉樹的非遞歸算法
{//思路為利用自己的堆棧模擬函數(shù)遞歸調(diào)用時棧區(qū)的變化。
InitStack(S);//初始化堆棧。參照嚴(yán)蔚敏編《數(shù)據(jù)結(jié)構(gòu)C語言版》實現(xiàn)堆棧的相關(guān)功能函數(shù)，這里會用到。
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); //向右一步，從這個結(jié)點開始繼續(xù)進行先序遍歷
}
}//while
}//PreOrder_Nonrecursive

int NodeCount_BiTree(Bitree T)//求二叉樹中結(jié)點的數(shù)目
{
if(!T) return 0; //遞歸結(jié)束條件：空樹結(jié)點數(shù)為0
else return (NodeCount(T->lchild)+NodeCount(T->rchild)+1);//二叉樹中結(jié)點數(shù)＝左子樹的結(jié)點數(shù)＋右子樹的結(jié)點數(shù)＋根結(jié)點自己
}//NodeCount_BiTree

int LeafCount_BiTree(Bitree T)//求二叉樹中葉子結(jié)點的數(shù)目
{
if(!T) return 0; //空樹沒有葉子
else if(!T->lchild&&!T->rchild) return 1; //葉子結(jié)點
else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子樹的葉子數(shù)加上右子樹的葉子數(shù)
}//LeafCount_BiTree

若已知二叉樹的結(jié)點數(shù)為n，葉子的結(jié)點數(shù)為n0，那么n2=n0-1，n1=n-n2-n0=n-2n0+1?；蛘哂靡韵滤惴?nbsp;
int n1=0;//定義全局變量n1
void Count_n1(Bitree T)
{//先序遍歷二叉樹過程中統(tǒng)計度為1的結(jié)點數(shù)
if(T)
{
if((T->lchild && !T->rchild) || (!T->lchild && T->rchild))//判斷是否是度為1的結(jié)點，實際上是異或
n1++;
Count_n1(T->lchild);
Count_n1(T->rchild);
}
}

int Get_Depth(Bitree T)//求二叉樹深度的遞歸算法
{
if(!T) return 0;//遞歸結(jié)束條件：空樹深度為0
else
{
m=Get_Depth(T->lchild);
n=Get_Depth(T->rchild);
return (m>n?m:n)+1;//二叉樹深度為其左右子樹較大深度＋1
}
}//Get_Depth

反對回復(fù) 2023-04-05

撒科打諢

TA貢獻1934條經(jīng)驗獲得超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;
}; //定義一個節(jié)點
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;}//構(gòu)造函數(shù)
void createTree();//創(chuàng)建樹
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;
}
//用二叉堆的方式建樹