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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   7 x* H6 x3 _, o0 }3 \
2.        tree_nodename：节点名字或序号
   , O' A- k+ E6 z1 n% f* F3 T# q
3.        tree_nodevalue：节点对应的值2 \: @( r' q, F$ f; M0 y3 ?
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空1 b# U+ e. P# S& Z- ^9 [
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空1 M6 D+ D7 A& S6 A2 i
   
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
   & H0 k) e4 v7 {7 l7 O, D
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   8 X4 f3 ]) u: t) T$ r
8. 
   4 P: Q9 S$ \, i: \& J4 s
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   ) o4 ~% T4 g6 N' L$ P5 J1 Y8 F
10. 
    1 e4 p2 Z) x% F5 G/ d, x. I
11.        %matlab源程序5 d' P0 K! r4 C$ M( N, \
    
12.        %输入：树的深度、树的广度、搜索的值
    2 i3 q- i- }0 W; S
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    / D4 Z% Y0 L8 y8 O& e' d( M- H/ j  X
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)3 ]% H7 ]) S* V2 S; D/ U
    
15.        %根据树的深度、节点的儿子数量计算树总的节点个数- M; B3 G; R1 C5 e- o+ u+ `
    
16.        node_num = 0;
    / w: l( i( y4 K4 ~4 y
17.        for n= 0 : (tree_depth-1)5 m\" |, Z! z, O! Y
    
18.               node_num = node_num + tree_width ^ n;
    0 Y$ i' X0 ]; |# b% i/ }
19.        end5 k2 d  w4 j8 Y4 m+ C) x
    
20. 
    ' {: ^* ~/ D8 f: I8 k4 D' u3 a
21.        %为树的存储空间赋值
    / S8 l' f+ x8 K, C
22.        %node name，按照广度优先为节点排号- F. n, ~; G+ A) O  z6 T( f3 ^
    
23.        tree_nodename = (1 : node_num);- @: p! Q1 ~, T2 C- S2 S
    
24.        %node value
    $ ~8 W) `( p& _- N; [
25.        tree_nodevalue = rand(1 : node_num);' p. @3 R9 Y$ t* X  X  f% |
    
26.        %node father and son
    1 Z\" H2 N  L) J/ B
27.        tree_nodefather(1) = 0;) H2 ?2 O3 f9 q0 z( D
    
28.        tree_nodeson = zeros(1, node_num);
    2 _  P5 P' F+ K4 |\" I# p: u
29.        n = 2;
    ; O+ [\" E& R# {' E4 h
30.        k = 1;1 K9 j( `8 M0 u6 h: N) Z
    
31.        while n <= node_num: I/ b6 P8 Q% G3 K. z
    
32.               for m = 1 : tree_width2 X2 f% }  _9 D
    
33.                      tree_nodefather(n) = k;/ ~( w- q; s3 A: T
    
34.                      if m==1, J# x; v2 ]\" q
    
35.                             tree_nodeson(k) = n;, O' K  [8 l% M: v/ g
    
36.                      end
    ( c4 e7 W# r( n1 O8 V( W9 z, g$ R+ }8 }
37.                      n = n + 1;* t1 z/ j) V6 i
    
38.               end
    1 u* I7 b4 l6 ?8 Z
39.               k = k + 1;
    : \4 _9 \7 S6 U. u3 [- c% y/ q6 \3 m
40.        end% c/ `7 B+ {+ ]( N
    
41.        %node neighbor1 Y* {) m2 u. {: H6 c! e, k% o
    
42.        tree_nodeneighbor(1) = 0;( a# ?3 Q: N. Z7 n5 _; t' g, l9 Y
    
43.        n = 2;
    ) i- U0 \) h4 k0 U
44.        while n <= node_num
    : h, R( E( p\" \
45.               for m = 1 : tree_width( V; j0 H9 r+ t5 W! i7 H& D, z
    
46.                      if m ==tree_width: X4 G% V7 m4 ^& C3 s! _9 x0 s5 B. v
    
47.                             tree_nodeneighbor(n) = 0;0 ?) L; b1 w8 }1 a8 V; W- E
    
48.                      else' B7 R: j& [4 g+ H, F
    
49.                             tree_nodeneighbor(n) = n + 1;
    6 D/ X. }+ L- c* o
50.                      end
    7 v2 ^4 d7 Q2 |5 W' j  Q1 f
51.                      n = n + 1;; g! o: V6 F1 |/ v8 o5 c% F$ W
    
52.               end8 m/ C/ [2 c' C
    
53.        end
    5 S9 w# j- s. T/ w
54. 
    - I! I. `2 J! ~& P\" ~8 |! ]! G
55.        %下面是有效程序段，用栈实现
    4 C4 e\" }* b6 h  q9 I' D
56.        stack = zeros(1, tree_depth);8 v+ m' C0 p- N; p
    
57.        nodeinstack = zeros(1, node_num);
    : a  F5 I7 P: B- w! s
58.        stack_ptr = 1;
    - \3 |, ?& z. V7 M8 C/ F
59.        stack(1) = 1;( C( M& {) e% m8 M# m
    
60.        nodeinstack(1) = 1;  @1 a3 h) f. ~- @4 x
    
61.        valueintree = seek_value;
    2 p7 c+ R# u6 E# {3 B, w
62.        nodeintree = 0;. {\" Z( N2 Q& F
    
63. % D5 b8 V# k/ M9 R; b9 ?
    
64.        while stack_ptr > 0( Z. ?# V8 I7 ]7 S( v
    
65.               n = stack(stack_ptr);: G7 K7 w' L8 W# `4 U
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-31 w  J4 P% K6 b: G1 [, M* I
    
67.               %如果搜索到值，返回1 ^% ]( [0 r' H/ F5 o, l' `3 J
    
68.                      valueintree = tree_nodevalue(n);$ c. X  O! J( c
    
69.                      nodeintree = tree_nodename(n);
    ) z3 Y) p\" g) ]2 Y0 m- T
70.                      break;
    / e. f# [$ z7 P; o0 F
71.               end
    ) n. T4 p7 [4 b! Y* N
72. 0 c, m8 c# @7 V1 c4 W/ G4 K! W0 o
    
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1! N3 P8 H5 W! C% g5 k1 \; b
    
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    $ D  E' i$ z3 P7 w
75.                      stack_ptr = stack_ptr + 1;
    1 x9 a# e/ T3 }$ m$ C
76.                      m = tree_nodeson(n);
    + t% F8 W3 z; u, {9 x
77.                      stack(stack_ptr) = m;& Q6 g! Q; F0 t$ Q% }3 J3 [
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    % \4 {, y; X) |2 J0 N\" L5 ^, S
79.               elseif tree_nodeneighbor(n) ~= 0( V0 k7 z% t7 `\" A
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈$ R0 q) M. {$ W1 J2 r
    
81.                      m = tree_nodeneighbor(n);. ^7 l9 m8 n5 I1 F0 F4 S
    
82.                      stack(stack_ptr) = m;
    \" c/ L$ c. N+ X' j3 F7 Z5 x
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    % d) ?/ W* \) F
84.               else$ G1 @\" c\" w7 S! S  o
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    1 f5 Q; a( K' D2 e' b
86.                      stack_ptr = stack_ptr - 1;
    9 x- r5 ]* B$ \6 _1 \9 B- f' t4 \
87.                      m = stack(stack_ptr);' B( g+ P& U! j7 D5 [, F+ _
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;; R& ]7 S9 l, h) k5 C- J
    
89.               end' N\" @6 s; F4 P  {0 n
    
90.        end

复制代码