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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：' \+ ]) N9 h6 A3 k- C+ ]
   
2.        tree_nodename：节点名字或序号9 m' F- M# F4 B  [( P2 I7 s
   
3.        tree_nodevalue：节点对应的值1 Y6 |9 I% m( v
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   * s. H9 q) \; O  S
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   5 m' y; E) E# _( m
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空% K- y; n3 Q* c% ?\" ]$ r
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   \" }. t) I9 J& J; {+ w: `' |% A
8. 
   % D9 I3 W5 _- x# s8 N5 L6 C1 Y
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。7 L6 l# x) V$ t6 i5 v/ {+ J
   
10. 
    0 c- f4 v& J/ c7 g\" G6 K7 i
11.        %matlab源程序
    \" n7 I: O4 [) o1 M% o% x, q
12.        %输入：树的深度、树的广度、搜索的值
    2 _$ S& q% k( e- c7 M9 x
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空& ?4 A: y5 c, n- k1 z$ {
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    % @0 W5 t! k6 S- G5 r0 l9 D- G8 q
15.        %根据树的深度、节点的儿子数量计算树总的节点个数. f$ Z% s, Q) q2 ~; }
    
16.        node_num = 0;' t$ N0 ~7 `' Q
    
17.        for n= 0 : (tree_depth-1)
    \" W4 t9 V: h6 n, _
18.               node_num = node_num + tree_width ^ n;$ C, H& k  a/ @9 W; s
    
19.        end
    3 p' m* f3 {! j6 \# }; h
20. , ~' Y3 M$ ?- Q4 r- @3 n! w
    
21.        %为树的存储空间赋值4 R9 M+ H# z6 M6 s\" }
    
22.        %node name，按照广度优先为节点排号
    6 j+ y5 J4 |7 ~* |3 g8 q
23.        tree_nodename = (1 : node_num);
    . [6 ^6 f' d0 \' s- l# S
24.        %node value* ~# q6 j; H3 h' _
    
25.        tree_nodevalue = rand(1 : node_num);
    9 }& L4 Y- Z2 Y3 C: u
26.        %node father and son
    + @- p8 n3 i! @) |  M- S  l% P  H
27.        tree_nodefather(1) = 0;
    6 S! O' t1 I5 a. c# W1 r, B
28.        tree_nodeson = zeros(1, node_num);. h5 f) K$ H. u9 B( g
    
29.        n = 2;
    3 m3 Q7 s1 r8 S9 H2 L1 X
30.        k = 1;
    1 p$ M6 ^) u/ @& U  x
31.        while n <= node_num  q: |5 l; J, ?4 U. g
    
32.               for m = 1 : tree_width3 O2 q  _) Q) h4 r) e
    
33.                      tree_nodefather(n) = k;
    8 H9 ?& @5 w$ M5 r\" j& Z1 e
34.                      if m==1
    8 d( O: A7 W% w3 \
35.                             tree_nodeson(k) = n;
    ) q+ O8 t8 {+ y% O% v8 b6 h+ k/ r4 v  i
36.                      end
    # ]- L8 w7 l: o\" z
37.                      n = n + 1;
    ; c3 b# r' u- |5 g4 b6 N  E
38.               end
    / O& ^$ Z& U) Z+ U* I0 A0 ^# @
39.               k = k + 1;
    $ W( V  W; Y* O& y5 {3 P( D
40.        end
    ) w! ~0 k4 s: g. z& v
41.        %node neighbor) ]+ s- Z$ Y2 x4 n+ m- g* }
    
42.        tree_nodeneighbor(1) = 0;
    . B. a$ k  ~. b9 N, O
43.        n = 2;& W( u& X( b. t+ G) C0 F( o5 J
    
44.        while n <= node_num
    % O; d, y$ n5 P0 d. J
45.               for m = 1 : tree_width\" R; @) X- C6 E$ N3 v- |- `, P
    
46.                      if m ==tree_width8 |* l\" n7 z' s/ w
    
47.                             tree_nodeneighbor(n) = 0;
    1 C; `6 Q+ i+ m5 O' C
48.                      else! Y- M# o' V1 g, L3 J
    
49.                             tree_nodeneighbor(n) = n + 1;
    # E6 J4 N1 c( m. \2 @
50.                      end
    . U- U8 w& B  g
51.                      n = n + 1;# R7 e5 X! v' T, _# }
    
52.               end6 J, I0 d5 @, @) I
    
53.        end
    , n& I* r* d' s1 W3 o
54. 
    1 J/ i* I+ h) s' b
55.        %下面是有效程序段，用栈实现
    - a6 p6 P/ F) r- M9 [6 V+ t# Z# J  g& l
56.        stack = zeros(1, tree_depth);
    : k- ^( |  n$ g6 K8 E
57.        nodeinstack = zeros(1, node_num);
    - _8 g( l& G4 s) s3 ?' x
58.        stack_ptr = 1;0 m: n  B9 N7 Q
    
59.        stack(1) = 1;
    6 b2 M1 N  M' E1 _- c' R# z, ^
60.        nodeinstack(1) = 1;
    / v) i) p! h! }0 @/ P
61.        valueintree = seek_value;\" X& n9 x; a0 Q- _
    
62.        nodeintree = 0;5 z2 r' H8 U; |9 K' i0 T$ Q
    
63. % S8 {$ X& y+ d\" |
    
64.        while stack_ptr > 0/ p' L/ _) N6 J3 h- R3 }# B' h
    
65.               n = stack(stack_ptr);1 I# N8 _# E0 i) ]  N
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    $ |# E3 v. U7 B1 G/ [& S/ x
67.               %如果搜索到值，返回
    , @9 k+ x( Z' z/ D. |4 Z4 _& K
68.                      valueintree = tree_nodevalue(n);. K1 ^. L5 |# N3 Y% P
    
69.                      nodeintree = tree_nodename(n);# I2 i8 l6 H4 G2 L. ^& M
    
70.                      break;
    % {) q: m3 p) Y: V% t
71.               end% ~. Y4 I9 b. M: P- \
    
72. 
    ' E2 ~, ?2 M8 l5 x7 V' [
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    \" \+ w7 L! n\" X
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈$ M8 Y$ t* \1 C- M' i2 ]; q
    
75.                      stack_ptr = stack_ptr + 1;2 D$ B/ U2 \% ~/ r7 J
    
76.                      m = tree_nodeson(n);
    9 Z$ e9 }\" @\" _) [- n8 p) i& u
77.                      stack(stack_ptr) = m;0 ]  l- \) D. V' A
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    # C% T7 m  Y7 @% }/ x6 s
79.               elseif tree_nodeneighbor(n) ~= 0
    5 @/ x, B& |3 r3 N0 h
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈! |7 o& Y: W+ z( f5 B; A1 M; w4 Z) d
    
81.                      m = tree_nodeneighbor(n);
    - U5 Y4 K$ w2 z+ S$ ]+ t- Z5 ?( p9 J
82.                      stack(stack_ptr) = m;
    9 \5 `  n0 I4 Q7 S% \6 U
83.                      nodeinstack(m) = nodeinstack(m) + 1;% t, V6 R2 s+ v
    
84.               else4 X: a4 F\" L( m0 z
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一; n( B' N6 w6 q. T2 v7 |
    
86.                      stack_ptr = stack_ptr - 1;4 O2 s! I4 m\" R, u8 i% P6 _
    
87.                      m = stack(stack_ptr);3 Z7 i, R, m& F* }& m& s! I+ w
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;
    : }7 ?* l5 L0 @! K( h6 }
89.               end
    ( K  A: v\" B7 w9 r
90.        end

复制代码