一、給定二叉樹如下圖所示，編程完成下列要求：1、用二叉鏈存儲(chǔ)結(jié)構(gòu)將其生成一棵二叉樹；2、分別用三種遍歷算法將二叉樹的遍歷序列輸出；3、用括號(hào)表示法輸出二叉樹。GDBEA C FH上面是個(gè)圖。。。由于我分不多了，所以不是很多。但是我很想學(xué)這方面知識(shí)，到時(shí)我有分了再給你叫啊。高手幫忙啊。我把圖詳細(xì)說(shuō)下。A是樹根；B、C分別是A的左右孩子；D、E分別是B的左右孩子；G是D的右孩子；F是C的右孩子；H是F的左孩子。相信我已經(jīng)表達(dá)清楚了吧。謝謝各位大蝦了。
3 回答
飲歌長(zhǎng)嘯
TA貢獻(xiàn)1951條經(jīng)驗(yàn) 獲得超3個(gè)贊
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
//using namespace std;
typedef struct BiTNode {
char data;
struct BiTNode *Lchild, *Rchild; // 左、右孩子指針
} *BiTree;
void CreateBiTree(BiTree &T){
以B為根節(jié)點(diǎn)的左子樹 A根節(jié)點(diǎn) 以C為根節(jié)點(diǎn)的右子樹
以D為根節(jié)點(diǎn)的左子樹 B根節(jié)點(diǎn) 以E為根節(jié)點(diǎn)的右子樹
以G為根節(jié)點(diǎn)的左子樹 D根節(jié)點(diǎn) 以H為根節(jié)點(diǎn)的右子樹
以K為根節(jié)點(diǎn)的左子樹 C根節(jié)點(diǎn) 以F為根節(jié)點(diǎn)的右子樹
以I為根節(jié)點(diǎn)的左子樹 F根節(jié)點(diǎn) 右子樹為空
左子樹為空 I根節(jié)點(diǎn) 以J為根節(jié)點(diǎn)的右子樹
擴(kuò)展資料：
主函數(shù)的兩個(gè)形參形式中的形參，允許從執(zhí)行環(huán)境中傳遞任意的多字節(jié)字符串（它們通常被稱為命令行參數(shù)），各個(gè)指針 argv[1] .. argv[argc-1] 指向每個(gè)這些字符串的第一個(gè)字符。argv[0] 是指向一個(gè)表示用于執(zhí)行該程序自身的名字的空結(jié)尾多字節(jié)字符串（或者當(dāng)執(zhí)行環(huán)境不支持時(shí)，為空字符串 ""）的開頭字符的指針。
這些字符串是可以改動(dòng)的，雖然對(duì)它們的改動(dòng)并不會(huì)被傳回給執(zhí)行環(huán)境：比如可以用 std::strtok 來(lái)使用它們。由 argv 所指向的數(shù)組的大小至少為 argc+1，其最后一個(gè)元素 argv[argc] 保證為一個(gè)空指針。
拉風(fēng)的咖菲貓
TA貢獻(xiàn)1995條經(jīng)驗(yàn) 獲得超2個(gè)贊
#include
<iostream>
using
std::cin;
using
std::cout;
using
std::endl;
//using
namespace
std;
typedef
struct
BiTNode
{
char
data;
struct
BiTNode
*Lchild,
*Rchild;
//
左、右孩子指針
}
*BiTree;
void
CreateBiTree(BiTree
&T){
//
在先序遍歷二叉樹的過(guò)程中輸入二叉樹的"先序字符串"，
//
建立根指針為
T的二叉鏈表存儲(chǔ)結(jié)構(gòu)。在先序字符串中，
//
字符'#'表示空樹，其它字母字符為結(jié)點(diǎn)的數(shù)據(jù)元素
char
ch;
cin
>>
ch
;
if
(ch=='#'){
T=NULL;
//
建空樹
}else
{
T
=
new
BiTNode
;
//
"訪問(wèn)"操作為生成根結(jié)點(diǎn)
T->data
=
ch;
CreateBiTree(T->Lchild);
//
遞歸建(遍歷)左子樹
CreateBiTree(T->Rchild);
//
遞歸建(遍歷)右子樹
}//else
}//CreateBiTree
//先序遍歷以T為根指針的二叉樹
void
PreOrder(BiTree
&T){
if(T){
//
T=NULL時(shí)，二叉樹為空樹，不做任何操作
cout<<
T->data
<<
"
";
//
通過(guò)函數(shù)指針
*visit
訪問(wèn)根結(jié)點(diǎn)
PreOrder(T->Lchild);
//
先序遍歷左子樹
PreOrder(T->Rchild);
//
先序遍歷右子樹
}//
if
}
//中序遍歷以T為根指針的二叉樹
void
InOrder(BiTree
&T){
if(T){
//
T=NULL時(shí)，二叉樹為空樹，不做任何操作
InOrder(T->Lchild);
//
先序遍歷左子樹
cout<<
T->data
<<
"
";
//
通過(guò)函數(shù)指針
*visit
訪問(wèn)根結(jié)點(diǎn)
InOrder(T->Rchild);
//
先序遍歷右子樹
}//
if
}
//后序遍歷以T為根指針的二叉樹
void
PostOrder(BiTree
&T){
if(T){
//
T=NULL時(shí)，二叉樹為空樹，不做任何操作
PostOrder(T->Lchild);
//
先序遍歷左子樹
PostOrder(T->Rchild);
//
先序遍歷右子樹
cout<<
T->data
<<
"
";
//
通過(guò)函數(shù)指針
*visit
訪問(wèn)根結(jié)點(diǎn)
}//
if
}
//用括號(hào)表示法輸出二叉樹
void
DispBTree(BiTree
&bt)
{
if
(bt!=NULL)
{
cout<<bt->data;
if
(bt->Rchild!=NULL||bt->Lchild!=NULL)
{
cout<<"(";
DispBTree(bt->Lchild);
if
(bt->Rchild!=NULL)cout<<",";
DispBTree(bt->Rchild);
cout<<")";
}
}
}
int
main()
{
cout
<<
"請(qǐng)依次輸入字符:
ABD#G##E##C#FH###"
<<
endl;
BiTree
T;
CreateBiTree(T);
cout
<<
"先序遍歷:
"
<<
endl;
PreOrder(T);
cout
<<
endl
<<
"中序遍歷:
"
<<
endl;
InOrder(T);
cout
<<
endl
<<
"后序遍歷:
"
<<
endl;
PostOrder(T);
cout<<"\n用括號(hào)表示法輸出二叉樹:\n";
DispBTree(T);
cout<<endl;
return
(0);
}
一只名叫tom的貓
TA貢獻(xiàn)1906條經(jīng)驗(yàn) 獲得超3個(gè)贊
//
中序遍歷偽代碼：非遞歸版本，用棧實(shí)現(xiàn)，版本2
void
inorder2(tnode*
root)
{
stack
s;
if(
root
!=
null
)
{
s.push(root);
}
while
(
!s.empty()
)
{
tnode*
node
=
s.pop();
if
(
node->bpushed
)
{
//
如果標(biāo)識(shí)位為true,則表示其左右子樹都已經(jīng)入棧，那么現(xiàn)在就需要訪問(wèn)該節(jié)點(diǎn)了
visit(node);
}
else
{
//
左右子樹尚未入棧，則依次將
右節(jié)點(diǎn)，根節(jié)點(diǎn)，左節(jié)點(diǎn)
入棧
if
(
node->right
!=
null
)
{
node->right->bpushed
=
false;
//
左右子樹均設(shè)置為false
s.push(node->right);
}
node->bpushed
=
true;
//
根節(jié)點(diǎn)標(biāo)志位為true
s.push(node);
if
(
node->left
!=
null
)
{
node->left->bpushed
=
false;
s.push(node->left);
}
}
}
}
對(duì)比先序遍歷，這個(gè)算法需要額外的增加o(n)的標(biāo)志位空間。另外，?？臻g也擴(kuò)大，因?yàn)槊看螇簵５臅r(shí)候都?jí)喝敫?jié)點(diǎn)與左右節(jié)點(diǎn)，因此?？臻g為o(n)。時(shí)間復(fù)雜度方面，每個(gè)節(jié)點(diǎn)壓棧兩次，作為子節(jié)點(diǎn)壓棧一次，作為根節(jié)點(diǎn)壓棧一次，彈棧也是兩次。因此無(wú)論從哪個(gè)方面講，這個(gè)方法效率都不及inorder1。
后序
void
postorder(treenode
*root)
{
stack
*>
st;
treenode
*p
=
root;
treenode
*pre
=
null;//pre表示最近一次訪問(wèn)的結(jié)點(diǎn)
while(p
||
st.size()!=0)
{
//沿著左孩子方向走到最左下
。
while(p)
{
st.push(p);
p
=
p->left;
}
//get
the
top
element
of
the
stack
p
=
st.top();
//如果p沒(méi)有右孩子或者其右孩子剛剛被訪問(wèn)過(guò)
if(p->right
==
null
||
p->right
==
pre)
{
/
isit
this
element
and
then
pop
it
cout
<<
"visit:
"
<<
p->data
<<
endl;
st.pop();
pre
=
p;
p
=
null;
}
else
{
p
=
p->right;
}
}//end
of
while(p
||
st.size()!=0)
}
- 3 回答
- 0 關(guān)注
- 532 瀏覽
添加回答
舉報(bào)
0/150
提交
取消