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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   5 P  ]1 e2 v6 t: n. W$ v
2.        tree_nodename：节点名字或序号: W( M\" u7 s' o4 y' K
   
3.        tree_nodevalue：节点对应的值
   $ Y* u) l& b4 K/ r- {\" T8 |$ E: S
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   / |% z3 \; W! p4 a4 ?  n* X' V
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   7 N\" f8 A9 w! r' V
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
   ' }\" q7 K. F3 y( A5 }2 q- l
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   7 W- Y5 D8 z+ |\" n( |7 V) o# {
8. ' e) o+ z3 T: k' N3 S- }
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   ! [# |3 ]& Y, a- ~3 D
10. 
    & ]' @9 H\" o( Z
11.        %matlab源程序  a) \; T. l7 L- c+ C. v, _
    
12.        %输入：树的深度、树的广度、搜索的值: N\" d0 {# {0 I1 h; x3 E, X; l9 i
    
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    ; r/ t* h/ P2 |0 M- M
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)4 Z, j' d! V+ P5 a# C
    
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    + C5 z0 C4 P9 N$ I
16.        node_num = 0;/ k8 b  [+ W7 r  ]# H: o, i8 m6 P
    
17.        for n= 0 : (tree_depth-1). O' Y4 V9 E5 \# \! P/ t
    
18.               node_num = node_num + tree_width ^ n;6 x) o0 g7 i4 u5 X! {$ k
    
19.        end
    ) j* M- j: E1 q
20. \" Z! S- F6 m( Q; }- h
    
21.        %为树的存储空间赋值
    * w0 A; @$ V2 ~: A: [4 w3 ^
22.        %node name，按照广度优先为节点排号# G: R  |. P2 b$ U- B5 @  F
    
23.        tree_nodename = (1 : node_num);3 Y, b7 q) i. j# d; d/ s
    
24.        %node value
    + x3 `3 A4 ]6 c( m* B. T3 u, U, w8 G
25.        tree_nodevalue = rand(1 : node_num);5 g+ R/ y, s' w; ?
    
26.        %node father and son
    * k: g) e% K# z+ P. i2 e4 @
27.        tree_nodefather(1) = 0;& d' g\" h) p$ ]. I0 L) M
    
28.        tree_nodeson = zeros(1, node_num);
    * f$ e7 w) o\" u; L9 e2 S
29.        n = 2;
    + J9 p7 w: ~/ u+ p\" L
30.        k = 1;
      P! B) r% T- D5 w
31.        while n <= node_num
    3 U  T! g- f+ U
32.               for m = 1 : tree_width
    ' s  G7 d9 t) f5 C# ^. f# w2 B9 k
33.                      tree_nodefather(n) = k;
    \" B- o7 C+ S\" H* D
34.                      if m==19 p: G3 k& f* ?) i
    
35.                             tree_nodeson(k) = n;6 o! \& g( |2 b\" ^
    
36.                      end
    * w7 B  b\" e. K\" ?
37.                      n = n + 1;
    . W* H/ w3 U) I
38.               end2 h! p3 n& r, n+ o, T& \
    
39.               k = k + 1;+ n. V' c. x& Q
    
40.        end6 ]) F+ T- S  O\" Y5 p1 w
    
41.        %node neighbor
    8 m3 R3 {6 ]! ?: y( H6 h# u0 \! Z
42.        tree_nodeneighbor(1) = 0;
    9 O# w# ]  m4 ^$ I! N6 E( Z) \
43.        n = 2;\" x; u( i6 {$ {! n7 e& C0 ?( o
    
44.        while n <= node_num# @) x9 i7 h& f/ q
    
45.               for m = 1 : tree_width
    * s+ b8 D* A$ x- l
46.                      if m ==tree_width
    3 C! e* D1 k( e0 y7 i+ O4 V
47.                             tree_nodeneighbor(n) = 0;+ s+ C* g% j2 J7 x
    
48.                      else+ I5 `% p0 O( ?
    
49.                             tree_nodeneighbor(n) = n + 1;
    ' ]: }+ s) x9 {/ [% C# I9 I
50.                      end- P# n2 k! _' w0 X& ]4 _% d
    
51.                      n = n + 1;
    ; K0 g' }; L* S$ h2 P# f
52.               end6 F8 C/ a0 Q6 A# T\" t# ]
    
53.        end. H1 V, `, e/ Q2 E' K6 L
    
54. 
    % D. t$ H1 s, j0 N7 k
55.        %下面是有效程序段，用栈实现% c7 T1 G; j5 e' C# d0 w. v
    
56.        stack = zeros(1, tree_depth);
      B3 O! |6 e! `; f3 s
57.        nodeinstack = zeros(1, node_num);6 `, ~, q. y3 X5 f4 w) `\" K
    
58.        stack_ptr = 1;- N0 o. x/ M3 R6 I: h1 u
    
59.        stack(1) = 1;
    , ~0 {, b( b, @' a; \
60.        nodeinstack(1) = 1;3 @\" I  b, ~: p) ~3 k) O# k
    
61.        valueintree = seek_value;9 E, W0 L6 R6 ]6 F
    
62.        nodeintree = 0;
    1 Y# L+ W# j9 t4 C! t+ K
63. 
    ( S, w6 V0 a! v$ E; k& q- m
64.        while stack_ptr > 0
    8 `1 s8 c. d! K. u- t! m
65.               n = stack(stack_ptr);
    / m6 ~. Q5 x* A/ b0 C
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3( T% M4 R  r& x# a/ a8 l2 E& t3 H
    
67.               %如果搜索到值，返回
    0 V; ]- S4 s; @, A* b/ h+ G/ y
68.                      valueintree = tree_nodevalue(n);0 ]- }  C5 s8 d- z
    
69.                      nodeintree = tree_nodename(n);
    ' h, k4 @* B. b8 i4 m; Z( E
70.                      break;
    9 [7 g. I$ P, N8 e3 H- e
71.               end
    ; i& U+ c2 o7 G
72. 
      _7 j0 @: q* v) Q0 P7 {7 K% v5 a
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1. t/ _* T0 y, e
    
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈8 R, V$ l# X. x+ K
    
75.                      stack_ptr = stack_ptr + 1;
    3 L; G6 L5 u' N3 r$ V0 V
76.                      m = tree_nodeson(n);
    7 P+ o5 b: N/ R8 h) z. s2 Z
77.                      stack(stack_ptr) = m;7 L2 u& l/ Z, y+ t# n# z
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    $ w# h9 Y3 j4 l* P: m: H0 m6 G
79.               elseif tree_nodeneighbor(n) ~= 0
    ; a% }- M8 l* W9 B
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈2 c2 K  b2 ~% ~8 I* {
    
81.                      m = tree_nodeneighbor(n);
    . [# ^$ o: V' n) A7 k$ V, k+ t
82.                      stack(stack_ptr) = m;0 D+ C. O3 l' Q9 K$ c
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    5 v; _7 t$ n! z4 W2 v
84.               else
    6 q  _6 D! o- ^1 z3 }( M\" j/ ?+ c' e+ o
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    8 \$ {# ?/ r) S7 S8 q  @
86.                      stack_ptr = stack_ptr - 1;
    + ~% D; F% f& N4 `6 B
87.                      m = stack(stack_ptr);
    4 [; J/ ]4 T$ Z
88.                      nodeinstack(m) = nodeinstack(m) + 1;
    * _8 o$ o+ q& C( }/ R( _, M% [. \
89.               end# p0 N, }( P9 b; w8 i* W: p0 T4 @
    
90.        end

复制代码