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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：2 B7 W3 d. T, n5 H0 @  r2 w
   
2.        tree_nodename：节点名字或序号( t+ D' n- K1 c0 _, C- b4 n
   
3.        tree_nodevalue：节点对应的值5 [+ C) Y5 c9 k$ ?
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空  f6 P$ A' M: c0 |7 C: c
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   8 P' M% m# B& M6 l4 h
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空2 ]& U% r& F. Z1 `2 w0 R; P
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。( V7 E7 {! C! D5 z( w' w: n* K
   
8. 
   $ t6 I9 f; E\" C2 }( V+ `+ I
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。. @9 o& a1 G1 E* L$ s6 ^
   
10. 
    : {! w\" ^3 p& G/ U* c
11.        %matlab源程序! }6 I9 q3 Z- D5 Z
    
12.        %输入：树的深度、树的广度、搜索的值
    8 h4 e3 @, G4 {, W: T; J0 s\" k
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空) z+ |- v6 Y: P( R' p6 N! Z' P
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)7 r9 `\" q9 d6 B) i: `
    
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    . B6 D8 Y2 w/ t4 E2 q+ ~
16.        node_num = 0;
    # u' p! ~5 A+ v# J
17.        for n= 0 : (tree_depth-1)+ E# Q# V4 U+ B! I/ n- j% M0 u0 R
    
18.               node_num = node_num + tree_width ^ n;
    5 R* X2 a& f$ f! J\" x2 @
19.        end
    \" |$ \9 \9 ]% o/ w6 f. f+ s
20. 
    ) ?1 Z4 }2 F# W! v
21.        %为树的存储空间赋值
    0 n4 V6 W9 }* [; X! q\" I
22.        %node name，按照广度优先为节点排号# w6 H& I7 M; Y7 o
    
23.        tree_nodename = (1 : node_num);
    1 _9 @' V8 t! c
24.        %node value4 w+ F( ^7 N5 A3 \# Y: T0 ]\" R
    
25.        tree_nodevalue = rand(1 : node_num);
    , a$ n: a* v+ C; O
26.        %node father and son
    - J' L9 J: D- u$ h% Y! B
27.        tree_nodefather(1) = 0;) j9 ^. h8 o6 E\" _/ f3 \
    
28.        tree_nodeson = zeros(1, node_num);
    + b3 C# B7 G5 }0 }
29.        n = 2;
    9 T. D( f* r9 Y! G* C- d
30.        k = 1;
    & `, w, t# E2 v
31.        while n <= node_num% ^7 u( e2 {1 c3 W
    
32.               for m = 1 : tree_width/ k* z( v9 A+ P1 d4 d3 ^
    
33.                      tree_nodefather(n) = k;: o, q( c! z) {\" m
    
34.                      if m==1; d% @4 ^( O) d0 M: C1 w
    
35.                             tree_nodeson(k) = n;  p, z9 t' U$ e6 z! J; z5 f
    
36.                      end
    \" ]2 }* L0 Y/ w8 [! Y1 h: _
37.                      n = n + 1;- F/ d* R6 _8 q7 c0 T
    
38.               end2 J/ ^! h9 ^& ~\" [\" N. M
    
39.               k = k + 1;( z7 x5 q' ~1 C5 _. e/ }$ F$ r
    
40.        end
    % t1 j\" w; m  N0 b
41.        %node neighbor9 m8 M0 J+ B1 `5 |% t- G
    
42.        tree_nodeneighbor(1) = 0;
    $ N3 P7 x6 l4 q/ r$ m
43.        n = 2;
    ! d  D$ H! [/ C7 V
44.        while n <= node_num
    3 x3 g  q; L/ X8 q
45.               for m = 1 : tree_width
    & b& n, q2 P# l- t7 Z
46.                      if m ==tree_width
    & C2 M. o8 y; q
47.                             tree_nodeneighbor(n) = 0;. f! n. L+ |) s! s\" f
    
48.                      else
    * p* e/ _% w0 {# x4 g
49.                             tree_nodeneighbor(n) = n + 1;5 u# {- p( k# y0 w& E5 y# H
    
50.                      end
    ( w: q* ?3 U8 P. ~+ K
51.                      n = n + 1;- k  v& ?8 K( P8 g& d4 C
    
52.               end
    / H5 ~9 n5 M: `5 B$ @2 w0 g
53.        end) n' B1 D. B1 ?/ U& _% ]' R
    
54. 
    % X9 e3 R\" j* B  a2 |$ t
55.        %下面是有效程序段，用栈实现* t' k* k7 }# U
    
56.        stack = zeros(1, tree_depth);
    5 _/ y1 f! ]- i. o* l
57.        nodeinstack = zeros(1, node_num);
    ) r% z# w! _4 d! O  O/ o
58.        stack_ptr = 1;
    # D. m5 f& _; X( i3 ^3 {7 p
59.        stack(1) = 1;4 ?* |8 c- F2 }4 C- Z* O( U& E
    
60.        nodeinstack(1) = 1;
    4 M4 U, S* y( L, \6 o9 X# q; \
61.        valueintree = seek_value;
    . p, I& I1 t* Z8 }6 P! p
62.        nodeintree = 0;
    . y2 r* A1 g; y5 h
63. & ]  w1 X& V5 o
    
64.        while stack_ptr > 0
    ( a( G- {# G4 B8 \1 K
65.               n = stack(stack_ptr);6 c$ U1 \  _9 l% E8 l
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-34 p# {- N$ m) l. {
    
67.               %如果搜索到值，返回
    ; e0 f; E3 _, W- V2 t6 U! H
68.                      valueintree = tree_nodevalue(n);
    5 f! P7 ~! f/ N! G
69.                      nodeintree = tree_nodename(n);0 P0 r+ k5 U7 g$ g
    
70.                      break;1 t/ z( `; z. J7 T7 i
    
71.               end: c\" T/ P$ m  S+ ~
    
72. - y+ o! B$ }, G9 N3 d1 x! s3 B
    
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 19 d- ~( e  z* e3 Z2 G+ U
    
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    ; C8 V' A, H5 h
75.                      stack_ptr = stack_ptr + 1;6 _+ Z; t8 s- }! I% d\" [0 ^3 |. H: O
    
76.                      m = tree_nodeson(n);
    , Y5 ]6 k$ z2 Q* z% ~! a! y: ], e4 n9 L
77.                      stack(stack_ptr) = m;: x0 R0 j6 j  @9 ^2 G
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;  @* V\" z8 @+ N\" j* n
    
79.               elseif tree_nodeneighbor(n) ~= 0
    1 o- F% q: `( c. O9 T; S( M7 d
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    8 I6 S3 i; q0 u- T: k
81.                      m = tree_nodeneighbor(n);7 i. U( f  C8 P) B  x  b; |
    
82.                      stack(stack_ptr) = m;\" L8 r. r. r% o7 k3 p
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    \" {3 L: A1 W- m+ g  e
84.               else, I7 C: A& C: Y+ g8 C; |/ O& n4 l8 O
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一, E$ Y( w1 D- U% l, j% Z6 b4 @* @2 F
    
86.                      stack_ptr = stack_ptr - 1;
    , p) y3 L  f2 A% T7 j; P
87.                      m = stack(stack_ptr);6 ?) F# D- z% d7 g4 r5 p1 d
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;
    7 l9 U7 a; s* r1 l# n, O
89.               end
    7 c, q# a4 S! Y2 S. V8 l
90.        end

复制代码