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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   - U# J% e0 Y0 N) |0 L' _$ G7 Z) B
2.        tree_nodename：节点名字或序号
   + A3 y4 z. W4 S; }
3.        tree_nodevalue：节点对应的值
   * L. d4 h, E) z
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   + I# Y, a1 q# \; I
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空5 Q) X! u+ N7 l; j5 K2 c8 R2 c
   
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空  G; u, H/ f) E1 w, D' K4 o/ G  J
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。: X& ~% v\" `0 h
   
8. - i( c8 [3 y( ~6 X+ i3 g\" ^
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。4 d' Q, f: X) _1 {0 Z9 A+ I7 a
   
10. $ q6 s' Z. @% C8 Y5 U0 Q
    
11.        %matlab源程序
    9 @& l# C6 R0 U( z2 f
12.        %输入：树的深度、树的广度、搜索的值
    ) t( I5 g6 a, C\" b9 X) r
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    ; J) X7 d/ f; v0 e* x
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)\" S% `# x0 y1 i) k
    
15.        %根据树的深度、节点的儿子数量计算树总的节点个数\" X  k$ E* _5 f* B6 z\" {
    
16.        node_num = 0;
    4 a$ }1 }3 h7 O0 G- q
17.        for n= 0 : (tree_depth-1)
    , @\" n1 j. W) Y
18.               node_num = node_num + tree_width ^ n;' u( S+ s3 S2 j
    
19.        end/ s4 [0 b\" ^7 ~) A! v
    
20. 
    9 S  |\" o9 H5 ?# Z5 v
21.        %为树的存储空间赋值
    $ m\" f' R! E& N
22.        %node name，按照广度优先为节点排号
    8 {5 p7 @2 j, K\" w& a+ t
23.        tree_nodename = (1 : node_num);
    * Y8 y, Y$ Q3 _5 z$ F\" i* V- l
24.        %node value3 L) c7 l; ^) f\" @% J3 q
    
25.        tree_nodevalue = rand(1 : node_num);
    ' a, Y4 r, ~# Z( d
26.        %node father and son
    # N& N: X\" b) R, f; Y7 [
27.        tree_nodefather(1) = 0;
    4 K) s3 ?. b% Q8 v1 j8 T: }
28.        tree_nodeson = zeros(1, node_num);
    1 X$ r; V) r% R3 U! V
29.        n = 2;
    $ G, K* H2 Y9 v3 f8 H; x
30.        k = 1;4 ~( S) x: }$ L4 H
    
31.        while n <= node_num9 Y/ ?7 k$ K% m
    
32.               for m = 1 : tree_width, ]9 k! ~; o7 x+ h2 ?/ T4 H
    
33.                      tree_nodefather(n) = k;
    1 w4 w0 l/ I4 z  l) Q$ [
34.                      if m==13 m* b/ W2 A  s% |( ?: ?0 B+ W
    
35.                             tree_nodeson(k) = n;
    ! q* O! ^3 x6 C+ [6 M
36.                      end
    * G6 K! q  u7 x9 u6 d6 n) L
37.                      n = n + 1;
    \" D6 E8 G3 M9 Z' B  |
38.               end1 ]# E  l  v# l6 ^( t' e# M- Y
    
39.               k = k + 1;9 v' |) ?: r9 {  v+ y4 M6 N
    
40.        end0 ^& K( q* ~  c; f! Q) N8 s
    
41.        %node neighbor! C8 s. X( S& U\" G, a5 n5 ]2 E
    
42.        tree_nodeneighbor(1) = 0;' I  I' G7 ]+ Z
    
43.        n = 2;
      o\" |& ~7 u: S; l* `
44.        while n <= node_num) A6 h, h% N5 k. \# q
    
45.               for m = 1 : tree_width( H7 h4 E  @: V( C
    
46.                      if m ==tree_width
    6 M6 k8 g4 C3 Y, R9 C
47.                             tree_nodeneighbor(n) = 0;
    8 U3 h7 G' z% j. c* W# d
48.                      else
    * h  h' U. a+ }
49.                             tree_nodeneighbor(n) = n + 1;
    ; I2 Z\" w- x4 D# B0 E. x1 t  `\" b
50.                      end
    ) W9 e3 F7 s2 g7 m2 @: K
51.                      n = n + 1;
    * o+ e, t% d5 ^* ]8 W+ E
52.               end9 b6 @# }, S3 f
    
53.        end
      s! e9 l7 _1 |7 ]# v: u
54. 
      }0 ^; Z5 f9 t  k
55.        %下面是有效程序段，用栈实现
    ' I. i& R6 U+ H1 z2 v/ j
56.        stack = zeros(1, tree_depth);
    % }3 g6 p, J9 t/ b- f& e  e: M
57.        nodeinstack = zeros(1, node_num);$ _% S6 N& x% w: k8 |3 @
    
58.        stack_ptr = 1;
    5 G' u1 [+ R& x7 w) s
59.        stack(1) = 1;
    / P& X6 ]% n/ x
60.        nodeinstack(1) = 1;. p& w5 ~1 P+ u
    
61.        valueintree = seek_value;5 m( U# e& z4 T9 y8 {
    
62.        nodeintree = 0;
    8 s7 V: t0 X8 l- |6 r2 d2 ?
63. 
    & z$ H+ n' i  s\" ^, e# [/ A! }. @
64.        while stack_ptr > 0. ]7 n- F9 k9 ~. @
    
65.               n = stack(stack_ptr);
    % X- @, d- p, t2 H' o) x, s
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3( y; q. q& B& G\" e
    
67.               %如果搜索到值，返回
    . q: v6 P9 E4 A7 q
68.                      valueintree = tree_nodevalue(n);: i' H1 w* @5 t, K0 ]
    
69.                      nodeintree = tree_nodename(n);: b; T9 h6 ^. ]\" w
    
70.                      break;4 S6 O7 k\" E8 K2 b
    
71.               end6 y+ f. g/ ]0 S( `2 B* ?. L: Y
    
72. 
    2 b; a2 C! k( k( O, f$ X
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    ! I9 A. ^7 |1 G1 B9 T
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    \" E2 o4 O* A# z  U* K$ x; w
75.                      stack_ptr = stack_ptr + 1;
    ; u5 S5 S' a* ^
76.                      m = tree_nodeson(n);
    5 i/ j( X9 _& o& H- }' x
77.                      stack(stack_ptr) = m;# n* C\" O. ?3 t% F
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    . L) k$ @% J  U, u0 d# f& _4 y' \
79.               elseif tree_nodeneighbor(n) ~= 0
    0 ?. u# f9 o; Q
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    8 p6 q! H; N: I\" H- d
81.                      m = tree_nodeneighbor(n);* A  u( q0 V* N6 D) K; {- w) H
    
82.                      stack(stack_ptr) = m;2 U+ L# |6 t6 J7 B
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;. W: v6 Q) V) F# b+ `0 ~% ?
    
84.               else
    . d\" g& O0 s9 J  U
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    9 B* Y. S% E9 c4 u
86.                      stack_ptr = stack_ptr - 1;
    5 e1 b0 r# H: N
87.                      m = stack(stack_ptr);
    ) H, ?3 s4 q3 z\" W, c% t, B
88.                      nodeinstack(m) = nodeinstack(m) + 1;2 |' [$ z, W( G! G* |2 U
    
89.               end
    . w% ~, d# U- q, Q: r
90.        end

复制代码