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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   3 {+ M4 P& Z4 ]% q7 Q
2.        tree_nodename：节点名字或序号
   + P3 S: v- z+ q6 f1 Q
3.        tree_nodevalue：节点对应的值
   % M5 T! A4 W/ x  B+ p
4.        tree_nodefather：节点父亲，如果没有父亲，值为空7 [3 X8 u4 u  M/ n% L: y
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空9 r; t  Z$ O7 U( ~3 U$ {
   
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
   9 E; T$ v9 V/ b0 X  ?
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。) O4 ^  R6 m7 g7 |' k6 ?5 B
   
8. 4 F. _! j1 ?) d* Z
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   0 `5 B2 G* g2 u- M
10. $ E$ M\" M8 t% ]) c: e
    
11.        %matlab源程序, I/ o0 x5 H; `( O1 q; P\" y  i8 L9 n+ ]
    
12.        %输入：树的深度、树的广度、搜索的值% x/ S- @4 |& a2 {, P
    
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空' c$ r1 ]3 y/ J; f; y
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    ( A' I/ f9 x* ]: b/ q
15.        %根据树的深度、节点的儿子数量计算树总的节点个数  Y, L! v6 g8 A0 _& K$ i8 _
    
16.        node_num = 0;' @\" u; F' q0 t  @( {
    
17.        for n= 0 : (tree_depth-1)
    + j1 e7 D. W* Z4 `
18.               node_num = node_num + tree_width ^ n;
    3 o3 ]5 M! c) f' i9 o\" G
19.        end
    9 S. l$ D; y\" Z) M* l1 F
20. 
    * E1 Y5 j9 m2 [
21.        %为树的存储空间赋值. A* T, Z5 B0 F4 {, b3 v( U1 A
    
22.        %node name，按照广度优先为节点排号
    0 |. u/ V1 d/ ?! B9 [/ g, i
23.        tree_nodename = (1 : node_num);* o+ A/ r' D1 J& ^  T) Z
    
24.        %node value
    4 U4 x$ y5 f4 [# H
25.        tree_nodevalue = rand(1 : node_num);6 o\" r; f& D+ D
    
26.        %node father and son
    5 V% e  I, \. |* }8 P1 I5 O
27.        tree_nodefather(1) = 0;5 z! y! s, b5 ]; u% s\" N
    
28.        tree_nodeson = zeros(1, node_num);  {$ Z3 J( X. B' l8 T
    
29.        n = 2;
    7 @. h, r- b. f\" s6 f+ b. ~' B
30.        k = 1;4 I4 t* V! H# G; d% x
    
31.        while n <= node_num  R4 `6 x6 K4 p4 B- t
    
32.               for m = 1 : tree_width: P  \8 K; C5 b! b
    
33.                      tree_nodefather(n) = k;- y0 ~$ M8 p# {: @
    
34.                      if m==1- L5 S# u. @\" A( f
    
35.                             tree_nodeson(k) = n;% m7 p9 O# {\" x* d1 D+ @3 g
    
36.                      end
    ( y' V& H\" d3 k6 q) V; K
37.                      n = n + 1;
    0 K7 U! @) z- N  l) c9 ~# \\" ~
38.               end
    : \4 f6 _$ |% x) t
39.               k = k + 1;
    * g! X\" g% i- S( ^  {
40.        end) U! }' v6 R7 x\" T0 }; J
    
41.        %node neighbor
    5 o\" }, N2 w, \# @  D
42.        tree_nodeneighbor(1) = 0;3 f+ G4 K# \7 j& _1 b  d( I& \
    
43.        n = 2;' X) L% Z8 U  g9 P( o
    
44.        while n <= node_num
      r1 H3 S: j+ r+ p- m4 C
45.               for m = 1 : tree_width3 O  {2 U6 S% \4 U& e) G- f
    
46.                      if m ==tree_width% |/ y4 p  Z( U2 q
    
47.                             tree_nodeneighbor(n) = 0;) X' ]) `# {: j3 L\" }  y% C
    
48.                      else3 T' |% U+ e6 C& j6 q
    
49.                             tree_nodeneighbor(n) = n + 1;
    * I! s# q: _9 g
50.                      end
    ; u9 p, \* h9 M* D5 \. s' @9 j
51.                      n = n + 1;4 A8 r9 N$ l  ^5 B
    
52.               end1 y1 B, f5 |3 u# W\" g! I
    
53.        end  {. }8 U; L- _
    
54. 0 g2 A  x* A- d9 W\" N$ G* d
    
55.        %下面是有效程序段，用栈实现
    % s7 ]; _  z. a% ~: k
56.        stack = zeros(1, tree_depth);; O( {2 f+ T( Q6 n  l9 ^5 W
    
57.        nodeinstack = zeros(1, node_num);1 z+ A8 I) m9 G' y' r% u
    
58.        stack_ptr = 1;* d2 y& N/ `( z! D
    
59.        stack(1) = 1;: O8 ~+ G; y- x! u- B: \$ R$ N
    
60.        nodeinstack(1) = 1;1 L+ ?, Z\" e9 T8 _$ T' V
    
61.        valueintree = seek_value;
    & [; z; Q( d' N9 P/ Y
62.        nodeintree = 0;
    + Z* C9 z6 [# y2 R4 |5 W
63. / q& v+ z9 i5 o5 S
    
64.        while stack_ptr > 0- f& {' t9 |+ n3 }
    
65.               n = stack(stack_ptr);( g! o$ M, c: j1 F6 o- G
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3( E* v  t( F) @* N1 F5 }, v% z
    
67.               %如果搜索到值，返回
    % R0 `+ M- i# f0 h, r# R
68.                      valueintree = tree_nodevalue(n);
    5 B# X( E$ x' q# G6 X0 c
69.                      nodeintree = tree_nodename(n);
    $ Z* q) e  _3 s( y' r: g
70.                      break;
    : ~1 v+ w7 _) J+ g
71.               end
    ) m1 J1 f& a) Z$ ]5 L# s6 W. x% \
72. 
    + `' H& `2 Z% J. Y* C) `\" D
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 13 s5 a! x# d! I4 T! J
    
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
      N& D7 o0 Z9 ~. V& A
75.                      stack_ptr = stack_ptr + 1;/ W4 z5 S. }. c
    
76.                      m = tree_nodeson(n);
    $ E6 X9 |3 D, w- u, |0 H
77.                      stack(stack_ptr) = m;
    1 Q' k- O: S, B$ u4 `( ~
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    0 }+ S9 d+ ~) I
79.               elseif tree_nodeneighbor(n) ~= 0  ?- c  e4 `6 L- e
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    . v$ K5 h, ~. S, i+ ^9 r
81.                      m = tree_nodeneighbor(n);3 b3 _8 s) d: \/ n
    
82.                      stack(stack_ptr) = m;9 w5 a\" R9 s: r5 T/ i
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    4 v( a) X% T5 y$ @, r, M0 b
84.               else
    3 C9 i2 _$ @% A+ {4 Q7 R4 t
85.               %再否则，出栈，然后将父亲节点的入栈次数加一3 ?) @1 r( q\" W; L  _& k
    
86.                      stack_ptr = stack_ptr - 1;+ ^5 Q9 V; a+ |6 g. _; G
    
87.                      m = stack(stack_ptr);9 t1 Q( P, k0 ?! k2 w/ ?2 o
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;
    . `  h: x. g3 P
89.               end& M5 x) M, d; f7 M
    
90.        end

复制代码