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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：7 O4 h0 e3 c/ M& ]- w4 r* c- b
   
2.        tree_nodename：节点名字或序号
   ! v9 d/ v! C# f' x# M% C
3.        tree_nodevalue：节点对应的值) `* p# s1 k1 K# J\" Y\" d2 Y
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   8 D# ]9 f\" p' ]6 q
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空2 b( g3 R9 o1 W% g& o* F4 F3 U
   
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
   & O0 K7 N; t8 }1 i  d0 N2 W
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。4 M, Y( e9 p* }, N
   
8. 
   ; ]4 q# [: r7 Z7 U( B! `7 V( U
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   , |' T6 m$ k) Y
10. 7 K! o* r6 O) B9 \3 j4 a
    
11.        %matlab源程序
    8 h\" M8 u; M9 _9 B
12.        %输入：树的深度、树的广度、搜索的值; O) m6 k  n3 D: q% L
    
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    5 N1 G2 [6 E( P\" p& s
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    % s! W4 \6 O2 G% T3 k. d( |
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    ( P, S4 h( ]& u% _9 e
16.        node_num = 0;
    ' g4 }$ I. C4 K0 V3 {8 l
17.        for n= 0 : (tree_depth-1)! D3 {$ V6 @8 [) X2 o+ y
    
18.               node_num = node_num + tree_width ^ n;' A* s9 d! N2 `3 ~7 C9 L' B
    
19.        end
    5 }, I, ~- A7 t1 I! s7 K
20. 
    9 D\" X' U6 d; V- U4 c7 e6 j
21.        %为树的存储空间赋值, b* V% f8 p. C1 V
    
22.        %node name，按照广度优先为节点排号
    / {, g- j6 J5 l# N( f
23.        tree_nodename = (1 : node_num);\" R& a2 K2 c) X6 R* e8 e% ]/ P$ p( `
    
24.        %node value
    1 V# S$ R/ o* A* o. D
25.        tree_nodevalue = rand(1 : node_num);
    ) `0 ^9 u/ f9 a
26.        %node father and son# i- i3 i$ L) X4 u
    
27.        tree_nodefather(1) = 0;
    2 s( n9 J& V- x% l7 J. s
28.        tree_nodeson = zeros(1, node_num);* u2 t3 A5 w$ K# b; t1 t
    
29.        n = 2;- F8 @/ p) y& g9 j8 g8 m: W8 @
    
30.        k = 1;! z0 Y+ G( z! w/ Y) J; g. t/ ^: o
    
31.        while n <= node_num, {) u4 B: u, N- P7 \$ T
    
32.               for m = 1 : tree_width
    / v( }$ @8 @' N+ Z
33.                      tree_nodefather(n) = k;6 `; ^. r- V* \
    
34.                      if m==1
    # o7 b) z8 I9 E/ h( c
35.                             tree_nodeson(k) = n;
    3 K$ b- y) U' E  J/ @( G
36.                      end
    # N: z/ E: S& z8 F2 u
37.                      n = n + 1;
    / D7 D% ?0 A/ S
38.               end' {& T$ |\" Y0 s: b  W
    
39.               k = k + 1;
    7 I' t* V$ I$ z  d
40.        end
      i( E# f7 o- [& V; i% ]' C
41.        %node neighbor
    2 h+ w3 l2 }4 Y7 I! N
42.        tree_nodeneighbor(1) = 0;
      V, t2 u( m% ?3 }0 e8 q  n
43.        n = 2;
    & ?0 M. N8 b0 b' `1 p
44.        while n <= node_num- g6 U) T+ `1 o0 I
    
45.               for m = 1 : tree_width2 i. z; }6 g6 S4 a
    
46.                      if m ==tree_width
    2 l* z' P! X/ H. A& j
47.                             tree_nodeneighbor(n) = 0;
    ) P8 ^- p2 J( h$ \% E\" X4 C
48.                      else
    0 Q\" H' U% p# Y9 m8 a9 P
49.                             tree_nodeneighbor(n) = n + 1;# f* P1 l- R9 Y
    
50.                      end
    . [5 |# X! c# g( y
51.                      n = n + 1;
    9 R* {4 K, p6 W) Y$ q; x
52.               end
    8 x* @- n! Q8 J& b/ V+ V+ [
53.        end
      x; B/ u0 k: @9 Q: S( `  P
54. 
    $ }, T/ m% x  W# U/ G$ `  N
55.        %下面是有效程序段，用栈实现
    \" J4 g' b4 r3 B2 P  w: P7 S5 U
56.        stack = zeros(1, tree_depth);: j7 g- E, f0 A\" p$ _
    
57.        nodeinstack = zeros(1, node_num);
    4 j8 }* r5 F0 I
58.        stack_ptr = 1;
    2 Y$ ^* H; V2 Y7 S$ l' C
59.        stack(1) = 1;
    ) K1 P% J  @\" t  p: C: ?  Y
60.        nodeinstack(1) = 1;% c& R4 ~- p, t9 M$ K/ B! z  U, @
    
61.        valueintree = seek_value;0 x$ E  r! [- B* ?8 j
    
62.        nodeintree = 0;
    # r7 ?4 x) w2 `- |
63. & U5 t' U1 M+ D% O1 K
    
64.        while stack_ptr > 0
    / }  U# f- ?  a/ ~+ O+ y
65.               n = stack(stack_ptr);
    * V+ N  f( J7 a, [3 N, K
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    ; q# q+ K) |\" W% G
67.               %如果搜索到值，返回; L( s* I8 ?( g
    
68.                      valueintree = tree_nodevalue(n);
    & |. @9 v3 e6 }* S& d
69.                      nodeintree = tree_nodename(n);
    . B& b8 j, p7 o
70.                      break;4 {. }8 K. ~\" r/ p# ]% _  L- j
    
71.               end- {$ Q: h/ j% s! ^% _- P
    
72. $ x7 l7 G4 g' h& f7 e8 }
    
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 14 b( ~* Z4 W, m2 ^! K8 _7 F
    
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈; d, n; Q' M# r' z
    
75.                      stack_ptr = stack_ptr + 1;2 \5 B\" _' u% o- c5 t0 y( B
    
76.                      m = tree_nodeson(n);
    1 n& j5 ?9 a# S  q) Q$ j' V* d/ [
77.                      stack(stack_ptr) = m;
    ( f0 u8 W/ _* s3 U
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    ' s* p  g' ]5 T1 U/ R
79.               elseif tree_nodeneighbor(n) ~= 08 H0 C# J2 N9 T' q, Q1 K
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈: o4 t( [) I$ m7 `\" p: O& B8 ]9 K
    
81.                      m = tree_nodeneighbor(n);  z5 F* x4 k- b
    
82.                      stack(stack_ptr) = m;' f( ~1 U1 E; E4 A8 t3 P% Z
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    - V2 O. c: O# W  e
84.               else* X! r) r% ~) k
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    - w% B9 W9 @3 c. s
86.                      stack_ptr = stack_ptr - 1;
    & ?1 W2 j( O* C4 G+ h; y
87.                      m = stack(stack_ptr);
    . j/ A$ d* `' v# x
88.                      nodeinstack(m) = nodeinstack(m) + 1;
    4 `# B. L0 }* I0 F! Y+ Q: h
89.               end
    ; ~\" m  E: l/ N* E: c
90.        end

复制代码