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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   8 N& `; G$ g9 b
2.        tree_nodename：节点名字或序号
     v- B4 w1 m7 F7 V- X: [0 w
3.        tree_nodevalue：节点对应的值
   6 {$ h) S$ ?# h+ {; p: C2 J
4.        tree_nodefather：节点父亲，如果没有父亲，值为空8 z5 I( |) E4 y. d6 t
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   0 V! ]9 F% r+ J1 z5 X2 I) X' C; Z
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
   9 |5 K1 P9 N5 r% {; @8 m- N
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   0 R& H: `9 v; z/ O4 d- u$ B
8.   a- t7 }# Q3 Z( l: g% m. H% ^
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。; E/ V! U2 A& ?2 {
   
10. + [! l, D  ?, Q0 N, K  y
    
11.        %matlab源程序9 @\" G* i# B0 h4 w( `4 @
    
12.        %输入：树的深度、树的广度、搜索的值/ I5 _\" r$ C2 B4 ?
    
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空% B: x9 M& x8 h6 s* T
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    ' K- R8 c( m/ M3 Z- f9 r
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    1 W; @% S% {5 @$ w( q2 t7 a
16.        node_num = 0;
    ; B5 ~7 f% i3 e0 L- l
17.        for n= 0 : (tree_depth-1)
    : H8 T5 ]  j! H* [5 F( z/ m
18.               node_num = node_num + tree_width ^ n;
    % ]  r# C% _4 x3 ]7 }0 w
19.        end
    # ^  v$ n7 o: r% @
20. 
    - W( T+ ?9 s5 l, U4 \\" y- G
21.        %为树的存储空间赋值
    \" C  T' p0 M- O8 C  @7 L. ]+ C
22.        %node name，按照广度优先为节点排号6 Y; W* W) B7 h/ A* g
    
23.        tree_nodename = (1 : node_num);% p0 U/ [3 S2 ~0 M0 w+ F# L9 }
    
24.        %node value6 q0 I( _' S  [* s- f7 T3 S
    
25.        tree_nodevalue = rand(1 : node_num);
    2 m4 J; u( a- Y. f) I) h
26.        %node father and son3 Z! l1 y& D- m0 C
    
27.        tree_nodefather(1) = 0;
    - r8 K7 _6 \  `\" P
28.        tree_nodeson = zeros(1, node_num);
    ' y- p% p0 d+ D' C1 ]+ \
29.        n = 2;
      r9 |* U( F5 {  ^4 h' Q- h
30.        k = 1;
    , ?& D( r- T* x: A1 H
31.        while n <= node_num4 Z+ y! P2 A( j, j! }6 M8 M$ o\" J
    
32.               for m = 1 : tree_width
    % ]2 b  A, F# V4 s- ?( Y
33.                      tree_nodefather(n) = k;$ e% a1 n; w- d5 {3 q3 ~% q
    
34.                      if m==1
    , R8 _+ C2 i) q$ v) D$ S0 I! ^! |
35.                             tree_nodeson(k) = n;
      D2 v* o; o1 g) t) p/ v
36.                      end9 M! l7 B\" `0 l: ~6 T: h
    
37.                      n = n + 1;
    ' Z+ L% X- ~* p! ]
38.               end
    & b4 h! {- e3 T/ c. C; q6 i1 S
39.               k = k + 1;
    $ q2 h2 H% b) _: `2 c\" z: h
40.        end
    ! g$ L  W: Y; E9 F\" c5 d2 i0 ]
41.        %node neighbor/ U- R2 E1 ?1 K2 F
    
42.        tree_nodeneighbor(1) = 0;
    & [1 K) M. k( N$ N
43.        n = 2;
    / x\" t: E4 h' \) C% q$ D) U
44.        while n <= node_num# z- C2 D6 D! e. {/ W& Q. V
    
45.               for m = 1 : tree_width3 e' S. f: B' i. l$ J+ y
    
46.                      if m ==tree_width$ T9 b# C2 N) H/ ?7 N8 B5 D
    
47.                             tree_nodeneighbor(n) = 0;6 N6 B2 G3 j# F9 l
    
48.                      else
      t/ W6 _9 Z& s% j0 C) B
49.                             tree_nodeneighbor(n) = n + 1;5 r( |1 _4 s/ @8 _1 C! i/ M6 F
    
50.                      end
    7 H. l9 U7 [7 u
51.                      n = n + 1;
    ' [+ y( n1 D* ]0 j  W# f9 L- }9 v
52.               end
    ; C$ r9 M' j/ j4 {$ G
53.        end+ D5 i: k! e# h
    
54. 
    9 r\" {3 p4 H, r1 v0 U$ t
55.        %下面是有效程序段，用栈实现' b\" i1 j; `! M0 V6 x8 x; R3 M
    
56.        stack = zeros(1, tree_depth);* _/ Y0 M+ F! F; C
    
57.        nodeinstack = zeros(1, node_num);6 F1 z( N* F- b& i6 {\" g% b
    
58.        stack_ptr = 1;7 r% t- `$ ]4 c; w% ?
    
59.        stack(1) = 1;
      @' m6 f\" H0 e! `; M% ~8 S
60.        nodeinstack(1) = 1;% \$ |$ K3 T1 Y7 q: F
    
61.        valueintree = seek_value;
    - i6 _: W3 v( T0 ^; O% d2 O% B
62.        nodeintree = 0;
    6 j% g& y  `% M* J0 z( S6 Q
63. 
    # R0 O9 M- J: S+ g/ c
64.        while stack_ptr > 0
    % A4 g2 u) Y4 D' m; z
65.               n = stack(stack_ptr);
    % L  {, `\" H+ G& M
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3\" d\" c/ _7 y7 l0 x\" y
    
67.               %如果搜索到值，返回, y5 `# E# ~2 B$ O* H1 N
    
68.                      valueintree = tree_nodevalue(n);9 T3 P1 V3 K, z7 q& h# h
    
69.                      nodeintree = tree_nodename(n);
    1 d7 F* X1 V2 \, x9 X
70.                      break;
    . v  D6 c8 ?6 F5 H! M6 l* n
71.               end
    3 s  J4 J4 z2 i' a% ?+ J
72. 
    ; C6 W, K! W8 j1 \2 L\" t
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    ( b9 Y0 m\" B; {; X8 T
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
      n6 Z' H% ~  D2 y2 ~- s
75.                      stack_ptr = stack_ptr + 1;
    0 _& G2 ~' e& d9 e5 E9 ]) s: o% c
76.                      m = tree_nodeson(n);
    ' q\" Z7 e8 L! U/ V7 W$ m# r
77.                      stack(stack_ptr) = m;
    5 d9 I% }9 h* I2 b; y5 y
78.                      nodeinstack(m) = nodeinstack(m) + 1;' ?\" G3 }! I% _9 K3 @% \
    
79.               elseif tree_nodeneighbor(n) ~= 0
    * [0 n/ d+ _; ?# g% a# L7 ~+ p
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈$ x8 q0 t\" Y* j\" y. d8 i3 Z+ ?
    
81.                      m = tree_nodeneighbor(n);2 Z3 A9 b' [. [1 F! g& u# u
    
82.                      stack(stack_ptr) = m;1 R5 X9 M3 b& m1 M( b) i\" m2 s% Y
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    8 E& C; ?/ ?- z% }
84.               else
    7 W6 z7 C- l- d2 ~- k
85.               %再否则，出栈，然后将父亲节点的入栈次数加一  F% s% i5 u3 y
    
86.                      stack_ptr = stack_ptr - 1;+ l% H) S8 m8 P' R5 M$ m+ w
    
87.                      m = stack(stack_ptr);
    9 K2 g# F( V& A
88.                      nodeinstack(m) = nodeinstack(m) + 1;
    \" F4 F, j* T\" D- a6 [# O$ ]
89.               end
    - y1 b+ e1 h; F9 n& K7 O, V
90.        end

复制代码