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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   0 E; W: R) }2 |) A
2.        tree_nodename：节点名字或序号
   * X! b! O1 b. h% ]! \6 p
3.        tree_nodevalue：节点对应的值4 w1 F: i& C: r
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   $ T: C% Z+ u. W\" [9 S: S1 ]
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   * F% n2 g( [. b, K
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
   # P\" F2 i) q! [. E9 ?3 Z
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   ( m$ ^% V% @& T5 E0 o# s
8. 
   / I3 ?! ~4 w! E% L& I
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。1 `+ F& B% C) K+ ]6 r
   
10. # d* f* b3 R7 A7 @& z2 h; Q
    
11.        %matlab源程序0 j1 i8 b0 @6 v
    
12.        %输入：树的深度、树的广度、搜索的值6 g6 B, f/ b  G
    
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
      P  B* h# t0 [% w/ v9 r7 j
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)9 c2 s) T( w6 q3 d3 C) F3 _- c! Z
    
15.        %根据树的深度、节点的儿子数量计算树总的节点个数( n/ p2 R5 y4 w5 A\" e8 P\" q
    
16.        node_num = 0;5 R9 O1 w) [  t1 p4 m- z* H; b4 l
    
17.        for n= 0 : (tree_depth-1)
    $ W8 X# E& A2 a; _8 }' N1 ~0 U
18.               node_num = node_num + tree_width ^ n;
    ( j9 l4 }* O  ?8 R. w6 d2 b2 {& m
19.        end
    8 g, d8 ]) w' Z$ }; Z: Q8 I& {
20. % g! j0 [% }: c8 D
    
21.        %为树的存储空间赋值
    0 L3 f. j8 P8 m; [* U9 p
22.        %node name，按照广度优先为节点排号
    9 d+ u+ e* B6 A+ W# X' M+ S
23.        tree_nodename = (1 : node_num);
    7 x) p- O! `- K$ V, @' p; g
24.        %node value( [! u! ?/ |. l1 v, r* J% T  v
    
25.        tree_nodevalue = rand(1 : node_num);
      [( g6 x: O& H
26.        %node father and son
    / f$ E5 p0 |3 ]7 B3 ]
27.        tree_nodefather(1) = 0;
    ) H  x2 H$ `% }& j1 b
28.        tree_nodeson = zeros(1, node_num);6 M$ J( i+ j$ |4 |( D. a( Z' j( c
    
29.        n = 2;% F( x5 b: E, W
    
30.        k = 1;
    ! l# U\" D8 _1 o
31.        while n <= node_num
    9 a' ?1 o3 M% A* G9 T6 P
32.               for m = 1 : tree_width
    6 l/ Q6 }6 W. Q\" L& C- q& Y
33.                      tree_nodefather(n) = k;
    ' b3 J6 }5 Z; j$ T8 q
34.                      if m==1, d8 A+ Y  i  W$ m# z
    
35.                             tree_nodeson(k) = n;  _$ D: u( L7 q4 N* v( }
    
36.                      end
    . @# N& J7 g$ o) G; N. S
37.                      n = n + 1;
    5 [\" A  r( H$ }! [! p  \
38.               end5 E% K( B% {2 D: m
    
39.               k = k + 1;
    ; m' a, p7 S) i0 j( _% `
40.        end
    / w$ h: ?# _$ t2 M
41.        %node neighbor
    9 q$ U# U+ P4 |0 `- M2 J# W
42.        tree_nodeneighbor(1) = 0;) K+ |, H! y; n* [
    
43.        n = 2;4 i1 P9 n3 Q7 |) K/ F
    
44.        while n <= node_num, d% F, T: o7 l; Y0 a+ z5 w0 F
    
45.               for m = 1 : tree_width/ \1 C: B. Q- D1 T  @0 a
    
46.                      if m ==tree_width4 n3 P; O' |/ L1 F7 B* s* x; r
    
47.                             tree_nodeneighbor(n) = 0;
    9 a0 i7 a3 l$ r. Q
48.                      else8 j3 F/ C) P/ D
    
49.                             tree_nodeneighbor(n) = n + 1;$ ^  Q, c0 z: [  I! Y  B
    
50.                      end& Q* N  e; O8 I, r. l
    
51.                      n = n + 1;
    ; q( \6 F0 N: H# a+ {- I
52.               end2 @0 G# v# D) S& X/ B; z
    
53.        end
    7 P- Z6 f: U* ~. ]% i# M0 Q: H
54. 
    + g' ?+ D! I1 x# u' Q4 @, ^
55.        %下面是有效程序段，用栈实现
    ) O! S0 ]6 I5 I- t/ Y
56.        stack = zeros(1, tree_depth);) v! A. _7 m0 g
    
57.        nodeinstack = zeros(1, node_num);
    $ w\" [1 y, x- I& V7 Q8 i
58.        stack_ptr = 1;/ o# W) J. W' Y
    
59.        stack(1) = 1;
    9 v6 F* s$ q0 X$ s
60.        nodeinstack(1) = 1;
    . V4 X9 i% M: d2 N5 [
61.        valueintree = seek_value;
    ) M( x) P7 @# r- [\" ]5 X$ w) w* n
62.        nodeintree = 0;
    3 \6 ~) Z3 S1 g8 R
63. 3 R- n% g( |6 _# m; l
    
64.        while stack_ptr > 0
    ) K$ @* y- S- C; l8 W9 g
65.               n = stack(stack_ptr);4 M; a7 N4 z3 a; a
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    : j9 j1 s% ~2 P) \6 E$ V6 _
67.               %如果搜索到值，返回
    1 [. U7 D- _5 q: K
68.                      valueintree = tree_nodevalue(n);
    . u( N* J! f# U6 v4 L
69.                      nodeintree = tree_nodename(n);. k0 W- I( \( J# ~
    
70.                      break;
    2 @$ P# y' N& W/ S( f1 ^, }
71.               end5 O1 N* K. [3 \
    
72. . [/ R% w( h( D2 Q8 C
    
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    4 D! j* O2 n5 @5 _
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈2 [0 c% q1 v) h
    
75.                      stack_ptr = stack_ptr + 1;
    9 N2 f; S7 p& q2 l\" s5 r% n
76.                      m = tree_nodeson(n);2 F5 a1 Z2 p\" T/ i$ F$ I5 F
    
77.                      stack(stack_ptr) = m;# K% R8 X, S5 E* _. [- m0 H$ \
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;* w6 B9 }. J6 R3 u
    
79.               elseif tree_nodeneighbor(n) ~= 02 |  j8 U. D2 Y( e* B/ F
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    - j# C0 I8 y* |/ d1 d\" c
81.                      m = tree_nodeneighbor(n);
    1 W% O. W; v& Z* n- M
82.                      stack(stack_ptr) = m;
    ) ^1 f2 i3 p3 ~\" i
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    4 l7 g9 B\" l' \- G' n
84.               else) r4 r# V0 ]( R( I
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一0 O2 C5 r) s. \2 K# t1 I* T
    
86.                      stack_ptr = stack_ptr - 1;! T; K9 u0 ]\" P7 j3 Y' j
    
87.                      m = stack(stack_ptr);
      B5 C; K9 ]5 y8 u& j' v
88.                      nodeinstack(m) = nodeinstack(m) + 1;0 t% j8 a% b9 [4 W
    
89.               end
    6 |# `( e$ K( F% p9 ^$ F
90.        end

复制代码