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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：/ Q- f8 }8 ^6 X4 C* N& B1 O* f
   
2.        tree_nodename：节点名字或序号
   7 B# T6 P: O  S* Q: ^
3.        tree_nodevalue：节点对应的值! o! @) j* G& k' O. [\" C6 k' b
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空* {8 l5 ]- j/ B$ C$ ^( S& }
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   5 G. F' Q! {) y+ `% `2 O; ^; u2 o
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
   & b; a9 U9 |4 `\" q5 N% @8 ^! }, I
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   ! {: u/ V% A6 y7 Y! E
8. . }* N- e' O; p8 P1 U7 \* h& T
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   . l3 j' O+ d/ e* v
10.   C# f7 d6 {' v& g
    
11.        %matlab源程序
    * ], P4 a9 K, i: k
12.        %输入：树的深度、树的广度、搜索的值
    5 |! b( r; t\" e% J( P+ G6 O8 n
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    6 g\" P% E! u3 e! m: n* Q0 |
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)' U: m* x' Y' h- ]\" n
    
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    ( D% _9 u9 M; D5 P) M
16.        node_num = 0;
    % d3 Z\" [1 z0 w. O* X1 n
17.        for n= 0 : (tree_depth-1)
    ) f, _' m* Z6 j: Z5 U
18.               node_num = node_num + tree_width ^ n;! \+ i( m- `$ a
    
19.        end8 z! z5 t2 m' z( U\" @9 Q. x) E
    
20. ! x; ~9 ]5 O5 d: e  u9 w; N
    
21.        %为树的存储空间赋值' P& h5 |; U) \/ |
    
22.        %node name，按照广度优先为节点排号
    & N- a+ s- r* N\" O) S7 s4 ?, M
23.        tree_nodename = (1 : node_num);/ S0 {) Q& j! g( u/ v
    
24.        %node value
    ( O, y4 j+ F8 V$ v' l0 A
25.        tree_nodevalue = rand(1 : node_num);
      m+ z8 \! Q0 U9 ?$ a
26.        %node father and son
    ! U; r( R, T\" N6 X  A  q/ _
27.        tree_nodefather(1) = 0;
    7 G! @+ w( E- G3 C
28.        tree_nodeson = zeros(1, node_num);
    - {8 d1 z! J$ t$ H, R5 {
29.        n = 2;' ?+ r) Z: N$ \- C; J
    
30.        k = 1;
    ! T& I; w7 ~& c, `9 {
31.        while n <= node_num* L8 r1 V0 n5 p8 s
    
32.               for m = 1 : tree_width. g- d1 P' j; I7 @
    
33.                      tree_nodefather(n) = k;
    ) ^9 {  \0 n8 N8 W# @
34.                      if m==1
    6 H  D  y! Y3 n- U* [
35.                             tree_nodeson(k) = n;; C9 C& W1 F% C6 J0 s& P
    
36.                      end
    $ X3 D\" ]9 ]% z2 u8 K9 v8 k6 J
37.                      n = n + 1;
    ) J0 d% o5 r% U  c# \% D
38.               end) |1 a' v) `- V
    
39.               k = k + 1;
    % y6 x0 u3 y2 u% `, n
40.        end
    8 |( K+ @3 U/ j% C/ [
41.        %node neighbor
      J/ P; _+ h. q. s
42.        tree_nodeneighbor(1) = 0;
    * f0 I) s# ^- t; {3 V
43.        n = 2;5 {- n0 B7 h% o4 `
    
44.        while n <= node_num
    \" R, y/ ]5 K2 ]) U1 m3 Z
45.               for m = 1 : tree_width; u$ m; [1 R( b+ P2 m/ a
    
46.                      if m ==tree_width
    1 V: m. Z) d0 z\" ~3 J
47.                             tree_nodeneighbor(n) = 0;
    2 ^' A7 D- V( |0 ~' B2 [/ j- `
48.                      else2 a4 M% Q* ?, W$ T  }7 K! F+ U7 M
    
49.                             tree_nodeneighbor(n) = n + 1;
    % f% P1 V3 `\" |% ^4 W
50.                      end- D# o# E1 ]1 i1 [; K- q
    
51.                      n = n + 1;& h) `& o3 c' [% p2 ?# n
    
52.               end% e  |; n- B9 `% B( ]
    
53.        end
    - B6 L  Z; i! x6 m- F' o
54. 1 [# V- h( E4 B( ]- s\" b% d6 e% g6 o# c
    
55.        %下面是有效程序段，用栈实现) W7 [. G4 [0 A# u; J4 [+ B
    
56.        stack = zeros(1, tree_depth);
    : i: o8 C. X4 [! L) N- ^
57.        nodeinstack = zeros(1, node_num);
    4 c' A% u0 N! B7 H4 ?
58.        stack_ptr = 1;
    9 r( W5 O; s  ^/ U
59.        stack(1) = 1;8 ]\" m4 ?0 G& X* K# H, a
    
60.        nodeinstack(1) = 1;6 V# ]0 A& n3 F4 H
    
61.        valueintree = seek_value;3 S\" i6 t\" I4 Z
    
62.        nodeintree = 0;
    0 s# }7 v* D, \( Z0 B: r2 W
63.   E: F6 N1 x# n- p; J+ Q5 R8 V
    
64.        while stack_ptr > 01 t8 _9 `  L# O6 q; f5 W
    
65.               n = stack(stack_ptr);
    1 l: i$ t9 S0 A$ w% C
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    / l( c7 F. L8 k1 o8 J
67.               %如果搜索到值，返回! w  H5 ?# N1 A6 U2 Q' ~  |5 z) \' {5 a5 q
    
68.                      valueintree = tree_nodevalue(n);
    , s, i5 m6 b+ Z6 b9 D; \$ ?+ y
69.                      nodeintree = tree_nodename(n);4 I9 H* L7 w% v, h# h
    
70.                      break;
    $ ]0 X- C* N5 v) |- p9 l\" A
71.               end: Z3 U5 F. x7 R: t4 n, R3 U
    
72. 
    / |* v8 f; X0 N# @
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    & y! L# @9 u* q\" Y5 Y* H8 J
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    , h) P/ f- {) K; X
75.                      stack_ptr = stack_ptr + 1;6 Y& x; ?3 t% O; s: o% z, h$ A
    
76.                      m = tree_nodeson(n);8 t9 G. P' U\" t; P( {5 _
    
77.                      stack(stack_ptr) = m;
    / M* O) ]* j\" U( O/ P% B3 H8 \7 L- k
78.                      nodeinstack(m) = nodeinstack(m) + 1;! r. ~* Q2 }! |- z/ z
    
79.               elseif tree_nodeneighbor(n) ~= 0' o; L/ C5 G$ o! z
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    ( J. b4 y3 p9 ]4 Q% c, B$ G2 S\" u; K8 \; |
81.                      m = tree_nodeneighbor(n);: y5 g8 s\" j) U, m3 t
    
82.                      stack(stack_ptr) = m;
    8 S0 c6 J4 ~! [, L2 l. O0 B
83.                      nodeinstack(m) = nodeinstack(m) + 1;/ W) }9 v) Q( G, e3 H
    
84.               else
    6 q) o\" S3 K/ a1 C$ x
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    \" u+ ?) b: M8 I8 @, v' A1 {9 f
86.                      stack_ptr = stack_ptr - 1;
    * T$ U. S4 r  s$ `; j  I9 ]
87.                      m = stack(stack_ptr);2 Z( w, x% f1 j\" U\" z2 W& h
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;+ J% k& Z) _: }/ y2 Y
    
89.               end
      S- m$ m0 ]& C1 j
90.        end

复制代码