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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：, p0 W3 m6 _5 O2 D7 k5 m6 n) A
   
2.        tree_nodename：节点名字或序号% C. K3 O\" {0 u1 S
   
3.        tree_nodevalue：节点对应的值
   5 _4 f+ h6 |& d  ]% i2 q' J
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   % Y. A\" C% A: }! [2 x4 B
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空6 D. p3 `) S% z5 c! ~  k' ]
   
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空- C$ R) _' e) o1 ?
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   ; F' Q- S! i8 }
8. 3 ~+ Q7 H$ E8 R
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   * P/ E\" @# f$ \4 F, m0 q0 d
10. 
    1 `/ s5 h5 I, }2 P& d  l$ h
11.        %matlab源程序* Q5 R: R\" S: h( b0 z
    
12.        %输入：树的深度、树的广度、搜索的值
      @) N+ Z2 G( b* G\" h+ L, ^
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空2 z  g/ h: K* L& o
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    ! e, E7 K4 B2 |+ e- Q
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    & F* O' B) j1 f* k6 n# o
16.        node_num = 0;+ X, [2 U' C8 `' n
    
17.        for n= 0 : (tree_depth-1)4 Q, i8 o: y  P) E
    
18.               node_num = node_num + tree_width ^ n;7 d7 m9 Q1 O+ I1 r0 g
    
19.        end
    ! }\" A1 x0 _8 c4 r* I% j\" @
20. 
    5 {: Q# ?# S, X6 W- ]1 @; `, B
21.        %为树的存储空间赋值
    & K/ K/ T3 D4 H* T( `0 s
22.        %node name，按照广度优先为节点排号3 Y4 m3 G) ]+ I) l, L  k
    
23.        tree_nodename = (1 : node_num);
    0 ]+ ^1 c, N) S, @0 {9 r: c
24.        %node value\" k- V3 ?: T( l3 y. e& P
    
25.        tree_nodevalue = rand(1 : node_num);( L$ b& g7 G3 V, h5 \2 ~6 x, y& R
    
26.        %node father and son
    : k4 N! [) k! T0 Z; z; M5 A* R
27.        tree_nodefather(1) = 0;' X; s: v+ R/ c- p4 m
    
28.        tree_nodeson = zeros(1, node_num);
    - B, `+ ]! I2 N5 y
29.        n = 2;1 [4 h( f- B\" v7 j5 u
    
30.        k = 1;% ]6 s; t! J4 l0 d2 }
    
31.        while n <= node_num4 o5 P+ e$ Y, s4 V- C+ r$ H
    
32.               for m = 1 : tree_width
    : n3 v- `  h4 |# {
33.                      tree_nodefather(n) = k;$ T$ z# I0 g/ S& H2 X/ \: ^
    
34.                      if m==1: ?. l( Z1 Z8 J: C& A) ~
    
35.                             tree_nodeson(k) = n;
    ! U0 ?% o9 [0 p3 y! c- J
36.                      end
    + {2 W; X3 y- n. q! l) Z\" B
37.                      n = n + 1;, R  ]* }\" f& a
    
38.               end5 {  Z! n( }' j% `; d7 V# N5 T; o
    
39.               k = k + 1;
    , C\" L: N  r* x  y2 D) B. T  x% T+ U
40.        end1 x, W. e( ]* s: [- ~) V- g' l
    
41.        %node neighbor- b: y5 @  x7 n( P$ P
    
42.        tree_nodeneighbor(1) = 0;
    \" S8 f: ~2 H' t( h+ J2 s1 u' ^+ H; e# Z
43.        n = 2;
    0 f7 C8 w& D4 s
44.        while n <= node_num
    6 o+ U' h9 f; i' J' e% E
45.               for m = 1 : tree_width: K! ?, Q/ M+ I% X+ D
    
46.                      if m ==tree_width
    + ~; M' n5 U/ p( x1 Q0 d, t( E
47.                             tree_nodeneighbor(n) = 0;' @: Z% g0 R& k' p1 _
    
48.                      else\" Z6 \: Z( j8 f% i
    
49.                             tree_nodeneighbor(n) = n + 1;
    6 _  S  E3 y5 M$ S0 y
50.                      end/ [% \6 j/ S9 ^! D# \2 }
    
51.                      n = n + 1;
    0 r- M+ ]- g/ w# K$ J
52.               end0 d3 C& A+ f( _+ F4 u$ R* A
    
53.        end
    ' P  _% |. M# ?1 T% q: \+ R
54. : O+ O# z4 Y3 R- X0 z
    
55.        %下面是有效程序段，用栈实现
    6 U, [$ X5 u/ s) q% ^
56.        stack = zeros(1, tree_depth);
    ! [8 e\" b2 n5 g) w  c
57.        nodeinstack = zeros(1, node_num);4 v\" E& F+ G. O3 z# u; x\" ]# r
    
58.        stack_ptr = 1;\" y4 R1 L) B8 z* S$ e, E
    
59.        stack(1) = 1;\" q) F; E7 X- G' x! y
    
60.        nodeinstack(1) = 1;) _! _2 C+ Y+ p: @5 `6 \6 R4 E
    
61.        valueintree = seek_value;\" e6 T. V4 A# P
    
62.        nodeintree = 0;+ q( ^- q0 H2 O1 T% O
    
63. 
    : c; f0 y3 f/ l
64.        while stack_ptr > 0
    9 \% e+ U  e; t5 w4 a  l5 [\" W
65.               n = stack(stack_ptr);
    & Y5 Y5 X* \5 c* v/ F
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3\" E\" S8 K, `8 E5 W7 |
    
67.               %如果搜索到值，返回
      b7 Z7 U) ~! C
68.                      valueintree = tree_nodevalue(n);- L$ V7 q$ ~* p$ m/ d. G
    
69.                      nodeintree = tree_nodename(n);: e2 [3 c$ I) |) K+ u
    
70.                      break;& P# R\" C0 t6 S6 d- a+ u
    
71.               end
    8 N5 _: @\" Q: o1 J+ G2 I3 R
72. 
    5 J# ]' ~8 g8 Z3 ]\" J
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 15 w/ J. o; M  D$ V$ u% W
    
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈( k1 A0 m- M% b$ M2 Q0 ]\" {
    
75.                      stack_ptr = stack_ptr + 1;
    : q8 k$ d# F4 r/ R# k3 [
76.                      m = tree_nodeson(n);
      g/ V6 |2 Y9 W0 ~3 v
77.                      stack(stack_ptr) = m;7 J& K. z9 k+ a4 u) f# F' h( s4 o* m
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    3 z& U% j; f0 s7 m2 [  A
79.               elseif tree_nodeneighbor(n) ~= 0( x+ q9 Q/ L5 y7 [2 _+ I
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈/ k$ ?7 H. {, @% w; {
    
81.                      m = tree_nodeneighbor(n);
    ) d: @; Q* u) s6 |
82.                      stack(stack_ptr) = m;
    5 M' Q5 e\" i4 ?( V  C
83.                      nodeinstack(m) = nodeinstack(m) + 1;# M+ Z6 J7 v# }0 u& {
    
84.               else+ J5 Y) v( ~- Z) e# v* q/ U
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    ) _. [- N) |# p& L( n, x
86.                      stack_ptr = stack_ptr - 1;
    2 Y2 }5 q9 p# n1 y9 V
87.                      m = stack(stack_ptr);
    4 b/ y) z2 t8 h* p\" \
88.                      nodeinstack(m) = nodeinstack(m) + 1;+ H5 p' w+ G, J
    
89.               end
    ' q- W) M2 z' N4 O
90.        end

复制代码