Skip to content

Commit 718ca77

Browse files
sourcodersourcoder
committed
add experiment07 code
1 parent 6279dfe commit 718ca77

File tree

6 files changed

+150
-0
lines changed

6 files changed

+150
-0
lines changed

‎experiment/experiment07/experiment07.cbp

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
<?xml version="1.0" encoding="UTF-8" standalone="yes" ?>
2+
<CodeBlocks_project_file>
3+
<FileVersion major="1" minor="6" />
4+
<Project>
5+
<Option title="experiment07" />
6+
<Option pch_mode="2" />
7+
<Option compiler="gcc" />
8+
<Build>
9+
<Target title="Debug">
10+
<Option output="bin/Debug/experiment07" prefix_auto="1" extension_auto="1" />
11+
<Option object_output="obj/Debug/" />
12+
<Option type="1" />
13+
<Option compiler="gcc" />
14+
<Compiler>
15+
<Add option="-g" />
16+
</Compiler>
17+
</Target>
18+
<Target title="Release">
19+
<Option output="bin/Release/experiment07" prefix_auto="1" extension_auto="1" />
20+
<Option object_output="obj/Release/" />
21+
<Option type="1" />
22+
<Option compiler="gcc" />
23+
<Compiler>
24+
<Add option="-O2" />
25+
</Compiler>
26+
<Linker>
27+
<Add option="-s" />
28+
</Linker>
29+
</Target>
30+
</Build>
31+
<Compiler>
32+
<Add option="-Wall" />
33+
<Add option="-fexceptions" />
34+
</Compiler>
35+
<Unit filename="main.cpp" />
36+
<Extensions>
37+
<code_completion />
38+
<envvars />
39+
<debugger />
40+
</Extensions>
41+
</Project>
42+
</CodeBlocks_project_file>

‎experiment/experiment07/experiment07.depend

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
# depslib dependency file v1.0
2+
1493901893 source:c:\users\dell\desktop\curriculum\semester_4\datastructure\algorithm\experiment\experiment07\main.cpp
3+
<iostream>
4+
<fstream>
5+

‎experiment/experiment07/experiment07.layout

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
<?xml version="1.0" encoding="UTF-8" standalone="yes" ?>
2+
<CodeBlocks_layout_file>
3+
<ActiveTarget name="Debug" />
4+
<File name="main.cpp" open="1" top="1" tabpos="1" split="0" active="1" splitpos="0" zoom_1="2" zoom_2="0">
5+
<Cursor>
6+
<Cursor1 position="0" topLine="56" />
7+
</Cursor>
8+
</File>
9+
</CodeBlocks_layout_file>

‎experiment/experiment07/input.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
ABC##DE###F#G##

‎experiment/experiment07/main.cpp

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
/*
2+
设二叉树结点数据域为字符类型，从键盘输入先序递归遍历字符序列（用#字符表示NULL指针域）
3+
建立二叉链表存储结构，然后实现中序线索化。基于中序穿线二叉树存储结构定义first,next,last,
4+
previous四个函数并实现中序线索二叉树中序遍历（正序与逆序）非递归算法，输出遍历结果。
5+
*/
6+
7+
#include <iostream>
8+
#include <fstream>
9+
using namespace std;
10+
11+
enum PT {LINK, THREAD};//定义指针域类型
12+
typedef struct node
13+
{
14+
char data;
15+
struct node *lchild, *rchild;
16+
enum PT ltag, rtag;
17+
}*SBiT, SBiT_Node;
18+
19+
ifstream is("input.txt");
20+
//创建一颗二叉树
21+
SBiT create()
22+
{
23+
char c;
24+
is >> c;
25+
if('#' == c)
26+
return NULL;
27+
SBiT bt = new SBiT_Node();
28+
bt->data = c;
29+
bt->lchild = create();
30+
bt->rchild = create();
31+
return bt;
32+
}
33+
//中序线索化，bt为主扫描指针，pre始终指向前驱节点
34+
void midThreading(SBiT bt, SBiT &pre)
35+
{
36+
if(bt)
37+
{
38+
midThreading(bt->lchild, pre);
39+
if(pre)
40+
{
41+
if(pre->rchild)
42+
pre->rtag = LINK;
43+
else
44+
{
45+
pre->rtag = THREAD;
46+
pre->rchild = bt;
47+
}
48+
}
49+
50+
if(bt->lchild)
51+
bt->ltag = LINK;
52+
else
53+
{
54+
bt->ltag = THREAD;
55+
bt->lchild = pre;
56+
}
57+
pre = bt;
58+
midThreading(bt->rchild, pre);
59+
}
60+
}
61+
//求中序遍历第一访问节点
62+
SBiT first(SBiT p)
63+
{
64+
while(p&&p->ltag == LINK)
65+
p = p->lchild;
66+
return p;
67+
}
68+
//求中序遍历某节点的后继
69+
SBiT next(SBiT p)
70+
{
71+
if(p->rtag == THREAD)
72+
return p->rchild;
73+
return first(p->rchild);
74+
75+
}
76+
//中序遍历,非递归算法
77+
void midtravel(SBiT root)
78+
{
79+
SBiT p = first(root);
80+
while(p)
81+
{
82+
cout << p->data ;
83+
p = next(p);
84+
}
85+
}
86+
int main()
87+
{
88+
SBiT root = create(),pre = NULL;;
89+
midThreading(root, pre);
90+
pre->rtag = THREAD;
91+
midtravel(root);
92+
return 0;
93+
}

‎experiment/experiment07/obj/Debug/main.o

15.3 KB
Binary file not shown.

0 commit comments

Comments
 (0)