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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：. p2 o# x, }& J: h
   
2.        tree_nodename：节点名字或序号
   ' s8 z- o& m' z/ R
3.        tree_nodevalue：节点对应的值0 W6 F\" A. l  o
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   3 J0 a2 D+ n0 i2 t6 [: i4 |$ ~, t
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   7 X' n  n) q8 v( w7 g! N) G
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空- n+ Z6 l( c/ M* h/ W* d7 ~
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   5 F- `6 v. |\" a0 X- \
8. 3 M$ ]& G\" }: q( }% S; e0 h
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。\" s3 H2 A5 x4 q0 [2 n2 ~) f
   
10. 1 G' W4 t- k( M
    
11.        %matlab源程序
    7 m! p6 q! K4 P
12.        %输入：树的深度、树的广度、搜索的值
    ; p8 M3 c2 I6 O1 Q! F! m
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    ' J+ L) x/ O4 }7 T\" a/ a
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)1 D% u6 e! `  u( e. R
    
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    ! k5 {9 n3 n( k/ M
16.        node_num = 0;
    0 o! }0 y7 b& E9 l* L
17.        for n= 0 : (tree_depth-1)
    * v- R8 @6 n% E- N
18.               node_num = node_num + tree_width ^ n;# d; a0 ?3 c2 A. \3 D( K
    
19.        end
    5 r: B3 i( F; v2 K/ D
20. \" |3 R5 b0 O/ o
    
21.        %为树的存储空间赋值
    9 e3 g+ Q( {9 b' b* K8 A, p
22.        %node name，按照广度优先为节点排号
      Q\" ~! B. h, k/ L$ f, b
23.        tree_nodename = (1 : node_num);
      H; v6 h) S/ d& j, k  M# n
24.        %node value
      J\" m\" J! H( m* V/ l: Y9 b4 V
25.        tree_nodevalue = rand(1 : node_num);, j, h. J1 X7 V$ w* l9 B0 }* S
    
26.        %node father and son
    ( _1 h; o2 m7 K6 ^! I$ d! t3 L
27.        tree_nodefather(1) = 0;1 Q4 F6 f* J: W) Q+ f0 z1 e& K
    
28.        tree_nodeson = zeros(1, node_num);. j/ `! f% i# A
    
29.        n = 2;\" i8 B( X: P( z
    
30.        k = 1;2 w- Z9 T1 c6 B4 c  a5 p, X$ u9 T, E6 R
    
31.        while n <= node_num3 W0 M3 z# E/ K& f& P
    
32.               for m = 1 : tree_width
    3 p0 @% R( M, o/ C0 ?
33.                      tree_nodefather(n) = k;) v3 |5 A: ]( z% z& p. e7 K
    
34.                      if m==1, `3 p0 ~9 c0 e0 O
    
35.                             tree_nodeson(k) = n;
    2 l/ P$ m1 J$ t) t
36.                      end3 E9 `+ f& F7 m\" V' u1 E( O
    
37.                      n = n + 1;4 I& U4 _6 O$ p' }* ?7 E2 A
    
38.               end
    \" E. C: a+ x0 t1 s) R\" }
39.               k = k + 1;6 @) g; P1 w# w1 M, x, @
    
40.        end
    ) j9 [6 R1 R5 T  ?5 t: X
41.        %node neighbor
    , q8 {) Z; H8 u: }& R
42.        tree_nodeneighbor(1) = 0;; t5 y% E* Y2 j( s+ v$ X* B
    
43.        n = 2;. x4 Z7 O9 H8 @% C
    
44.        while n <= node_num2 x( t% M) K, }3 ^+ [8 ^
    
45.               for m = 1 : tree_width
    * @5 Y3 l! N/ \! o! z
46.                      if m ==tree_width0 _- f5 o- m' y; ?; Y, }' [
    
47.                             tree_nodeneighbor(n) = 0;
    9 l2 A5 W- K, M8 E' a) G- q
48.                      else
    2 E* p2 V2 g2 a. n
49.                             tree_nodeneighbor(n) = n + 1;
    * P, S2 ~8 O# |1 U\" m# |; ~2 O
50.                      end
    ' J3 a( K) j; y
51.                      n = n + 1;
    5 U( K& f0 L- d3 Y8 W7 J3 ^% i* ^3 X
52.               end& W- G8 V2 D( S' p) u7 K
    
53.        end
    . N0 }- z\" m7 S- {/ q
54. 1 \9 C9 l8 P; \% y, a7 R) `7 j/ u
    
55.        %下面是有效程序段，用栈实现2 L7 ]7 z0 ?6 J* o3 V! \
    
56.        stack = zeros(1, tree_depth);\" A/ Z! a. P( K! J
    
57.        nodeinstack = zeros(1, node_num);
    1 I& f# }  K5 S/ x$ S7 M' W
58.        stack_ptr = 1;$ U6 h8 V% c2 ~6 h  ?9 f
    
59.        stack(1) = 1;
    8 d\" q! A/ c, v8 W
60.        nodeinstack(1) = 1;
    & N8 _\" c+ z! N; D6 |4 N0 f
61.        valueintree = seek_value;
    ( l1 y3 H4 ^( Z& q
62.        nodeintree = 0;
    ) l8 l& C\" R: o. S, I4 i# r1 y
63. ; R3 @5 a7 F\" L( \6 a! y7 E
    
64.        while stack_ptr > 0
    ; y/ ]' ?& ^  D) V$ y- x+ t( B6 q
65.               n = stack(stack_ptr);/ N& _! p+ _2 ]  F% g( e
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3; m# Y: x: M/ s' [6 |# q5 Z/ b
    
67.               %如果搜索到值，返回
    0 H% ]; {6 p5 d9 E3 F# R
68.                      valueintree = tree_nodevalue(n);* p3 m. F! e, G3 ~: q! F
    
69.                      nodeintree = tree_nodename(n);
    $ D- P$ b  I* e' f3 z
70.                      break;, s! f, v) ?5 \  T5 W
    
71.               end# V  f\" l/ h' J  B
    
72. 
    : u; H8 ?7 [1 y+ J
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1! `9 {5 N! L- B/ a; N, `& a3 Q! Z
    
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    1 R% x$ [1 X\" Y( q/ ~- X
75.                      stack_ptr = stack_ptr + 1;
    6 q* u# N\" E+ D% p0 X' l. u
76.                      m = tree_nodeson(n);3 k% n8 ^6 B  W# W9 Q+ D
    
77.                      stack(stack_ptr) = m;# t+ G5 \& o! ~\" p
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    * P+ _7 u4 B0 m) V& q! }
79.               elseif tree_nodeneighbor(n) ~= 01 p- f& f\" D! Y6 E& e
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    : W: o4 S\" @+ A7 f& l8 e
81.                      m = tree_nodeneighbor(n);
    $ n) ~* Q8 z3 n7 P2 H
82.                      stack(stack_ptr) = m;- g\" g' x- i) ^, J+ R9 j
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    9 M; B. g# J9 d/ T0 l: u
84.               else7 K: q6 E! i$ @$ ]1 [
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一5 G4 W) _0 Q5 [; e( G, g
    
86.                      stack_ptr = stack_ptr - 1;& X% e* t. Q9 g5 c4 ]  I+ P* z
    
87.                      m = stack(stack_ptr);% D: F& x4 r9 c5 a( ?) o
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;8 y! C2 [+ d# s9 b
    
89.               end* I# n7 H6 T\" N0 ?8 Y+ ^! A
    
90.        end

复制代码