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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：: Y! x2 |+ L: b; [( f7 g1 V
   
2.        tree_nodename：节点名字或序号
   ' g$ P2 D/ P4 z+ l
3.        tree_nodevalue：节点对应的值
     l% k, q! B7 c: `& [9 A( g( ~& d
4.        tree_nodefather：节点父亲，如果没有父亲，值为空4 g9 b$ u6 Q$ N: X
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   ! ]  l( s# _* u# r7 g5 G
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空% M* z* G4 o/ U, v9 a
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。; R1 p# k- o! _  O2 j: }
   
8. , [) Z. P4 ?, o3 z3 R; ]
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   0 U\" K6 Z' O- X; Z
10. 
    ; o+ h) o% E6 ^& f
11.        %matlab源程序
    , @+ j3 \) g, R
12.        %输入：树的深度、树的广度、搜索的值\" E  ?+ k! r# b' _' n
    
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空& h9 |# f% ^$ `) H+ {& J& g
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    . I\" U) W0 @6 ?, D, V0 `
15.        %根据树的深度、节点的儿子数量计算树总的节点个数, U/ a% y$ w# U& a. v
    
16.        node_num = 0;3 i1 O! ~# S. b
    
17.        for n= 0 : (tree_depth-1)
    1 t  \; z- ~\" D% c
18.               node_num = node_num + tree_width ^ n;2 H! @0 ~, A5 F- m5 v3 F3 y3 s
    
19.        end, O$ X  l1 C\" c) F
    
20. 2 X9 @0 w5 D5 Q) Z8 j& Q
    
21.        %为树的存储空间赋值
    : m% ?) l\" p! E! M
22.        %node name，按照广度优先为节点排号
    + d) B7 x0 i3 Z9 o
23.        tree_nodename = (1 : node_num);
    $ s9 u/ f, U4 C) H5 X: @8 V' l
24.        %node value
    \" h  X; |  ]. s4 ?
25.        tree_nodevalue = rand(1 : node_num);
    7 E) v9 r1 U8 |7 y- ^$ e
26.        %node father and son
    \" r; Z# a8 G, M/ H' N
27.        tree_nodefather(1) = 0;, x6 B' j2 t' J% k: X\" E, i. h
    
28.        tree_nodeson = zeros(1, node_num);3 @% b9 |% I& N8 E1 E5 p2 H
    
29.        n = 2;1 }4 L7 y0 ?! v4 T. q+ t# E
    
30.        k = 1;% m1 l\" t) F\" s6 b3 J% i2 ?1 x
    
31.        while n <= node_num; K) \- L' v8 E
    
32.               for m = 1 : tree_width
    4 [# G3 c  \. g+ H. l
33.                      tree_nodefather(n) = k;& I# J- {0 ]$ t; Y& M% F: D: v0 m
    
34.                      if m==1( A4 x* x8 n6 g' s2 @. K
    
35.                             tree_nodeson(k) = n;$ q% N6 h: \/ |: X7 [- y
    
36.                      end
    ' k& _+ y6 K* ?% ~7 V8 o% H$ L: _8 j
37.                      n = n + 1;9 |3 B\" ]. z9 V3 w# p% d
    
38.               end$ y* d7 F, S8 B$ v\" p
    
39.               k = k + 1;
    & j3 E! \6 Q* ?# V7 `0 [' X
40.        end
    ! _. v5 W5 M+ A+ ]9 y- z0 _
41.        %node neighbor' @( u0 c! ?9 o+ g0 ?5 a
    
42.        tree_nodeneighbor(1) = 0;- g3 m5 m6 L. ]7 X  @4 g
    
43.        n = 2;
    . Y7 N& m# b) d2 q2 q0 d! U
44.        while n <= node_num
    ) ]+ q' ?8 Z% O
45.               for m = 1 : tree_width
    - o& |1 I6 I/ }8 U! U
46.                      if m ==tree_width3 q$ d2 g1 n% O\" j% x
    
47.                             tree_nodeneighbor(n) = 0;0 i9 x# H! R' I; k4 M' D1 C
    
48.                      else
    & X1 W6 {- c$ }, B/ W+ J
49.                             tree_nodeneighbor(n) = n + 1;
    5 a7 _! c; H- m) @: z4 \
50.                      end
    ; B! M# h: N' I8 r# k2 u
51.                      n = n + 1;
    : Z5 h2 P! U% d+ u- n0 U: `. U
52.               end  @0 S3 D! {; l. b, t
    
53.        end
    : i% @6 M. J) P* k# `( ^
54. & o5 I( ^  h. F% z
    
55.        %下面是有效程序段，用栈实现0 j7 N3 O/ u8 \9 F4 p
    
56.        stack = zeros(1, tree_depth);9 D, E# z1 H2 ]% z2 o
    
57.        nodeinstack = zeros(1, node_num);
    6 u  R: a- t( Q5 U$ V
58.        stack_ptr = 1;
    3 C2 m9 s# c1 A, Y  l7 D5 F
59.        stack(1) = 1;  K$ g$ E- h0 a\" D' G6 j, i% ]0 z\" D3 {
    
60.        nodeinstack(1) = 1;1 C( s& @4 @0 `! u0 a$ R6 d  h1 v
    
61.        valueintree = seek_value;
    - X+ h7 ^4 G7 n1 C  W% J5 y
62.        nodeintree = 0;; {: a: C/ @7 D) s' C5 L( Z
    
63. 
      @$ F( z' w2 o& {% [\" b
64.        while stack_ptr > 0
    - T, m! d4 t, g$ p: o
65.               n = stack(stack_ptr);5 k5 \: a8 L  {. O; T2 A! x( Q6 A1 ^+ W
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    - }' s6 I+ T+ f6 K1 `# N6 p
67.               %如果搜索到值，返回; [' G) I' n% s+ d
    
68.                      valueintree = tree_nodevalue(n);
      F, x+ T9 @8 L! t/ t% [- }& }
69.                      nodeintree = tree_nodename(n);2 b' _( B\" `3 K
    
70.                      break;, ~\" w! @* J  J
    
71.               end
    1 e# E, R. k: `7 _
72. 
    7 X/ f/ _\" m8 O+ S2 M% p- ]* K
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1% D) |3 r9 M: O' F
    
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    : y- p0 y, ]7 |- R  L: t
75.                      stack_ptr = stack_ptr + 1;
    9 o8 [0 o, M  y8 S5 T9 s
76.                      m = tree_nodeson(n);
    9 P, p3 W* m# t' K
77.                      stack(stack_ptr) = m;
    8 @$ T# {' o8 H1 l
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    . f( g+ E- i& p5 v/ }- X
79.               elseif tree_nodeneighbor(n) ~= 0$ Y6 N7 I: n+ w' ~0 A2 K# |% w. R5 q5 H
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    4 C  j) J2 h; f& ?# g0 m
81.                      m = tree_nodeneighbor(n);  B7 e, R0 z# B  g
    
82.                      stack(stack_ptr) = m;
    3 k7 ~9 f2 i- C1 _
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    0 @! Q. q\" a% g! i\" p. D' P$ K
84.               else. K! V5 I4 U\" C& r9 h. J
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    1 q+ \& }. H) s
86.                      stack_ptr = stack_ptr - 1;
    - i. @2 {1 L5 B; o9 o\" ]; c4 S2 y
87.                      m = stack(stack_ptr);
    % _; ?- t* R& t
88.                      nodeinstack(m) = nodeinstack(m) + 1;
    . p: r. O  D# P) l
89.               end
    : W) F) x' }7 \. a
90.        end

复制代码