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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   ( |' B  s$ `6 v  \4 y
2.        tree_nodename：节点名字或序号1 `: ]( N- {1 l4 l) q% M3 }$ E. N
   
3.        tree_nodevalue：节点对应的值; L# }$ a0 H, j' g
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   ( P6 U. ^1 T2 _9 Q: M& k& A4 G
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   : {( ?6 L, M$ O5 P
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空! z3 f+ s' s% E  O- O
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   & T0 S( S3 x4 J: F4 L9 [
8. $ R( L' q  ^7 y
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   * x* U% Y7 W+ w1 a( E% v% |
10. 
    ) F0 V6 v4 h1 m) ]9 ?$ L4 f
11.        %matlab源程序
    * z1 J& g5 l6 I5 }8 `( b+ n& O7 r
12.        %输入：树的深度、树的广度、搜索的值7 ?) V! Y0 G, v' h& M3 h% y
    
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    \" z& Y) V( A8 U$ P* P
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
      A2 x: h+ o- Q6 O1 j3 @$ i
15.        %根据树的深度、节点的儿子数量计算树总的节点个数7 m9 O$ v  B' r8 \& L
    
16.        node_num = 0;
    * W8 s- \* `' C3 p9 b
17.        for n= 0 : (tree_depth-1)
    4 h% Z6 m  i! j5 ~7 I
18.               node_num = node_num + tree_width ^ n;, F; F/ ~8 x. R$ p
    
19.        end
    2 A( o4 Z+ @! d* t; g- \$ y
20. 
    6 `; O8 K4 A! [9 [' M
21.        %为树的存储空间赋值6 i7 K1 v, r' M8 C' l: Y& [
    
22.        %node name，按照广度优先为节点排号  F! n5 \5 H2 t5 x( u' e
    
23.        tree_nodename = (1 : node_num);1 B5 k0 X; |$ z/ N6 U
    
24.        %node value4 ^, k- T, u( J  w* U
    
25.        tree_nodevalue = rand(1 : node_num);$ j% w# n( G+ }
    
26.        %node father and son
    ( O2 f2 r1 H- `! v1 Z! X  q
27.        tree_nodefather(1) = 0;
    ) P' o& G0 `& ^, `, H! I: x
28.        tree_nodeson = zeros(1, node_num);' c: {% T3 Q% w# h
    
29.        n = 2;' \& C6 J: ~! b: }0 r
    
30.        k = 1;
    ; K) L# F1 q) F
31.        while n <= node_num/ \7 f% O7 I0 \\" ^9 t! p
    
32.               for m = 1 : tree_width2 H4 u1 Z1 b( m! V: ?
    
33.                      tree_nodefather(n) = k;
    4 T0 \5 @6 h, _: ~1 r
34.                      if m==1) G$ m, ?\" y* z\" G! p0 T) W
    
35.                             tree_nodeson(k) = n;
    6 w3 S- V- M3 j: l8 t5 g# p
36.                      end
    5 W: Q) y3 I0 S  n
37.                      n = n + 1;1 L! z) c! c( P: L  A- y% w
    
38.               end5 Z! ^/ F8 d. _) M
    
39.               k = k + 1;
    5 u6 m! c\" w& O/ F
40.        end
    4 H* \5 J\" a  c& ]: H
41.        %node neighbor: w- \5 b2 w\" k
    
42.        tree_nodeneighbor(1) = 0;3 V/ U; C* O  a0 A& e- R6 `
    
43.        n = 2;
    7 m% g; Z, f; x$ N
44.        while n <= node_num7 S5 F. F  b+ [9 ^
    
45.               for m = 1 : tree_width
    - {* {7 t- n# n( L
46.                      if m ==tree_width
    - ?* t- d7 }3 l0 W* J
47.                             tree_nodeneighbor(n) = 0;
    . l8 Q5 }6 @. h- l
48.                      else( z/ {0 U  ]) g8 u
    
49.                             tree_nodeneighbor(n) = n + 1;
    6 u, l1 U( ^( q, q\" l, ], T' r# I
50.                      end
    / i. W6 E/ V1 i0 y
51.                      n = n + 1;
    ) ^$ C0 W8 }5 S6 j6 x5 |# _& R7 j
52.               end+ _. T! E) r. {
    
53.        end
    6 l# i2 A1 h$ M/ u
54. 
    ; `6 h3 w. L- s2 |# D* W; E
55.        %下面是有效程序段，用栈实现+ D/ ~# E6 Z% L* f3 N7 x
    
56.        stack = zeros(1, tree_depth);2 S8 Q, ~1 D2 O1 x
    
57.        nodeinstack = zeros(1, node_num);
    8 b2 N5 _& W; Z8 M; s
58.        stack_ptr = 1;
    . s4 `7 Z' a* K' B8 a9 R3 |7 ], I
59.        stack(1) = 1;
    * R' s0 k/ e( c. |6 U. L  n# i\" L
60.        nodeinstack(1) = 1;: Z\" l; _8 d. I% ?3 `; i$ G3 W! P4 P
    
61.        valueintree = seek_value;
    1 |% f  B, b# v3 L3 J7 N2 ^# C
62.        nodeintree = 0;
    3 r. \, }& X, o6 U* ]\" [
63. 
    5 g, k1 A7 y5 N: {. J5 F9 {
64.        while stack_ptr > 0
    # [! S\" y( R' G
65.               n = stack(stack_ptr);
    4 Y* a! v! T( f+ h
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3+ g& N) @: `6 ]5 ?\" D* u
    
67.               %如果搜索到值，返回
    5 v$ ^# L; s\" q! J  g9 Q4 z3 Z: Z
68.                      valueintree = tree_nodevalue(n);
    ) c. L- |7 }- J- q) [
69.                      nodeintree = tree_nodename(n);
    % g  P- L0 ^- t\" Y2 A/ q
70.                      break;8 |. X8 h+ ^' \) r& s8 p
    
71.               end) K; w! H6 @8 P# w* H, Z; Z
    
72. : g4 M* D1 [4 Q2 ~( _
    
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1: ]& h$ u& m\" H# F- _- z
    
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    3 J: Q* q  D% P; j* K/ q
75.                      stack_ptr = stack_ptr + 1;
    ( v9 L$ _- _. p0 `; w4 e0 B* h1 f
76.                      m = tree_nodeson(n);3 g/ L: D! u6 L8 S
    
77.                      stack(stack_ptr) = m;. @) P* E6 e2 M& `! {* H1 J
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    ; D9 @( J% {& @, @, l4 f0 C* U
79.               elseif tree_nodeneighbor(n) ~= 0
    4 y2 h) f) D! p) R3 ?\" T3 @- X
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈\" ^. v+ V6 i- s* y, z
    
81.                      m = tree_nodeneighbor(n);
    / E* i7 _* _: [5 r
82.                      stack(stack_ptr) = m;
    3 V* J( h1 U' v$ b. R
83.                      nodeinstack(m) = nodeinstack(m) + 1;2 a& R; Y  e% B
    
84.               else% _% t  }5 r4 o/ s  d( j
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一9 ~. f2 \9 i  o6 z1 f% {* D
    
86.                      stack_ptr = stack_ptr - 1;- q) S1 e% Z' w( M, e* J
    
87.                      m = stack(stack_ptr);4 p- M: h2 Q' g: A; Y
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;
    ( X) G+ q' d/ u' `0 |1 Z- ]
89.               end
    8 ~9 p4 M) Q0 ?0 O$ ^! s
90.        end

复制代码