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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   ' a- F\" [' R2 S
2.        tree_nodename：节点名字或序号
   ( p: k' c0 R7 }
3.        tree_nodevalue：节点对应的值
   1 M0 F3 g$ f! A+ ^8 T1 u
4.        tree_nodefather：节点父亲，如果没有父亲，值为空. K$ ?; A$ ]2 c! E( l4 }
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   * h2 w2 s9 A& U( J, n
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空) ~3 ?) C! `8 K* a. e6 G% y; C' E
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。/ M* I6 c9 h. B' S9 B
   
8. # R) d$ m8 k) d
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。: x# P+ n4 b& n+ p5 e& t- P6 d2 g
   
10. 6 ^. n6 g/ X0 j0 y, C, N& a* w
    
11.        %matlab源程序8 c8 L6 F2 \  y5 Q6 ?% T, b' ]
    
12.        %输入：树的深度、树的广度、搜索的值
    & T1 a! D6 D2 j% D
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    ) M7 D- X, `/ \7 R1 H
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)# z/ c% U% o) s  O3 F( q3 H. }: O
    
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    9 t- o. P2 p0 @+ v4 B; R5 _! h3 p
16.        node_num = 0;
    \" g, M8 H' ]2 c: P
17.        for n= 0 : (tree_depth-1)% |! B. D) P, ^* S/ @
    
18.               node_num = node_num + tree_width ^ n;
    \" U1 U' G9 b3 C7 G( s# V$ ?
19.        end( b; ^* ~/ H% K& S& X
    
20. 
    2 e/ U5 Z: i9 p6 f
21.        %为树的存储空间赋值3 {3 K) R$ |/ S5 V' T/ m9 x
    
22.        %node name，按照广度优先为节点排号6 J. ]8 O( p% \\" ^6 c, W) z  y( p
    
23.        tree_nodename = (1 : node_num);5 U' }0 B: v+ v
    
24.        %node value
    . d) r1 |/ J# k' s1 W( T- o  }# w
25.        tree_nodevalue = rand(1 : node_num);# p, @+ N\" p0 N: w3 ^: P$ A
    
26.        %node father and son  O$ e: g* t. w8 I
    
27.        tree_nodefather(1) = 0;, O. j1 b! i% a6 `1 g
    
28.        tree_nodeson = zeros(1, node_num);# |' A8 k9 P2 r
    
29.        n = 2;8 Q9 C. @$ Y1 c. \\" ^
    
30.        k = 1;
    # j% \5 _2 K' S\" H$ Q
31.        while n <= node_num( K+ N0 a- {# R7 u; T  o% v
    
32.               for m = 1 : tree_width/ u\" B6 a8 b+ ~( l
    
33.                      tree_nodefather(n) = k;
    \" ^! m( @' }7 m& m9 @
34.                      if m==16 B( y% Z; X+ B% k& }6 Y) ^. X\" b
    
35.                             tree_nodeson(k) = n;
    $ s' K+ _( U, R( {( O' }. F& y# v
36.                      end4 D0 z  q2 ?3 L6 D/ D. r% _- ]
    
37.                      n = n + 1;: q4 L* s3 D  {
    
38.               end
    4 b2 l5 ]  |2 |. s( \8 P1 I. @
39.               k = k + 1;% b7 G; }) Y& H
    
40.        end
    1 X7 S. g+ l4 V2 r9 H+ W/ m
41.        %node neighbor
    / }3 p. x: _# G8 P9 V$ U
42.        tree_nodeneighbor(1) = 0;+ a. {/ R4 n1 L4 B' {
    
43.        n = 2;
    % W% q' Q2 H4 N* g\" ^* c
44.        while n <= node_num
    0 m* _+ c/ g: \; m3 ?9 }\" [& X6 Z
45.               for m = 1 : tree_width& h* }/ v5 |. X+ z
    
46.                      if m ==tree_width$ `% F% D5 v4 ?& [+ t
    
47.                             tree_nodeneighbor(n) = 0;\" J& T' q  S5 y1 U9 e# t; m$ ^
    
48.                      else4 r: F* H\" U& y/ `$ |0 _% H
    
49.                             tree_nodeneighbor(n) = n + 1;, D6 z\" h; s3 w1 ?1 R
    
50.                      end
    - V& a1 b# f8 k9 B, z' j6 W
51.                      n = n + 1;7 o; c' w( l; |5 B# e
    
52.               end9 R( g5 g+ V\" Z
    
53.        end
    $ q3 `% Q, h0 _\" Y. Y+ |  X; s
54. 
    \" b  m  n+ c' Q
55.        %下面是有效程序段，用栈实现
    2 ]& X* a$ D# @, ^
56.        stack = zeros(1, tree_depth);
    & ~6 V- R+ Y* H+ d- I3 b* d5 ~
57.        nodeinstack = zeros(1, node_num);( J! Q\" W1 A7 g\" I\" X8 a5 l' s
    
58.        stack_ptr = 1;
    9 P; b9 x5 i, N; y
59.        stack(1) = 1;
    $ l/ ?; ^( q* h& L
60.        nodeinstack(1) = 1;& ^9 F% B* Y0 R2 X\" @6 [* H
    
61.        valueintree = seek_value;; R0 S6 B. k2 m7 ~# B& `
    
62.        nodeintree = 0;
    5 W' c( O& E9 u% a. |# V
63. 
    5 |3 W8 @+ J8 e
64.        while stack_ptr > 0
    \" P8 F$ r3 ^) u! k7 a$ f, G5 R
65.               n = stack(stack_ptr);
    , u5 a2 ~+ T) e2 [. T9 ]' r( \
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    ! `; D, G& {2 \* _$ \) A  l
67.               %如果搜索到值，返回
    % g. C* V% r8 d9 p0 B3 }; x
68.                      valueintree = tree_nodevalue(n);
    5 m* `# X% q3 K  J1 V
69.                      nodeintree = tree_nodename(n);
    $ j! V0 w* _\" _
70.                      break;
    2 H  z7 v) \2 x! {2 w# E+ ]8 J
71.               end# }' b) R/ Q* g1 S! V5 Q
    
72. 
    ( u+ A+ [8 V3 A2 u* d
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    ' K0 C8 a* D/ L+ Z/ S. F1 {+ ]8 R
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈, e+ j% d5 u: {! V
    
75.                      stack_ptr = stack_ptr + 1;
    9 d4 `9 W- s% p- b
76.                      m = tree_nodeson(n);
    / S) S% z6 D+ g+ K9 M, S& T
77.                      stack(stack_ptr) = m;
    0 z; s6 o3 @5 t& Q: Z+ {
78.                      nodeinstack(m) = nodeinstack(m) + 1;% E! x  @$ Z* I! B
    
79.               elseif tree_nodeneighbor(n) ~= 0
    0 P: E4 q\" \5 A4 b3 d( A
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
      o+ E8 s7 C& K6 Q( {
81.                      m = tree_nodeneighbor(n);
    1 N& [' x3 m3 k' `; h7 }3 i7 n. u
82.                      stack(stack_ptr) = m;
    & O4 C' I! S7 `- r5 f
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    4 w, K$ E0 Z0 R; r
84.               else6 _9 `- e: \4 b9 T5 C4 r4 _
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一9 T7 w\" L) [1 b2 [
    
86.                      stack_ptr = stack_ptr - 1;6 z0 x' H) H% n9 H$ x
    
87.                      m = stack(stack_ptr);- }# Y; }8 @1 E  O
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;
    ; _0 O8 h- J3 x0 r% d; k
89.               end
    ! ?; f- s/ d2 G8 _
90.        end

复制代码