求树的节点个数求法，求助啊！！！ - 数学建模社区-数学中国

首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：" c5 B1 R8 x9 h! L7 O& u$ X
tree_nodename：节点名字或序号2 L! p5 q7 ^. {
tree_nodevalue：节点对应的值
9 e g$ y, i9 {/ \& z! ]4 S
tree_nodefather：节点父亲，如果没有父亲，值为空
8 S' x, b" t a5 ~, N) O' o
tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空$ V* n* s/ g! B$ ^% w
tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空/ f) o. p) f, e5 K7 `
树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
0 P0 }% M# X- D; o/ U% p
. {9 S. ]1 b2 q* Q$ i" W D1 i
刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。* S6 y3 Y- w/ @# H! K5 Y
9 b. j1 u l- r/ k
%matlab源程序1 B2 s- U1 w6 B
%输入：树的深度、树的广度、搜索的值
6 M8 | k6 U1 e& `8 w+ ~( u
%返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空2 u# @* B9 L3 V" Y+ {
function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
: ?+ O' `+ N! R/ _% t
%根据树的深度、节点的儿子数量计算树总的节点个数( `. J! ~ q! z; h
node_num = 0;
0 E5 \* T7 y b2 V# }
for n= 0 : (tree_depth-1)
. t1 a! b$ b; g* p) g" o* d
node_num = node_num + tree_width ^ n;
0 e6 P) j2 e; k9 P7 E- e B. l* }
end ^; D: c+ H# b2 T' u
6 G* o( O% U3 _' Q: Z- d3 j
%为树的存储空间赋值
`: P! x2 X* M* K- `+ G7 G0 O
%node name，按照广度优先为节点排号+ [8 @( s4 ?1 g9 z/ K1 L' O/ R
tree_nodename = (1 : node_num);
. n( X$ y, j0 X4 o- z8 d7 b. Z
%node value
! ~/ y; Y0 C0 F3 {4 r
tree_nodevalue = rand(1 : node_num);3 d/ ]0 b2 u+ h2 L7 A2 M
%node father and son+ ]8 x$ s6 g b2 C6 v! W
tree_nodefather(1) = 0;
6 W% j. b$ ^( k2 a
tree_nodeson = zeros(1, node_num);* J4 Z& W/ _* N/ W. f
n = 2;* L! A: Y3 C' G: x; I0 d( a
k = 1;0 w3 O+ q2 M5 l" _# c- v% i
while n <= node_num
! k9 F0 B) R( Z3 O( m
for m = 1 : tree_width( ]: L* ^' w: |. H d* A
tree_nodefather(n) = k;0 j, V. d/ W% A0 h
if m==1! [" b/ Q. w: I1 R7 ]% R) J! h
tree_nodeson(k) = n;( k: S$ K$ y4 z+ f8 A' J- \
end
7 w. x2 E1 l/ E
n = n + 1;& A% B' u+ e) K, G# t' t% }
end
3 V7 Q$ {* b2 N
k = k + 1;
5 ]) s4 o4 E( |, ^! N
end' m2 r& p9 N$ \
%node neighbor+ E# E7 w1 P T4 n! E" M
tree_nodeneighbor(1) = 0;) c/ t! \( u w1 N% O; v8 c
n = 2;
. i, {- S4 G) T) Y6 h; A, v) s% f# P
while n <= node_num
3 v; m8 t4 J0 d) v/ b) h
for m = 1 : tree_width
6 W* n9 l3 d- J% R% J- y2 k& V4 \9 q* Q
if m ==tree_width
" X* }3 ?3 t- C1 V( V: p$ m
tree_nodeneighbor(n) = 0;, F6 S2 u6 ~. D! ]. D% v
else
) y( a1 f. A4 @% N4 G0 `+ Y
tree_nodeneighbor(n) = n + 1;
( Z9 ^" Y0 t' l% n
end w! V% c, |1 c! |4 S. {+ X& i. @
n = n + 1;3 e0 k1 m: t1 ]- a) Z2 k( D3 N$ Y R. M
end# K: Y1 l% l: c, J! g ]
end, f; s c' m$ P& Q# v7 V9 Y5 C# ^* f3 u, T
( `6 u$ u) X" C% k
%下面是有效程序段，用栈实现& A! @( H4 n7 w% u
stack = zeros(1, tree_depth);
6 `3 P1 q, m* t
nodeinstack = zeros(1, node_num);, ^: J9 o' e6 l
stack_ptr = 1;
3 l! N# d! [( `, b7 ~3 I
stack(1) = 1;( c4 ^5 e: u2 m3 w3 n
nodeinstack(1) = 1;
; d9 `! ~3 C3 S8 p
valueintree = seek_value;7 _; Q) m+ x8 `% r, ^: o8 ^
nodeintree = 0;
9 C) e, a5 C. W$ p( O4 }4 h0 t6 b
, S; D/ Q5 V2 q
while stack_ptr > 0
6 b) |5 r! Q% {3 F$ N( W
n = stack(stack_ptr);
! Z6 H1 t- f6 M, l# C& C
if abs(tree_nodevalue(n) – seek_value) < 1e-3
* G% @8 e0 Q! f9 x# ~% Y1 @! \, l
%如果搜索到值，返回
) ^; [% z% ^. {$ [$ D: u
valueintree = tree_nodevalue(n);+ [6 S/ ^7 A) f
nodeintree = tree_nodename(n);
; f1 u! n4 c% y& E3 `
break;" v2 g+ x$ ]" m* {$ m! _
end
8 L: i% X5 c1 a& _- T& z
' m0 A, E4 A# N% v, o' y! `
if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1$ B9 l: c# ~, O/ p/ V
%如果节点有儿子，并且第一次入栈，将儿子节点入栈
4 `5 Z# r r7 P; V3 C
stack_ptr = stack_ptr + 1;1 |$ m( T U/ ]4 F( F! F# P* s
m = tree_nodeson(n);
) G# H2 d& B/ }" t# G& k% b, p
stack(stack_ptr) = m;: h8 A# z5 T) u3 m5 ?! L
nodeinstack(m) = nodeinstack(m) + 1;' R, V- x# |; Y/ X2 z: T
elseif tree_nodeneighbor(n) ~= 0
0 i, ~5 C) H. Q a+ J
%否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈8 \1 }3 c% z% `0 ^" K5 J
m = tree_nodeneighbor(n);
3 J9 n1 e2 j* j2 z/ ~
stack(stack_ptr) = m;
5 @) ?7 d+ F! N" c# S9 v/ n
nodeinstack(m) = nodeinstack(m) + 1;$ |/ g- k6 j8 Q% M ?" N
else
6 K8 u7 [- p5 l
%再否则，出栈，然后将父亲节点的入栈次数加一! c/ A: k( H* q, W6 L
stack_ptr = stack_ptr - 1;$ {5 R+ V" Y$ c0 h
m = stack(stack_ptr);. L. t5 t$ U0 L6 d$ B
nodeinstack(m) = nodeinstack(m) + 1;
" e+ O6 ?1 C! a3 L; ]+ h1 w
end( O( x9 X; k! G% h8 D0 o
end

复制代码