求树的节点个数求法，求助啊！！！

qiandongdong

求树的节点个数的求法啊或matlab代码，我是新手，真心编了好久没结果。请前辈们帮帮忙啊~

madio

就是一个遍历树的所有节点的算法，我帮你找到一个

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   0 j6 Q  f' l8 L$ j! }/ s
2.        tree_nodename：节点名字或序号/ [: r8 Y5 Q8 L5 n
   
3.        tree_nodevalue：节点对应的值\" M8 R7 L0 j! V% q
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   % {0 C2 Q$ V; T% v
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空& H8 q9 f6 s$ Y\" @3 V: N
   
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空' D9 H+ Y6 n5 f4 y/ i: ~) c( X
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   0 z- \9 q, W2 a& i6 C2 Z
8. 
   - r9 U3 O6 X& O
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。- B  V, B; z% Y6 r( w2 x
   
10. 1 R9 w0 c\" D% K\" X* l
    
11.        %matlab源程序' b. U* Z5 |/ Y1 z4 }7 k6 F
    
12.        %输入：树的深度、树的广度、搜索的值1 q2 T1 y4 j\" j0 o: Z6 S
    
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空% f  E+ x  L0 K  @
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)& s& r5 I' Q$ v7 C
    
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    6 Q% s/ n/ A3 o( Z* W. Z
16.        node_num = 0;\" @# {+ z! |( L/ g
    
17.        for n= 0 : (tree_depth-1)& |; Z4 @$ P8 B$ W3 k. V: X
    
18.               node_num = node_num + tree_width ^ n;# y6 z8 D7 F9 h# h% u& n
    
19.        end
    ' b9 Q$ _\" i) t1 \8 r
20. 4 w) P4 j1 G: K3 [: Q8 X+ a
    
21.        %为树的存储空间赋值9 g! n% M: B9 a, L4 ~* U/ \
    
22.        %node name，按照广度优先为节点排号
    : a0 q! |. p0 G) p5 L8 G4 i+ M
23.        tree_nodename = (1 : node_num);
    ! U* A\" q) C8 M
24.        %node value
    ! R+ g# K0 G8 x3 t! [: S; o1 w- {\" I
25.        tree_nodevalue = rand(1 : node_num);% {5 e& |\" l+ s
    
26.        %node father and son
    ( l. [; ?8 J# P& B  o7 c# i$ _
27.        tree_nodefather(1) = 0;
    - ?\" }1 `% G0 e8 B/ [
28.        tree_nodeson = zeros(1, node_num);
    \" T; ^/ ]0 p  H$ k3 M$ A
29.        n = 2;
    2 F7 \/ [: [: U
30.        k = 1;4 s9 M* j, q% p# a% Z
    
31.        while n <= node_num7 U: U0 \: B& j
    
32.               for m = 1 : tree_width5 d\" J+ m3 q) H$ W
    
33.                      tree_nodefather(n) = k;) }: h/ {: E\" Q, K8 N
    
34.                      if m==1
    & N: b5 \* D\" ?0 g9 _9 O
35.                             tree_nodeson(k) = n;- n% L) Q& c$ \5 U2 m8 U- t
    
36.                      end
    & ]8 ~1 S! B, l# ~8 u& i
37.                      n = n + 1;% R, }& L* G% i
    
38.               end
    ; f) D8 Y0 \% I\" X
39.               k = k + 1;! @5 \( v4 Y, n0 ^4 a6 d4 u; j
    
40.        end
    + k0 [0 M8 y. i9 A. N* u
41.        %node neighbor' p7 \5 K5 O, s* x\" Q. A# \
    
42.        tree_nodeneighbor(1) = 0;- ^  ]! K5 T  U* z, A: Z; Q2 t. u: M0 |
    
43.        n = 2;  C* Q' D- X2 c; A  l- ^
    
44.        while n <= node_num
    ! q. z9 c' `6 @
45.               for m = 1 : tree_width$ }: ]' o. ?  b7 C! ^( B  \3 M
    
46.                      if m ==tree_width
    8 g# G9 E4 |\" q; S. n% g6 N
47.                             tree_nodeneighbor(n) = 0;
      e4 a2 c* ^. t' s! j
48.                      else
    / Y; s( T! r; O
49.                             tree_nodeneighbor(n) = n + 1;, u5 y2 J6 z+ k9 {; p
    
50.                      end
    , b4 w6 H9 Z7 ^# u, F2 z
51.                      n = n + 1;1 c\" o# ?3 V0 |9 }
    
52.               end& @+ S$ T$ e; D
    
53.        end
    : ?\" P' v2 y! M! O2 P) Z
54. 
    1 a' K  G8 z. a  S1 V5 f0 a
55.        %下面是有效程序段，用栈实现
    / y! Q+ K* d3 K6 P
56.        stack = zeros(1, tree_depth);
    4 U; b' D5 t* H* Y# L
57.        nodeinstack = zeros(1, node_num);
    8 d5 j, G  F  |) [) V0 g- I* B) j
58.        stack_ptr = 1;; R- y+ H7 H, {5 W
    
59.        stack(1) = 1;
    - ?1 X& k6 `8 C+ ?3 j9 ?; I
60.        nodeinstack(1) = 1;. P9 a) v8 e! Q9 v- l  Y& a
    
61.        valueintree = seek_value;
    * p# f5 G  M. C- ~
62.        nodeintree = 0;1 G+ Y' [+ [4 T' I
    
63. 9 F/ ]# ?7 ], M  f  I
    
64.        while stack_ptr > 0
    3 j, p) i4 L3 d: `# K/ x* D* \
65.               n = stack(stack_ptr);
    ) W1 b  l0 V- [( t; N. B
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    / K& t% |# Q* Q( R  I
67.               %如果搜索到值，返回- G4 f9 l\" S: q! C( _, ~
    
68.                      valueintree = tree_nodevalue(n);
    1 n- m# m3 a  }# e$ H7 y
69.                      nodeintree = tree_nodename(n);
    0 M' N4 H4 t0 l
70.                      break;; ]2 ?- ^, X  @+ \- L
    
71.               end4 a' |$ n' o+ M. q6 n8 W
    
72. 
    8 ~: q# Q. u% D$ \* j2 L& O
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1# {) K3 e8 M5 q\" n
    
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    8 y# a# z3 m- }5 x; A
75.                      stack_ptr = stack_ptr + 1;9 F$ r6 j5 |; H9 R
    
76.                      m = tree_nodeson(n);
    ( W* [) k7 j5 [& L) U
77.                      stack(stack_ptr) = m;: I+ s$ H: h3 _0 F; B; Q
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    1 Y. y3 O: ~2 u
79.               elseif tree_nodeneighbor(n) ~= 0
    . W) d# K+ g; C+ R1 [
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    5 f. X5 I- J9 Z. i* S8 ^. K
81.                      m = tree_nodeneighbor(n);
    9 C. S: ]. t1 Z
82.                      stack(stack_ptr) = m;2 U; J) F9 P. m6 U8 X
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    ( V  R* {% e/ z, c) j
84.               else9 f9 o) g2 ~5 Y( c
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一, S( B6 w0 ?- K0 R' ?3 ?6 P
    
86.                      stack_ptr = stack_ptr - 1;
    # X, t; h0 P3 r0 {% Z
87.                      m = stack(stack_ptr);
    & V& u/ t7 d4 G  G
88.                      nodeinstack(m) = nodeinstack(m) + 1;
    9 H5 ~# u- ]7 X
89.               end6 C  S6 y, b# f4 _5 F1 o1 k
    
90.        end

复制代码