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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：, P3 `) U. }  B6 }8 V6 |\" c8 @9 y
   
2.        tree_nodename：节点名字或序号% H6 w; `8 I. g\" z+ T
   
3.        tree_nodevalue：节点对应的值5 ^  T) N4 F+ _, N
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空* A5 G4 r; \, V
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空; X, K$ M/ }+ K# \5 [  P
   
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空3 @1 c/ o8 V: c& R( V) i
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   , f8 l  [/ v; K( J' H  ~
8. 1 R! z% k; V# b5 `! Q
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   + ?% Y8 c% l8 T* V; o, n6 O5 ?
10. ; d\" Z\" U* I\" i$ v+ x! y' Z7 A
    
11.        %matlab源程序! ~0 ^* H; c* ^+ D2 W  \
    
12.        %输入：树的深度、树的广度、搜索的值
    \" Y4 q) {7 f; f& c2 f* q
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    & ?\" k1 n, ?6 F( ]( k* [
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    ) @% s+ _7 \; L2 R9 k
15.        %根据树的深度、节点的儿子数量计算树总的节点个数) D( K' n: H1 L- |* v
    
16.        node_num = 0;
    ! G& z# D3 I$ D9 n/ R
17.        for n= 0 : (tree_depth-1)
    7 a) m9 Q6 X\" ~8 R. S/ q9 m
18.               node_num = node_num + tree_width ^ n;+ |2 x$ g4 d2 J  I
    
19.        end  u( l! K% N) t+ R8 @' N
    
20. 2 X: M# O. m/ |( I/ z4 u
    
21.        %为树的存储空间赋值: n+ y/ P6 t( j% e& p; B! [* c* G& i
    
22.        %node name，按照广度优先为节点排号+ I1 z) C! u+ e' d; n) a) U+ G  R
    
23.        tree_nodename = (1 : node_num);
    ( _\" b- f( r5 n2 y2 j0 o\" x  [- V
24.        %node value0 h, [# x) X) c% H1 t; r
    
25.        tree_nodevalue = rand(1 : node_num);\" D. o( X' U' h7 {( D. C% W8 z' ^9 N* V
    
26.        %node father and son
    5 y# o+ Q* B; K1 v' B7 E: b. K\" ~
27.        tree_nodefather(1) = 0;- `* i4 o3 u  Q: V0 a, Z
    
28.        tree_nodeson = zeros(1, node_num);
    / V2 U$ ]$ x  j9 R) g& \* f
29.        n = 2;( L& D$ E3 o' T\" b1 H$ P. ]$ J8 V
    
30.        k = 1;
      I\" |$ h, w3 w1 j$ f. |3 L( l
31.        while n <= node_num' X) N( l! f# w
    
32.               for m = 1 : tree_width
    ' X' x# Y% u; |* a1 I, E6 Z
33.                      tree_nodefather(n) = k;
    5 [\" d& \; |% b# n6 O: F# A
34.                      if m==1
    . ?5 c6 R. U* V( G8 f
35.                             tree_nodeson(k) = n;
    ; o! u9 c) z; e9 v( j
36.                      end
      F5 E$ T  `2 T# Y4 {6 \
37.                      n = n + 1;
    * A( ~+ N\" z: m$ ?  A/ f
38.               end; j4 R( H\" n6 _& l$ h# ~7 j1 K
    
39.               k = k + 1;* z8 G0 u( |& s7 N$ t
    
40.        end
    ! @* _& m3 x, G
41.        %node neighbor0 B( w( L' q2 m0 e  [
    
42.        tree_nodeneighbor(1) = 0;- p  X$ n) S0 s
    
43.        n = 2;
    & ~\" i' `9 Z3 D4 n; X
44.        while n <= node_num; F' L. p8 h5 \* F3 O+ V! `
    
45.               for m = 1 : tree_width) J* ~) E\" e1 l3 W\" j
    
46.                      if m ==tree_width- I1 R) I% K' M$ Z+ h
    
47.                             tree_nodeneighbor(n) = 0;; p. h2 E, ]$ F. Q, d% T' q- G1 n
    
48.                      else: f' N* O$ I2 q; B0 F) X) x  K: x
    
49.                             tree_nodeneighbor(n) = n + 1;
    2 H, u4 j/ }- z. ?5 r  c
50.                      end
    $ H/ M8 e& J. ^: r) S
51.                      n = n + 1;
    $ ?8 e) k5 D/ k8 O
52.               end
    : w1 {/ s( Z6 S; E8 g
53.        end
    0 k2 D. o; L, B9 Y- ~
54. 
    ( l2 y3 N8 s7 K9 M# K# d# @
55.        %下面是有效程序段，用栈实现
    0 z; i/ u, B' K+ z9 Z; C% t
56.        stack = zeros(1, tree_depth);. n' h' a! X: ~$ R' V! ]
    
57.        nodeinstack = zeros(1, node_num);
    \" K3 [  _1 u- r: P* f7 L
58.        stack_ptr = 1;5 n8 E\" @! F9 O5 |
    
59.        stack(1) = 1;1 y7 D+ }! v* Y( h* p
    
60.        nodeinstack(1) = 1;
    ( y8 u( T2 t, z
61.        valueintree = seek_value;* B7 o\" g3 h2 z
    
62.        nodeintree = 0;
    2 m\" [$ N( L& J  f: c+ C\" t
63. 
    4 X* k% L: v  ~6 c9 q
64.        while stack_ptr > 0: u1 f( p+ s$ C0 L$ r' M
    
65.               n = stack(stack_ptr);0 f! Q5 t& I; Y/ ?' \
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3) L* a) L- \# p
    
67.               %如果搜索到值，返回: O( K$ m- ~4 z8 N7 K& |/ u
    
68.                      valueintree = tree_nodevalue(n);
    3 m% A# c& @5 h6 K
69.                      nodeintree = tree_nodename(n);+ t9 q) v; H' T  [
    
70.                      break;
    & I' r# A# F3 ?
71.               end! m4 H, g7 m% g4 T# m
    
72. 
    $ R% N% N6 ~- n9 n, g+ d
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    8 M: S% w: F9 P; X. K
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈2 b$ X; F& Y, U
    
75.                      stack_ptr = stack_ptr + 1;
    + ^8 X* z( L# m. L4 M
76.                      m = tree_nodeson(n);; T: x3 i/ b* i2 J, `
    
77.                      stack(stack_ptr) = m;
    - ]( J: C' J( _1 e: S8 x
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    + |5 |  n' j8 A* }5 b4 C% E\" o
79.               elseif tree_nodeneighbor(n) ~= 0  q- r8 Q6 ~, [4 N7 P% D
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    % w! p3 w2 k* K1 o3 |9 Z) T$ w
81.                      m = tree_nodeneighbor(n);: N\" \  R+ ~) o# |6 P, U* a8 I! m8 R! {
    
82.                      stack(stack_ptr) = m;
      t  {7 g' J0 c' r7 `/ Z
83.                      nodeinstack(m) = nodeinstack(m) + 1;, G  q. |8 e5 Z9 ~$ H; ^' m
    
84.               else
    / k* F7 _: r$ u! \# s# l9 \) p) l
85.               %再否则，出栈，然后将父亲节点的入栈次数加一5 \* ]3 U! {  k% W; Y
    
86.                      stack_ptr = stack_ptr - 1;+ F* B7 H6 l4 J
    
87.                      m = stack(stack_ptr);8 k8 O\" t3 L6 G- C% p( V
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;& Z4 T+ {& N\" K7 z% j
    
89.               end
    ; q- G9 p% H* Y, |: b) S
90.        end

复制代码