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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   - ?& Q. v; ]5 O
2.        tree_nodename：节点名字或序号
   4 Q1 X5 ^' J) Q0 b
3.        tree_nodevalue：节点对应的值
   0 [; m, K. V( f' w
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   ( }1 g! Q$ b! L  c) O2 z
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   & \2 t+ E4 `+ S
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空7 t/ l1 v7 x8 [; F
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。7 j( u( ^% D, T7 U, M: `; C) B
   
8. 1 O2 V2 D; r* r& v8 E
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   7 C6 g- G, R0 `; Y# o' b
10. 
    0 N! z& u# x/ V1 g
11.        %matlab源程序
    & [* z1 I. i6 T/ j
12.        %输入：树的深度、树的广度、搜索的值& X* l* k& @) M0 t$ C5 g! K* L
    
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空2 M! K  F+ h& h0 A  T3 M$ R8 B
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    , U+ p0 h$ F  r* f
15.        %根据树的深度、节点的儿子数量计算树总的节点个数8 k) r; B* l1 `. s! x, c- a. u( T9 X
    
16.        node_num = 0;
    1 e* e# V  ~% s7 U0 V
17.        for n= 0 : (tree_depth-1)- m1 o\" S: F\" V4 ~; R! z
    
18.               node_num = node_num + tree_width ^ n;
    1 E- I! I  n1 \\" k6 E6 q
19.        end( @7 t/ s\" o% |9 M2 A0 r, M  X
    
20. 
    4 ~* T4 }. U( O  v% z3 b
21.        %为树的存储空间赋值
    ) W/ r. L4 U8 b5 J
22.        %node name，按照广度优先为节点排号7 A$ h: }+ l+ r9 G
    
23.        tree_nodename = (1 : node_num);
    - t. Z: ^\" b, b- o. g
24.        %node value
    7 t\" b% U' A1 M' p: \: S
25.        tree_nodevalue = rand(1 : node_num);
    ' o* Q( S8 x/ e' w7 n  ?
26.        %node father and son) \. [9 \8 p3 F% c. q\" K# R. p4 |
    
27.        tree_nodefather(1) = 0;
    * C/ L. o& I# q
28.        tree_nodeson = zeros(1, node_num);7 v- I' C' t% W5 U  q
    
29.        n = 2;
    9 f+ @\" g: W2 T  k  z2 l
30.        k = 1;+ \+ _6 v. J9 q: v5 ^8 P' c# s
    
31.        while n <= node_num/ [9 }4 A8 B. h! |
    
32.               for m = 1 : tree_width$ M. L; C) P/ C) q8 G% Y. [
    
33.                      tree_nodefather(n) = k;
    + p3 @0 O- F: e7 ~# r0 {  s
34.                      if m==1\" {9 C* m7 J! t5 R
    
35.                             tree_nodeson(k) = n;' f% |4 f& A# Z4 j: N. i
    
36.                      end4 I1 B( z' R# e9 g& U
    
37.                      n = n + 1;2 d& x8 R) u+ K4 M3 U
    
38.               end
    ; ], J) O, C0 f
39.               k = k + 1;
    % F5 D) L: p1 s6 w
40.        end
    $ V% D- ~& M9 j9 N1 b
41.        %node neighbor
    9 V/ J$ ~4 `9 {  X' k9 G
42.        tree_nodeneighbor(1) = 0;+ f! r$ p* {! Y# ]/ v
    
43.        n = 2;+ X* k+ m- F/ a! X
    
44.        while n <= node_num
    : _3 J$ r& i0 l/ G
45.               for m = 1 : tree_width
    * T& r1 c4 ?( ?! S' _( r4 }/ P* D0 g
46.                      if m ==tree_width# v% x: k- |$ X+ G1 a' C
    
47.                             tree_nodeneighbor(n) = 0;
    ; B' W8 S+ W- D- X% y& q+ G
48.                      else
    ! G& |1 V0 r$ t. I) H- _. ?
49.                             tree_nodeneighbor(n) = n + 1;$ \5 h) I8 R4 d. m; d
    
50.                      end
      G1 P8 G3 _7 ?6 {\" `& _4 [+ l9 P
51.                      n = n + 1;
    4 _' o) e9 u2 m/ S; N% U) k
52.               end
    3 u0 P) s\" m& X9 p' i! b. s2 ~+ e
53.        end
    \" F8 y  u( d+ c/ c* {+ O& w! w7 h
54. 
    3 _( L, g3 Y. Q4 Q5 w: U4 L1 x
55.        %下面是有效程序段，用栈实现+ b6 a7 E! O* U* I/ `
    
56.        stack = zeros(1, tree_depth);5 `9 ?# z' C: X: Q& F
    
57.        nodeinstack = zeros(1, node_num);
    % |  m5 M# |$ R\" w; d* u6 |
58.        stack_ptr = 1;
    # J4 H% s* A7 X' M
59.        stack(1) = 1;2 [2 K4 ?; s# f% @, F
    
60.        nodeinstack(1) = 1;
    * O* d. q7 [' z6 S5 f: e1 M
61.        valueintree = seek_value;8 C! f4 u; }\" Z\" o8 a& d! u, J% Y\" @# o
    
62.        nodeintree = 0;! W2 a% U8 T3 @, c
    
63. + i2 {& l. X2 l
    
64.        while stack_ptr > 0
    , z. R4 g3 j. i/ B
65.               n = stack(stack_ptr);
    6 j* I5 m0 J2 Y) w  X( N
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    6 j. j; d; M7 T\" _9 x8 @
67.               %如果搜索到值，返回3 n6 Q9 f, t' m+ G4 t9 E, U
    
68.                      valueintree = tree_nodevalue(n);, b7 s1 g$ {9 W  j  _
    
69.                      nodeintree = tree_nodename(n);$ Y  ]& O9 y; ?, ~
    
70.                      break;
    % d- z% U) ~% O/ @1 Q( U8 Y
71.               end- M# s# }0 I3 ]& R- C
    
72. / A6 O' }7 q9 Q+ o8 Q# m$ Q
    
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 10 G) M; Q, c0 A; b& c
    
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    % [/ ?6 {( h7 j
75.                      stack_ptr = stack_ptr + 1;2 g* X1 j2 t, \/ v7 R0 f
    
76.                      m = tree_nodeson(n);8 S: {6 G, n' ?( f' ^
    
77.                      stack(stack_ptr) = m;
    - J/ [4 R/ A& q/ G& i1 a* [
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    4 j2 a( v% Q7 t  T
79.               elseif tree_nodeneighbor(n) ~= 0
    # Y: z. v; _7 z8 Z
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    2 Z0 O0 `4 ?. \
81.                      m = tree_nodeneighbor(n);
    * C. w) G8 Y) e' P$ x# z; h
82.                      stack(stack_ptr) = m;
    & ?, e% r' \5 U8 g4 p9 ?: V
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    3 i9 H1 w3 b0 z0 l' R, K
84.               else
    ) f8 }7 G$ X$ p+ I/ h6 v
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    9 ?6 p4 n: b# R4 m8 |
86.                      stack_ptr = stack_ptr - 1;9 a. |9 f. }# r0 E  y\" [3 I
    
87.                      m = stack(stack_ptr);
    : r) p. ^1 ~3 R. X0 _
88.                      nodeinstack(m) = nodeinstack(m) + 1;
    0 j4 `: s9 s6 l; o  L0 }
89.               end. x. h7 _3 O3 b- T
    
90.        end

复制代码