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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   1 V5 H# Y7 C6 v, h5 c/ C
2.        tree_nodename：节点名字或序号
   8 d, u$ Y  {0 ]& H\" O. Y  O
3.        tree_nodevalue：节点对应的值' s! g8 W\" A) o/ U1 }6 k+ t' Y7 M
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空0 j( L( N4 N\" f0 R
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   + r1 H) ?( ?) g# i2 {2 e
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空* F6 l  Q2 ^) P9 ^
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。6 J/ `, p$ G( h' n- c) E\" U1 x3 N- A
   
8. 
   5 n\" O8 I: Z5 R% \) {: A
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。$ A# p1 {9 M% z% I9 H2 n. W9 b
   
10. 
    5 B2 O, D, r1 Q, B* v
11.        %matlab源程序
    8 o% W9 b: F: y# G$ [( L
12.        %输入：树的深度、树的广度、搜索的值
    2 c+ y4 c2 s. }7 t3 R* c% N- c
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空+ M  W7 W( A5 E3 C+ G
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)7 z3 b7 W! h% z  W5 U
    
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
      `; ~* g7 G4 s0 P' C
16.        node_num = 0;( F9 g2 i\" S# w8 F
    
17.        for n= 0 : (tree_depth-1)
    , c  g, y, Q9 d! x
18.               node_num = node_num + tree_width ^ n;
    : @3 d$ w- M% \
19.        end/ X\" {! U  ~5 X6 f' W0 }; _
    
20. 
    6 h) {2 D' f* P
21.        %为树的存储空间赋值) [# D& S( p8 ~( E3 H0 Y5 I
    
22.        %node name，按照广度优先为节点排号
    * E, E/ R# Z; i6 |2 U, z
23.        tree_nodename = (1 : node_num);
    + ?* f4 f  l% S' K
24.        %node value
    7 I/ z& \) e8 z; Q) E, G! _* Q
25.        tree_nodevalue = rand(1 : node_num);
    & h( a7 d  A) F/ f! d# `
26.        %node father and son; D9 E' D6 S1 \( Q8 I
    
27.        tree_nodefather(1) = 0;' S/ p9 z7 s0 T
    
28.        tree_nodeson = zeros(1, node_num);
    ! r# m6 d4 `4 I. ?3 p
29.        n = 2;
    0 @. z. q: x2 v; q. \
30.        k = 1;
    * T, h4 M9 r5 @* L
31.        while n <= node_num
    8 B8 }% N; _0 ~\" l& U( N  j  ?
32.               for m = 1 : tree_width
    \" I1 x$ C: N' d/ D* g5 T\" w
33.                      tree_nodefather(n) = k;
    # l. o2 ]# Y' ~6 o! h
34.                      if m==18 p% B  k$ |. T( P0 X, N0 O
    
35.                             tree_nodeson(k) = n;: \) i8 ~& K2 l/ |9 M4 [. x- e
    
36.                      end# J; O# B  d' M1 C0 z7 K
    
37.                      n = n + 1;% C4 N# y' @2 ?3 w
    
38.               end9 |+ G6 ?* W' b: g
    
39.               k = k + 1;
    \" i! `) s! e# y0 c, j
40.        end
    6 O& r* P% b+ {/ J! K9 V9 [5 a
41.        %node neighbor1 D- w& A6 w/ N7 M. ?. l
    
42.        tree_nodeneighbor(1) = 0;8 t' v$ R6 y' w; s
    
43.        n = 2;
    5 D2 [( V  E3 H
44.        while n <= node_num
    7 k\" q  }  o# {; y0 H
45.               for m = 1 : tree_width6 C* f\" o# q- L; n' J
    
46.                      if m ==tree_width
    & T5 W0 _8 @' y% x8 O8 @! b- x
47.                             tree_nodeneighbor(n) = 0;/ H& E% n* ]$ a- q# u
    
48.                      else
    , j1 s/ W, R( j5 E/ c5 B' L
49.                             tree_nodeneighbor(n) = n + 1;\" N& a4 T  o/ t0 M% }0 y; C
    
50.                      end
    0 [- C: e* E3 }5 O
51.                      n = n + 1;
    7 a/ C- X7 [. H7 U: \' n( s) \
52.               end; B  a- n& W0 \  `* O; j
    
53.        end
    ; S& p+ k% {2 A4 M' x3 }
54. 9 K; Q6 u' v4 @5 K3 f
    
55.        %下面是有效程序段，用栈实现& V( U# s; t% X
    
56.        stack = zeros(1, tree_depth);  v4 X$ e6 f/ n3 Y: `1 Z) d
    
57.        nodeinstack = zeros(1, node_num);* p/ R$ `; E& z1 q4 Y. J
    
58.        stack_ptr = 1;
    ! `! P# \  T: o5 x6 I4 D
59.        stack(1) = 1;\" ^1 u+ E+ _8 k8 V3 P) A6 o: k; x
    
60.        nodeinstack(1) = 1;  R7 q% U( v6 i
    
61.        valueintree = seek_value;
    0 ?9 G7 L+ @2 D+ k: ]: f
62.        nodeintree = 0;
    ! S5 @+ i3 T7 K
63. ' R- O1 {6 n  F4 U* B7 W
    
64.        while stack_ptr > 0
    $ c3 F' D3 ^- n7 A5 @
65.               n = stack(stack_ptr);! {9 F1 p; ?( |2 e0 V
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    + m, f# _' w9 n. }& q& |- K$ O
67.               %如果搜索到值，返回9 O% o; Y8 [( q1 ~: \
    
68.                      valueintree = tree_nodevalue(n);
    . i6 n4 O7 z+ V/ b( S9 f5 g
69.                      nodeintree = tree_nodename(n);
    6 N, Y0 w9 s- m6 g3 m
70.                      break;8 F& U) a6 {* i* x
    
71.               end
    8 `: K/ h, e+ F5 T; r- ]1 [- @
72. 
    & ^# z  |, M7 t9 y+ T
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    / U( u. f5 d' u1 s/ R  f
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    1 r- X! T* R1 v
75.                      stack_ptr = stack_ptr + 1;
    / ~$ h. ?2 s) d9 m
76.                      m = tree_nodeson(n);
      r/ F1 E2 q1 i1 z2 S; b
77.                      stack(stack_ptr) = m;
    3 G( e1 x, f# ]# h4 k
78.                      nodeinstack(m) = nodeinstack(m) + 1;- h  f9 U+ c' @) ~, H3 c
    
79.               elseif tree_nodeneighbor(n) ~= 0
    4 l$ k' B% p1 v- G, y
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈! S2 c5 U3 B1 }, X: k
    
81.                      m = tree_nodeneighbor(n);
    ; g: S7 r) \1 |3 G; v( V( ^
82.                      stack(stack_ptr) = m;3 |, |6 g: E4 I$ ]  a5 k
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    3 ^4 L5 W- e  o0 I5 Z
84.               else% L8 K. g6 j) @4 \5 V$ L
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一+ v4 E* i\" z$ f4 a8 `% u
    
86.                      stack_ptr = stack_ptr - 1;
    - I* y, \1 }0 z- r9 n# A
87.                      m = stack(stack_ptr);; u) B9 u# b. h( U
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;5 j' Q: _7 a8 }
    
89.               end
    2 A2 N. s- m. @% r5 A
90.        end

复制代码