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