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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   \" a$ _# o# j8 z
2.        tree_nodename：节点名字或序号+ a9 S/ Z$ N/ m/ `/ B
   
3.        tree_nodevalue：节点对应的值
   ' e4 F+ y# O5 o% R$ Z
4.        tree_nodefather：节点父亲，如果没有父亲，值为空$ `) Q. I; j2 k1 U; D( c7 J; ]
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   9 E  Z8 @1 r) L& F+ R
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
   * ?! `( p. T) E* \7 c
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   9 H0 L, l$ ]9 _; R. y
8. 
   3 Y; D. U& W4 w( z! I7 I
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   ( H\" e% e( D! E' @\" w; k- {/ U
10. ! \2 e, s0 S# J1 a! a1 t8 M
    
11.        %matlab源程序& p1 [7 X, P; a; [
    
12.        %输入：树的深度、树的广度、搜索的值0 ^' i) k, a* G
    
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空8 S& n4 r+ q) Q& I7 [2 M& O
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    0 J0 j1 p+ C3 e\" z% z
15.        %根据树的深度、节点的儿子数量计算树总的节点个数- j& i( W7 y* G8 a) w) t+ v
    
16.        node_num = 0;
    8 q! E- v5 B+ P1 o
17.        for n= 0 : (tree_depth-1)
    , ?' K2 W, o% _) F. j4 ^\" f5 e
18.               node_num = node_num + tree_width ^ n;
    + ^+ o% b2 e9 e+ y
19.        end
    1 V* l7 E: k1 e\" Z6 b: `7 M, v
20. 7 X( _8 c1 d* [5 ^8 s
    
21.        %为树的存储空间赋值
    \" j6 X$ \% l2 k7 P  P
22.        %node name，按照广度优先为节点排号
    7 q9 u( T0 v4 x  y+ ]
23.        tree_nodename = (1 : node_num);
    0 ]% ?/ e1 k\" b' a* E
24.        %node value
    8 i' _( v: `: ]# A$ w/ c: A
25.        tree_nodevalue = rand(1 : node_num);) s3 z( U6 i4 k, u
    
26.        %node father and son) z. b+ }8 F* C\" K
    
27.        tree_nodefather(1) = 0;7 m) @7 p3 X5 T\" q/ Q8 y, l
    
28.        tree_nodeson = zeros(1, node_num);
    6 C& ^8 V/ s6 [% {
29.        n = 2;- ]$ \8 p. F  y6 z- w( p
    
30.        k = 1;8 {$ a3 Q; Q, x0 }) c( X
    
31.        while n <= node_num
    1 h9 i9 O. C/ L' P; h8 b
32.               for m = 1 : tree_width0 X6 [3 s. p+ P# ^1 {
    
33.                      tree_nodefather(n) = k;/ [  J4 H3 V; x3 ^7 ~
    
34.                      if m==1
    $ u5 S  @0 L, r
35.                             tree_nodeson(k) = n;2 R6 A* N\" S! \5 V
    
36.                      end7 O+ R& o. K, {# L, c
    
37.                      n = n + 1;  Q! N# Z& J6 l: X! e
    
38.               end
    7 g8 ~% ]. D5 j9 X7 ^3 F
39.               k = k + 1;* T2 u\" M- s4 C+ c& r
    
40.        end
    / T3 L- ^3 y) @- ^* O) U6 k6 R$ S
41.        %node neighbor
    2 u1 T0 e0 a1 }8 i
42.        tree_nodeneighbor(1) = 0;/ a& C& C, u4 E2 C' Z
    
43.        n = 2;
    ! B% ?! p% c( T# {* Q6 y
44.        while n <= node_num9 ^2 n. z# Y0 w
    
45.               for m = 1 : tree_width
    3 t# y* g- v: Z8 {\" T; ^
46.                      if m ==tree_width8 Y5 [# u3 Z8 x
    
47.                             tree_nodeneighbor(n) = 0;
      n5 n/ |+ h$ o. O
48.                      else
    4 w# v* F\" N0 }; W. T
49.                             tree_nodeneighbor(n) = n + 1;
    & ^+ T- t* l: \' w7 F
50.                      end\" h9 f2 L8 O* i6 _$ I8 g( F
    
51.                      n = n + 1;
    4 X! J/ j4 C& V
52.               end8 O9 _  M8 }7 h& Z) ^! q6 v7 g
    
53.        end7 G7 k3 `; U, J7 k/ J
    
54. 4 X) R6 F$ m: P0 M6 k
    
55.        %下面是有效程序段，用栈实现1 x& i+ q8 m3 w7 Y- G8 ]
    
56.        stack = zeros(1, tree_depth);
    , G( O4 T4 ~# {5 q: q! U2 y
57.        nodeinstack = zeros(1, node_num);
    - F# q% Y\" C/ Y; p+ Y) B5 S% L
58.        stack_ptr = 1;: J7 F; E5 ~  T6 N2 ^( j1 ^
    
59.        stack(1) = 1;
      B+ A7 @/ g2 Q+ D8 I  c7 `
60.        nodeinstack(1) = 1;
    ( i7 q* z- z# e4 W- o+ T1 Q
61.        valueintree = seek_value;
    / M$ P  v, r% y7 r% I  N2 `' F
62.        nodeintree = 0;+ `$ O! D: E  {& Z* h! k# R) ^
    
63. 
    2 m$ ^: x& |( h\" C\" y: {2 V9 c8 P
64.        while stack_ptr > 0
    + A# V6 u; Y9 K) c+ d+ r% f
65.               n = stack(stack_ptr);
    3 V: m+ H& T- g2 @4 R
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3) i! T5 k+ O  b! ?
    
67.               %如果搜索到值，返回
      O* K# {& E, c2 h\" Z* I: b
68.                      valueintree = tree_nodevalue(n);6 [( x3 s5 h+ p# `8 @. v+ M
    
69.                      nodeintree = tree_nodename(n);) {\" `0 g4 R; {+ b+ a+ z3 c
    
70.                      break;8 w3 r$ \3 \5 ~8 ]0 X5 L9 q
    
71.               end8 w* e, |* o  e4 a4 |\" r6 u# C
    
72. 0 ~: a, i$ i! L# ^/ G\" i4 j
    
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    ! Z4 V; R  v# o- Y+ `3 B
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    0 W5 G6 }3 C0 z& u) s7 M
75.                      stack_ptr = stack_ptr + 1;
    ( i4 g) ], Q7 _7 M
76.                      m = tree_nodeson(n);- S0 N/ A2 h6 k; L& @3 j' L: K: Z
    
77.                      stack(stack_ptr) = m;
    % N2 a( ~+ a1 ^9 y& {/ V
78.                      nodeinstack(m) = nodeinstack(m) + 1;, @7 `# i/ N) s  o! z( I
    
79.               elseif tree_nodeneighbor(n) ~= 0
    3 p, O- [1 M( q( B! a) H6 |
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈# T9 e* h( m: T& U\" I4 B
    
81.                      m = tree_nodeneighbor(n);
    1 Q1 E8 }* o5 p1 u$ }( w
82.                      stack(stack_ptr) = m;/ D, a' G) {8 y2 o  s
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    , D1 U/ ?$ R4 p
84.               else& l1 r$ T/ Z3 G2 P
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    ! ^. s) q: f$ l0 |
86.                      stack_ptr = stack_ptr - 1;
    % n5 d4 V7 Z6 s9 w7 v1 f8 r0 R
87.                      m = stack(stack_ptr);
    , d) {+ e8 _( Q( U+ X  C
88.                      nodeinstack(m) = nodeinstack(m) + 1;
    * b' k$ Y( T+ V& [' [$ j6 A) g
89.               end
    # M! z$ c& T1 y9 s
90.        end

复制代码