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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：' @- V- h; ]; j8 E
   
2.        tree_nodename：节点名字或序号
   , D* p; ^1 C6 X
3.        tree_nodevalue：节点对应的值
   ( S5 H/ N2 {' A' F2 q$ ~) A7 o
4.        tree_nodefather：节点父亲，如果没有父亲，值为空! j% f3 d. i- x8 H; y9 B4 o. v, ^0 }
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   , z  S9 K% a0 n2 B
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空, G1 ?; u6 H\" F9 V9 l: w\" e) n( T
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。3 _* W+ Z8 Y\" R' ~* G
   
8. 
   3 }6 D# X8 w* q; D
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。4 {5 H6 z+ O+ @. H
   
10. % |+ y/ P' S3 L
    
11.        %matlab源程序. E7 g* F+ t\" B\" i6 J3 y
    
12.        %输入：树的深度、树的广度、搜索的值
    3 V) v$ y. U' J' X' Y  S, [$ u
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空! P/ B9 Z& \) `4 O\" y% |; d0 @! P0 v
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    3 F  l. t  o* M# ]
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    / W4 R5 x. ?/ e1 i( p/ E- G
16.        node_num = 0;
    % E# S) [( Q7 p; c4 b
17.        for n= 0 : (tree_depth-1)
    9 L2 P+ l/ a' z1 Q8 d- _9 X/ p  G
18.               node_num = node_num + tree_width ^ n;( \1 i& n/ e  c
    
19.        end
    % g# e1 ~# `\" o! b
20. 
    . g. k) r5 P2 {- S% a7 z1 w) H
21.        %为树的存储空间赋值
    5 m8 Q+ K/ D# x\" \* L. F6 ~
22.        %node name，按照广度优先为节点排号
    ) |' r3 c4 c6 C& C3 g% x3 K
23.        tree_nodename = (1 : node_num);7 a! H5 ]9 z8 Y, V% g# H
    
24.        %node value
    , V) t3 z7 m/ k9 \3 P
25.        tree_nodevalue = rand(1 : node_num);\" w: P+ D& S8 W; {9 A
    
26.        %node father and son
    / w' i* M, t1 J
27.        tree_nodefather(1) = 0;
    * p1 Q5 t, w3 G
28.        tree_nodeson = zeros(1, node_num);
    ) r) p/ ?) j7 V# N3 c3 |) D  [' i
29.        n = 2;
    : l1 ?* q! C6 W7 n0 N
30.        k = 1;
    1 @/ s& U6 K; V1 x/ R
31.        while n <= node_num2 y' C  d' ]\" ~; p2 _
    
32.               for m = 1 : tree_width\" S) g\" v; B1 w' M* g$ B
    
33.                      tree_nodefather(n) = k;0 S1 }! P7 ^& G/ z2 K
    
34.                      if m==12 J2 B  _7 C9 N, Q5 f2 L0 x: |: Y( v
    
35.                             tree_nodeson(k) = n;+ T) }) N8 k/ v, e$ ^
    
36.                      end' I2 M' Y; o' G
    
37.                      n = n + 1;
      o+ P( H2 C/ D( m& d/ b7 m\" ?  E
38.               end& d$ \4 Y6 D3 ?. z8 a4 K
    
39.               k = k + 1;3 s2 \* d; p! z5 F8 v4 F' v, @\" g
    
40.        end
    6 N9 n- A* F+ w; p0 _7 ?6 b
41.        %node neighbor
    2 c5 }; e9 b3 E. g
42.        tree_nodeneighbor(1) = 0;
    0 C1 N# f4 |; B; y* g
43.        n = 2;: Z' Z( d1 u; O) g4 P- F0 u! T5 T! \
    
44.        while n <= node_num! l! J) P3 l1 K5 q2 h
    
45.               for m = 1 : tree_width8 L; V\" m5 H/ G4 p* y
    
46.                      if m ==tree_width3 Q8 o0 L9 h0 w1 ~. @
    
47.                             tree_nodeneighbor(n) = 0;
    / a2 h- Y- y9 z0 b& c, ^
48.                      else2 g2 v! v- _$ r
    
49.                             tree_nodeneighbor(n) = n + 1;. g+ H# p7 B. w. A  X
    
50.                      end
    9 P7 q( J. l6 g  {; C6 m
51.                      n = n + 1;. j( B4 Q, @5 R- L/ K6 m7 V) l1 L
    
52.               end3 H# V* v3 R' F
    
53.        end7 Y' N! q: Z/ Z8 j4 K
    
54. ! _9 @! |9 ~; @8 R& @
    
55.        %下面是有效程序段，用栈实现
    # j8 ~1 |\" W3 ~; B3 D& K% m+ r; f
56.        stack = zeros(1, tree_depth);
    + m/ W3 ~& \8 X  ~2 z3 ^! ~
57.        nodeinstack = zeros(1, node_num);
    8 T8 y* J5 C- y. M/ w8 [, b
58.        stack_ptr = 1;
    3 t+ h/ b- X9 Z. N1 ~! |
59.        stack(1) = 1;
    ( R\" J# w% G+ u8 I. Q8 {
60.        nodeinstack(1) = 1;4 G# R! O/ N4 \, b2 z
    
61.        valueintree = seek_value;
    * ^- a  ]+ ^. i' L1 i4 W\" V5 ~. o
62.        nodeintree = 0;' v2 s0 ^+ t3 y\" C# m6 k. m$ ~$ a
    
63. 
    ( J7 U6 Z\" n) x0 [: b( L! e9 W/ c
64.        while stack_ptr > 06 ]; |( K8 _2 d/ J# c; Y
    
65.               n = stack(stack_ptr);1 k% K; _! I1 W) E, I- c* P
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    * f+ P: o. F6 i$ k1 t& i
67.               %如果搜索到值，返回
    : f& h+ j7 j/ x3 m$ m
68.                      valueintree = tree_nodevalue(n);5 Z; C4 s7 b% {' H. I& X
    
69.                      nodeintree = tree_nodename(n);
    % T- s2 j! e  H; `- B, l/ N. x7 N
70.                      break;' ]3 f- [( Q$ M$ v' N% N1 D# ~+ V0 S
    
71.               end
    $ ^' F& z( R6 N; j9 U/ c$ x  a
72. 
    , V  B* h, S; A& Y9 K2 Z0 e4 X. L
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1# ~( v' k! Z+ y/ Z4 v
    
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈: |5 n5 e) J) d: @3 Q
    
75.                      stack_ptr = stack_ptr + 1;
    : B9 K# ]' W\" A8 O\" g- y3 N6 _6 o0 F
76.                      m = tree_nodeson(n);: W$ y2 w. m/ z/ q- h- a
    
77.                      stack(stack_ptr) = m;
      R1 w4 A\" D/ i8 D8 |7 V5 N6 L
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    * L6 {/ h7 a! \9 u! M\" u) ]$ a+ f( F
79.               elseif tree_nodeneighbor(n) ~= 0
    % s# b$ G; G& U1 X8 P1 ~9 e
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    5 k$ ]& k, ?; Q+ X# d: |: @
81.                      m = tree_nodeneighbor(n);
    8 s; y5 d+ b2 J( o
82.                      stack(stack_ptr) = m;5 g. F\" U( J/ |3 ]+ @4 i4 i
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;6 h2 ?& ^0 I/ u3 I: e
    
84.               else
    * X3 [( y5 K0 p
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    0 w) R# s1 ]3 p0 e% d5 V) s- T
86.                      stack_ptr = stack_ptr - 1;
    ! P$ Y7 q- C6 m7 P4 F; ?
87.                      m = stack(stack_ptr);( H1 h/ ~4 f+ B/ H2 z. v, e# P8 p
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;: w* }7 C9 l; S
    
89.               end
    \" g9 z) h  O8 _8 I4 t. V* d
90.        end

复制代码