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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   : _  l; }+ f+ Z8 y8 v9 D) K
2.        tree_nodename：节点名字或序号
   4 J2 d7 N; l' h3 Y0 `) [
3.        tree_nodevalue：节点对应的值\" c7 ?$ d1 `8 }$ v
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   , f4 K$ ~/ A- H1 z* T4 n3 f2 g% U# R
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空0 Q% R% q0 S5 M4 Z
   
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空. s& q5 Q' [* w\" Y
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。3 U4 x3 @- @* |\" Y) Q1 l
   
8. - u0 W5 Z: ~5 [  U% W' U
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   ; I1 L8 n1 V$ J% _
10. 
    5 \+ J9 S7 P8 o7 C  ^7 j/ v9 I
11.        %matlab源程序
    $ X$ M- A; n5 w
12.        %输入：树的深度、树的广度、搜索的值
    % }! \$ a* y: e9 k. \
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空* w- N2 `4 v' }8 \* B# F# ]
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    4 B* P# q0 }\" A( Y
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    ' X8 P) H: i5 i% q
16.        node_num = 0;
    + G: B, K2 J% {
17.        for n= 0 : (tree_depth-1)9 n. O) p* C  a3 k+ f7 G
    
18.               node_num = node_num + tree_width ^ n;
    ( X( N6 T! x/ Z
19.        end
    # Y3 }$ U2 W5 H0 L0 |
20. * s\" U% G' I* h, A5 p+ h# X
    
21.        %为树的存储空间赋值
    ; x7 G4 G6 R, t( ^5 V5 U) j4 a
22.        %node name，按照广度优先为节点排号
    * O/ P5 @0 I\" Y, k- P* U\" M- P
23.        tree_nodename = (1 : node_num);6 J; h/ @/ R+ g0 O
    
24.        %node value
    9 G9 R. F$ v; r5 C; e/ ~' a. V
25.        tree_nodevalue = rand(1 : node_num);
    # l+ ]( H% [5 W4 I& ~/ U7 X
26.        %node father and son* O4 \( B1 p& t, V2 r8 D
    
27.        tree_nodefather(1) = 0;
    7 b, N7 Z) J; N' d. Q5 Q
28.        tree_nodeson = zeros(1, node_num);
    / a3 B4 y% C2 ^( k# G( j; M
29.        n = 2;5 r7 c, e3 O* K. a' W
    
30.        k = 1;
    7 `! v: K; x7 t\" V0 u
31.        while n <= node_num
    % [- k3 [4 R- S$ K( ?' r
32.               for m = 1 : tree_width6 ?9 v\" R0 X* a7 u1 Z
    
33.                      tree_nodefather(n) = k;
    ) a1 ?. r6 g# l( T  I2 w7 r
34.                      if m==12 [) L3 m* {% ^* }( B) @. y4 m0 P
    
35.                             tree_nodeson(k) = n;: ]9 F( K+ C% G7 H
    
36.                      end
    3 I9 H0 \' f0 [' e2 z; F
37.                      n = n + 1;
    % ~2 W! Z# g\" n+ `. x8 A5 L
38.               end
      U# }9 X% o$ C6 Y
39.               k = k + 1;. l! l6 y& G\" Z9 r
    
40.        end/ e( v6 o) T* H* C0 ?
    
41.        %node neighbor
    & R3 @+ Y  l0 O2 q+ r1 g
42.        tree_nodeneighbor(1) = 0;
    - z: J2 J3 I; O. E
43.        n = 2;% z8 U) ]9 J9 a3 h! {* N( B  R
    
44.        while n <= node_num: K: a- o' H: \+ v9 v
    
45.               for m = 1 : tree_width% p9 L+ w5 i9 e) x
    
46.                      if m ==tree_width( Q; I9 _- G9 @, \8 g
    
47.                             tree_nodeneighbor(n) = 0;  v8 b$ U) [! Q7 J( u\" q. `
    
48.                      else
    / _7 M: G$ z6 x, N
49.                             tree_nodeneighbor(n) = n + 1;3 D/ E. }8 O$ G8 E  K
    
50.                      end
    ! N& }* s. v3 g) Q
51.                      n = n + 1;  J4 Z. g, w2 Y
    
52.               end
    . a# c3 n7 w1 ?% m3 {
53.        end( p) j1 t& {  A# H
    
54. - K+ [  f+ `! {# T; X
    
55.        %下面是有效程序段，用栈实现
    - a2 k! N4 j0 _/ r9 q
56.        stack = zeros(1, tree_depth);
    . J7 X. S* O, e$ A0 R# |
57.        nodeinstack = zeros(1, node_num);
    0 x& L. j% `+ ^3 L
58.        stack_ptr = 1;+ |, Y. j& G% Y9 o
    
59.        stack(1) = 1;
    9 b1 m4 a2 M3 k: Q8 N
60.        nodeinstack(1) = 1;: C; ~/ H, n; _; Y
    
61.        valueintree = seek_value;
    3 g1 _5 C. n% a: L/ f
62.        nodeintree = 0;
    4 I% W: d0 w& X: r
63. 
    1 r/ `) [; |$ k/ i* A) Z& v
64.        while stack_ptr > 0; y7 n/ \# O  m6 ^
    
65.               n = stack(stack_ptr);
    % ]7 ?$ v5 E1 a7 |% c9 x$ ]
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-32 O7 C1 K+ [6 x
    
67.               %如果搜索到值，返回3 E9 t' u1 s) g% }& @- ^, `
    
68.                      valueintree = tree_nodevalue(n);. F# h' W' n/ |8 L, U; e* n
    
69.                      nodeintree = tree_nodename(n);
    5 q' C; x: q, \1 G2 u
70.                      break;
    ( ?$ s9 n+ d1 i& k7 F) S
71.               end
    9 N+ \+ }6 L0 R$ \7 I! K
72. 4 z4 S) `. w- q* X9 V$ R
    
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    : W2 G; m& z4 M
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈5 V* B5 p3 [( X  S
    
75.                      stack_ptr = stack_ptr + 1;
    1 z2 @8 H- W. s0 H4 g
76.                      m = tree_nodeson(n);
    . |) V  f0 A- e7 r0 a7 t
77.                      stack(stack_ptr) = m;9 Q2 a  Y; O\" @$ t' P9 D( b
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;( W  B; ?- s/ I* E
    
79.               elseif tree_nodeneighbor(n) ~= 0
    ; J% |3 p) D! Z5 U6 N
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    . W9 l# r7 l7 ^1 Z, n/ h& p
81.                      m = tree_nodeneighbor(n);
    6 s+ A# T: X% S6 H6 x- g8 }6 H
82.                      stack(stack_ptr) = m;8 r8 y+ t\" v5 j
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;$ v7 X; s/ i- U# V+ B6 {
    
84.               else
    * N\" X& s, o' F+ _; L
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    0 L# C% n$ f$ q5 X  U
86.                      stack_ptr = stack_ptr - 1;+ P% Y! A3 W5 t3 T/ p- y
    
87.                      m = stack(stack_ptr);
    * H1 _* l5 m0 m+ Y! _+ x
88.                      nodeinstack(m) = nodeinstack(m) + 1;
    $ O3 `5 t$ z& _# d2 \
89.               end
    , L- b1 K4 L0 s- M
90.        end

复制代码