Tree ++++
.pdf
Draw Tree
#include <windows.h> // wincon.h typedef struct _COORD
{ SHORT X; SHORT Y;}
COORD, *PCOORD;
HANDLE hout;
hout = GetStdHandle (STD_OUTPUT_HANDLE); COORD z;
z.X = 10; z.Y = 20; SetConsoleCursorPosition ( hout, z);
41
Expression Tree
Infix: |
|
(a + b) / (c*d –f)^p |
|
Post: |
|
ab + cd * f – p ^ / |
|
|
|
/ |
|
+ |
|
|
^ |
a |
b |
- |
p |
|
|
* |
f |
c d
Идея построения аналогична вычислению выражения через стек
42
Expression Tree
+
a b
Симметричный |
a+b |
инфиксное |
Прямой |
+ab |
префиксное |
Обратный |
ab+ |
постфиксное |
43
Derivation
e=f*g+u/v e’=f’*g+f*g’+(u’*v-u*v’)/v^2
+
|
* |
|
/ |
f |
g |
u |
v |
44
Derivation
e=f*g+u/v e’=f’*g+f*g’+(u’*v-u*v’)/v^2
|
|
|
+ |
|
|
|
|
|
|
+ |
|
|
|
/ |
|
|
* |
|
* |
|
- |
|
^ |
f’ |
g |
f |
g’ |
* |
* |
v |
2 |
|
|
|
|||||
|
|
|
u’ |
v |
u |
v’ |
|
|
|
|
|
|
|
|
45 |
Expression Tree
struct NODES { int c; char *s;
NODES *left,*right,*parent,*brother;
};
NODES* CreateNodes(int c)
{ NODES *p=(NODES *)malloc(sizeof(NODES)); p->left=0; p->right=0; p->parent=0; p->s=0; p->c=c;
return p;
} // CreateNodes
46
Create Expression Tree
NODES* CreateTreeNodes(char post [ ] )
{ |
int i, k=0; char c; NODES *p,*x,*y,*e[100]; |
|
|
for(i=0; post[i]; i++) |
|
{ |
c=post[i]; p=CreateNodes(c); |
|
|
if(!isalpha(c)) |
// знак операции |
{ y=e[k-1]; k--; |
x=e[k-1]; k--; |
|
|
p->left=x; p->right=y; |
|
|
x->parent=p; y->parent=p; |
|
} |
|
|
|
e[k]=p; k++; // узел - операнд или поддерево |
|
} |
// for i |
|
|
return p; |
47 |
|
|
|
} |
// CreateTreeNodes |
|
Tree to Infix
Как по дереву выражения получить формулу в инфиксной записи?
Самый простой способ состоит в том, чтобы при обработке дерева выражения каждый операнд заключался в круглые скобки.
В этом случае будет получена формула в инфиксной записи, но она будет содержать слишком много скобок.
Рассмотрим рекурсивный алгоритм, который по заданной формуле, представленной деревом выражений, строит формулу в инфиксной записи, расставляя в ней лишь необходимые скобки.
48
Tree to Infix -2
•В основе алгоритма лежат следующие действия:
•Если в узле дерева знак операции, то проверяется, какая информация хранится в корнях левого и правого поддеревьев.
•Если приоритет операции узла ниже приоритета операции в корне поддерева, то операнд в скобки не заключается.
•Если приоритет операции выше приоритета операций в корнях поддеревьев, то операнд, соответствующий поддереву, заключается в скобки.
49
Tree to Infix -3
•Если операции имеют одинаковый приоритет, то левый операнд в скобки заключать не надо, а для правого операнда требуется дополнительно проанализировать сочетание знаков в корне и в правом поддереве.
• В частности: |
- |
• Если в корне хранится знак минус, а в корне
правого поддерева знаки плюс или минус, то a + правый операнд заключается в скобки.
a-b+c a-(b+c) a-b-c a-(b-c) |
b |
c |
•Если в корне хранится знак деления, а в корне правого поддерева знаки умножения или деления, то правый операнд заключается в скобки.
50
a/b*c a/(b*c) a/b/c a/(b/c)