数学建模社区-数学中国
标题:
求树的节点个数求法,求助啊!!!
[打印本页]
作者:
qiandongdong
时间:
2014-8-20 23:31
标题:
求树的节点个数求法,求助啊!!!
求树的节点个数的求法啊或matlab代码,我是新手,真心编了好久没结果。请前辈们帮帮忙啊~
作者:
madio
时间:
2014-8-21 00:16
就是一个遍历树的所有节点的算法,我帮你找到一个
首先需要定义树的存储。如果是C实现,应该是链表实现,每个节点用四个属性标志:
' h: Z* q5 u, W3 T! c# W
tree_nodename:节点名字或序号
- }/ e+ D8 C) Z5 r
tree_nodevalue:节点对应的值
+ l8 W8 D, S& J
tree_nodefather:节点父亲,如果没有父亲,值为空
1 ~# V0 H+ J2 E
tree_nodeson:节点的第一个儿子(最左边),如果没有儿子,值为空
% A9 F; Q2 l% Y$ R5 p4 s3 {( `
tree_nodeneighbor:节点的右边兄弟,如果右边没有兄弟,值为空
) R" Q* Q( o l7 c4 P
树的搜索,因为不限制搜索顺序,这里使用深度优先。不用递归,可以用栈实现。
0 ]4 L( K) B* E
; E a, G0 m( w* M6 t
刚学了点matlab,就使用matlab实现。Matlab中没有链表的概念,用数组实现。
( R9 t! I0 @ I0 @" e7 k
# G# Z/ }' v6 I" ~7 }8 W( c
%matlab源程序
4 C- J' k& X% Q) \& b; V+ f1 d% ^) [6 a
%输入:树的深度、树的广度、搜索的值
* D8 G4 U6 u/ s4 J) W
%返回:树中接近的值、节点名字,如果没有接近的值,节点名字为空
2 B9 {; ? P5 c; _9 B" v! o
function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
' z( }' D" m$ _) C* T8 T. Y
%根据树的深度、节点的儿子数量计算树总的节点个数
; s& J0 Z+ e) T2 F4 f u# H
node_num = 0;
8 t, K0 u: A# c- a* t: T
for n= 0 : (tree_depth-1)
$ x' e0 O/ } p1 c7 u8 y; G! K
node_num = node_num + tree_width ^ n;
5 Y7 s% O$ V3 t( N) Z2 t
end
u" @( t& H( v- }3 a
& M/ L/ y( p: G
%为树的存储空间赋值
, j& b9 c" e& h5 y5 S0 d4 t
%node name,按照广度优先为节点排号
% J+ M# G# f' U9 H$ v0 k% M$ ]
tree_nodename = (1 : node_num);
& j( Q: e( X. q1 v6 Y
%node value
! { A) d+ a4 K6 _' f
tree_nodevalue = rand(1 : node_num);
! w0 M/ m4 {; d4 c
%node father and son
$ O5 Z7 Y7 v. p s# P
tree_nodefather(1) = 0;
! D) t9 w# ^1 d& D
tree_nodeson = zeros(1, node_num);
% W! O' E3 z2 j& p
n = 2;
+ h$ z' ]: ? x* ?+ a* ~* G- b
k = 1;
% ?( z0 N) o2 I/ ^
while n <= node_num
; `) X% q4 o& |9 ^& H
for m = 1 : tree_width
1 f0 `) f0 G0 G4 L: N# N
tree_nodefather(n) = k;
5 T8 r# x" M' |# `$ Z; u
if m==1
; f7 L3 J/ G8 N7 e) q
tree_nodeson(k) = n;
! F$ h [- T. a8 ~6 L+ Z
end
+ }+ e. n" S R& @1 G
n = n + 1;
8 E$ V8 Z" O* I
end
Z, r- ?) @+ I# ?
k = k + 1;
" v- O d, Q, r, p, Q, N9 Y
end
- K! v' @ w& R8 }6 \3 r9 |; O" h
%node neighbor
% W8 {% Y) c2 {+ U! O
tree_nodeneighbor(1) = 0;
, q' @- L! t7 I* n' T
n = 2;
" h7 T$ o! C/ T, l" g- c- M1 b
while n <= node_num
# d7 k& f" Y8 k6 Y! b) ~
for m = 1 : tree_width
# s) g( w* ?9 Q0 w& D
if m ==tree_width
6 s* N1 C4 Z6 c8 U2 p; g
tree_nodeneighbor(n) = 0;
6 i: p4 z8 N5 r' z! L
else
, M: O+ o% @0 {0 B0 S2 p' {9 {2 P
tree_nodeneighbor(n) = n + 1;
9 n8 P, U4 `1 C3 @5 o5 u
end
5 V; C! M7 a6 a+ M5 x
n = n + 1;
$ E2 M) ^# `+ b
end
+ W2 P; R2 I4 r# o9 Z6 L
end
2 \+ ?, B. n5 f
5 a4 A# Z, j4 t Z
%下面是有效程序段,用栈实现
& j+ M* ^& d3 Z8 J
stack = zeros(1, tree_depth);
! b1 z/ S$ `; C* T+ h
nodeinstack = zeros(1, node_num);
7 n# e* d" A5 r$ K
stack_ptr = 1;
# _1 y, W* ~+ j' G0 e
stack(1) = 1;
. }* `, N' Z9 X
nodeinstack(1) = 1;
- K9 D8 b. T& J: s
valueintree = seek_value;
* E# G2 N, a- U
nodeintree = 0;
! A/ o3 b/ u( w( O8 y" |& Z. |
+ K: K; j* N4 g% }5 f
while stack_ptr > 0
( b( ] P% z, k* F
n = stack(stack_ptr);
% R/ N7 V( X* ~/ u! j5 ^: c/ @
if abs(tree_nodevalue(n) – seek_value) < 1e-3
9 r! O1 R% b# i9 x
%如果搜索到值,返回
, X$ a7 N G q0 \1 B
valueintree = tree_nodevalue(n);
8 _& T3 P0 A6 s1 B' g5 u
nodeintree = tree_nodename(n);
: y/ B+ }" N3 h& K( v7 i
break;
( T4 Q X5 Q' l/ n5 T
end
. {' [# U+ l& P8 _+ \4 w
& q7 s9 K# C. V/ b1 V$ a
if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
1 q! Z1 ^% C3 Y3 L6 |2 S# ]
%如果节点有儿子,并且第一次入栈,将儿子节点入栈
# `. ]( v7 J0 Y# D6 K" x, b4 `
stack_ptr = stack_ptr + 1;
8 k( u/ ?8 E9 A% d, \
m = tree_nodeson(n);
% r/ N& S, y0 H" P3 F/ A
stack(stack_ptr) = m;
7 p ]8 `) K" @3 j Q- G
nodeinstack(m) = nodeinstack(m) + 1;
" ?2 S) g! c5 U N* C
elseif tree_nodeneighbor(n) ~= 0
- X! ]+ ~8 @% W
%否则,如果节点右边有兄弟,节点出栈,然后将右边兄弟入栈
4 w- i" M' s; |: c
m = tree_nodeneighbor(n);
! S& ?# y4 N$ ^8 L7 q4 q4 {' M s
stack(stack_ptr) = m;
3 `$ `5 f H; ]7 Z+ b
nodeinstack(m) = nodeinstack(m) + 1;
! |3 u: O& A4 e4 D
else
+ J: _# d# ?8 s H
%再否则,出栈,然后将父亲节点的入栈次数加一
% P2 v2 p$ s9 n( z6 w
stack_ptr = stack_ptr - 1;
( c6 k5 `! s7 m" h
m = stack(stack_ptr);
' T+ M G# a% a! x- J
nodeinstack(m) = nodeinstack(m) + 1;
& G, a$ B6 {# v) |/ z3 l; |8 p2 k
end
2 [! o. z5 w: T! ?- F5 Z& v0 x
end
复制代码
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5