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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   \" i: E( O) T3 R& m
2.        tree_nodename：节点名字或序号7 u5 k$ P7 m$ @
   
3.        tree_nodevalue：节点对应的值8 D. w# a. U1 V* K+ _
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空8 }  b  r3 w6 N
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空7 l; T9 |: z) ?% J7 P; z3 K# L
   
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
   3 G0 ^  R# h$ d- K/ T0 z7 X& ]
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。7 p, Z  o6 C' m1 k
   
8. ! b0 {; y; M  Z, S) s
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。7 Z5 k/ j2 s& @: Q# S, ^! {
   
10. 
    0 z' `8 J/ P  x, ?( S* ^
11.        %matlab源程序
    ' {6 Z. q, G: P$ Z; b# A
12.        %输入：树的深度、树的广度、搜索的值; ^: B5 A1 g  e0 f7 z! s/ q' P
    
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    , z$ y0 c$ {3 J\" K\" l. ~! l
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)) ?, Q* f5 k\" B
    
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    # M5 X2 r! \8 n\" S( R* D: u
16.        node_num = 0;
    # I9 t. F0 E$ D, T4 ]5 A! R
17.        for n= 0 : (tree_depth-1)
    % D: }1 G  j* y
18.               node_num = node_num + tree_width ^ n;
    8 _! k. u6 R; n3 W2 E
19.        end
    . O& H7 e' p5 L\" H4 W9 W# o& Z
20. 
    7 F! g0 V, n2 b5 T/ u9 m
21.        %为树的存储空间赋值, O* D7 e% K* ^8 [3 y
    
22.        %node name，按照广度优先为节点排号+ c, \7 Q\" ^+ r- M9 ^$ p
    
23.        tree_nodename = (1 : node_num);
    5 h; a1 L/ y0 W: a
24.        %node value
      W2 p3 i* d& X, `, [
25.        tree_nodevalue = rand(1 : node_num);( H; }5 x1 e2 c7 R% w$ K
    
26.        %node father and son- I7 ^; g) j+ S+ _6 [. j
    
27.        tree_nodefather(1) = 0;
    6 X7 r+ a1 t' s/ a
28.        tree_nodeson = zeros(1, node_num);
    . w( s  C  f- C; m8 z
29.        n = 2;
    6 W' O1 m, _9 M) p' ^
30.        k = 1;
    ) d0 z, ~, Q+ m
31.        while n <= node_num
    $ j# o* o7 K$ _+ ^$ k8 b1 y
32.               for m = 1 : tree_width. R7 D5 I* M5 i
    
33.                      tree_nodefather(n) = k;. N3 S7 Y4 ~3 E
    
34.                      if m==1+ S6 M% ?3 q- G\" U! e0 ]* X3 H
    
35.                             tree_nodeson(k) = n;% I! u, k) a: ~
    
36.                      end
    3 C7 A* P% U# i( G\" b0 |/ F8 y
37.                      n = n + 1;# H; n# m7 u; ?4 R) v1 s
    
38.               end
    & u- s; Y0 y9 }9 m, M; ^9 P+ i
39.               k = k + 1;5 V7 `1 q2 b+ b
    
40.        end9 `* M! G2 [* P
    
41.        %node neighbor9 {5 u: Y9 y6 t4 b( k* u. a* u
    
42.        tree_nodeneighbor(1) = 0;
    $ a2 \! S3 b7 i4 ]; c2 b6 c- c
43.        n = 2;/ X1 I9 q1 m4 j\" ^
    
44.        while n <= node_num
    # @; a7 j0 _5 U+ @. A
45.               for m = 1 : tree_width* L( ]; r' {# S; ]
    
46.                      if m ==tree_width2 }\" t0 E\" [. J\" i9 l9 r5 N( O' W
    
47.                             tree_nodeneighbor(n) = 0;& X: s( _7 ^% R, v2 D% |
    
48.                      else
    9 m4 B3 P. t& K# u
49.                             tree_nodeneighbor(n) = n + 1;7 o1 S\" O& F: w' M
    
50.                      end
    * c! d( M+ t0 F  V* w2 W
51.                      n = n + 1;) D2 u) N, m, C\" [, U6 D. X\" u8 t
    
52.               end, x6 `7 h% E6 L! A- Y4 b$ v\" k
    
53.        end( u& J. X  U& \
    
54. , X' k5 O6 b  j' O  K7 i3 a
    
55.        %下面是有效程序段，用栈实现9 U; s0 o# b% m
    
56.        stack = zeros(1, tree_depth);
    \" u; Z9 m* u$ F' \
57.        nodeinstack = zeros(1, node_num);
    * m4 Q, m  L\" m
58.        stack_ptr = 1;
    + J; w* E+ d! O$ ?2 F, F
59.        stack(1) = 1;
    ! m- p4 Z; c9 m
60.        nodeinstack(1) = 1;
    & e4 a: v& N7 b2 _
61.        valueintree = seek_value;6 y& t/ q/ P/ H+ b* }2 d
    
62.        nodeintree = 0;
    % x  I, l. \; G\" }% t: c
63. 
    $ t5 g$ j+ C/ ]: F9 F) R  n- ?: [
64.        while stack_ptr > 0/ ^* k& I( E2 ]: u
    
65.               n = stack(stack_ptr);  g2 n& ]% [& ~  s
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3+ R9 d7 a! t) i/ I
    
67.               %如果搜索到值，返回5 O/ g; R% \. K* T
    
68.                      valueintree = tree_nodevalue(n);
      e) ?) }. u! [3 M9 o
69.                      nodeintree = tree_nodename(n);# s+ s4 h- ?7 e/ c% q/ q
    
70.                      break;
    ( M# j) y* ^+ Z  z( e
71.               end' N6 W  `! L/ ~' L) ~: F' h
    
72. 
    % q! \! t4 y% G/ b  z4 ?8 Z& Z
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    * g0 _: i! w4 \7 e3 U
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    $ j/ H! W5 L6 z. m/ P' S1 u
75.                      stack_ptr = stack_ptr + 1;
    & e% n# T& W+ u5 Y1 r2 j
76.                      m = tree_nodeson(n);
    . k\" a$ o1 J: ^( \% U
77.                      stack(stack_ptr) = m;7 k- v8 E$ @* \
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    ) W- E& x& G  J; B0 I! }7 D
79.               elseif tree_nodeneighbor(n) ~= 09 o  F/ ~2 Y* Z! d+ E! b  R
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈  U. P6 }1 u$ J; H2 U
    
81.                      m = tree_nodeneighbor(n);! R  L) W4 n' P6 }
    
82.                      stack(stack_ptr) = m;2 |! w; e  P/ V, s8 h
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;7 W7 G$ f' a1 v! y
    
84.               else
    ; r3 v5 j9 z+ }; J) H. P  q; e
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    4 F6 F; ^9 m% @! g
86.                      stack_ptr = stack_ptr - 1;+ D; g1 F; Z8 c' f/ ?* g# C
    
87.                      m = stack(stack_ptr);, P7 b! m- o5 k( D5 f% d
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;; N) F$ Y' D1 ]- q( j
    
89.               end
    . g8 E/ N- ^4 @4 ^) A- i- E# k
90.        end

复制代码