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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：, @& E+ @5 V/ W
   
2.        tree_nodename：节点名字或序号
   / f8 k/ s' |% f; l4 ^& {! f; |
3.        tree_nodevalue：节点对应的值
   9 }, y- V3 r! n5 ~
4.        tree_nodefather：节点父亲，如果没有父亲，值为空' ^7 R1 `8 `( r9 n1 C& w$ s2 n1 C\" n
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空' n; I* m2 h8 \\" M0 z5 q
   
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空; K& D; W: O/ z+ N# R9 h' X
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   ! N; K. D. n( Q3 z3 L; i
8. 8 T- R4 h7 O: Z- J1 h
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。\" x2 K9 d, M; ~3 h) _; ~& O' O
   
10. 
    4 ?  j! J4 O$ s' s1 R! U9 \
11.        %matlab源程序
    $ F0 h4 x+ F% A4 z\" v
12.        %输入：树的深度、树的广度、搜索的值
    4 g  w% |9 b. _
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    : K2 C# g+ _7 K  k6 H
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    ' F, Y$ ?2 p\" x: h& y1 H
15.        %根据树的深度、节点的儿子数量计算树总的节点个数) O$ K, C4 G  i( E9 R# A2 ~
    
16.        node_num = 0;
      N: R3 e% |, @  O
17.        for n= 0 : (tree_depth-1)4 M1 X0 P/ A% N' U: b/ j0 n
    
18.               node_num = node_num + tree_width ^ n;
    ' P\" Z  }% E4 k; a- l+ p5 [
19.        end
    1 I8 f! }* _: P+ V: _
20. 
    ; r2 S5 y. w& }7 t0 J) I- K
21.        %为树的存储空间赋值, Q' F+ L7 [; ~
    
22.        %node name，按照广度优先为节点排号
    ! n( r! m' K. @+ e
23.        tree_nodename = (1 : node_num);5 ~8 Z3 p: L+ b' }9 K2 E/ T2 b
    
24.        %node value
    ; x; |1 Q1 X& u\" S, _- M6 j
25.        tree_nodevalue = rand(1 : node_num);
    : `# P5 s& F- k
26.        %node father and son$ ~1 E5 ~7 A& X: c) }
    
27.        tree_nodefather(1) = 0;8 m5 S! r\" G$ d8 E. v: X
    
28.        tree_nodeson = zeros(1, node_num);
    + [( E\" ]# D! m$ }* W3 f+ q( b
29.        n = 2;
    - o9 P( N5 `. z1 J7 Q
30.        k = 1;# j' h0 o2 L- ]# U2 X# B
    
31.        while n <= node_num
    & A\" \9 b$ I( B! u
32.               for m = 1 : tree_width( `8 X, _# R4 s; P& L  s
    
33.                      tree_nodefather(n) = k;
    - `6 t% [\" z6 T4 H/ k+ `; Y
34.                      if m==17 X3 w% k8 u' I' d& w: {; v* B
    
35.                             tree_nodeson(k) = n;
    : y, l+ G  h9 b  `
36.                      end7 b% o$ T0 l$ A1 f* L4 T/ n  e+ s
    
37.                      n = n + 1;* P% ~. d4 B0 M
    
38.               end
    6 R) H5 x4 l# h+ e3 E$ g
39.               k = k + 1;
    , y% g; T0 \4 |- @
40.        end
    3 |: E# J6 p$ T$ m/ H
41.        %node neighbor
    : P7 W0 D5 \' B- A3 U
42.        tree_nodeneighbor(1) = 0;\" b7 _8 r' Z! u- k; A3 y
    
43.        n = 2;\" m; B& u6 C6 a' \
    
44.        while n <= node_num( A/ X, D& \, _( I5 i: Q: Q; r
    
45.               for m = 1 : tree_width0 v6 [2 W3 U. w3 ~: e
    
46.                      if m ==tree_width
    \" F1 q\" ]8 ]5 [1 v% x
47.                             tree_nodeneighbor(n) = 0;
    * M# L, ~- h9 [- H
48.                      else
    9 J; L' R2 N\" a4 Q2 X9 N# U
49.                             tree_nodeneighbor(n) = n + 1;
    9 k! j) a1 C$ j, R9 Z( v
50.                      end# s- T. L0 }4 s7 q1 w
    
51.                      n = n + 1;
    8 j9 @: B1 T) K: s\" _1 w; {- ^9 Q
52.               end$ W5 k& l- U+ |4 @
    
53.        end. [4 |) ]8 f; j
    
54. 2 P: ~; e6 p% z4 w) q$ F
    
55.        %下面是有效程序段，用栈实现' {3 k6 t* F* J+ k( p
    
56.        stack = zeros(1, tree_depth);
    ; D6 {4 b# R# ?! _5 z. j9 u
57.        nodeinstack = zeros(1, node_num);
    / c! h: _6 x7 }( j- X; ?1 b
58.        stack_ptr = 1;
    5 }5 L4 ~. z/ y7 Q- G2 S
59.        stack(1) = 1;
    ! P! i' y+ Y% Q
60.        nodeinstack(1) = 1;% n8 J4 m' W5 {, a
    
61.        valueintree = seek_value;/ J1 ^\" h3 _/ s5 s( C$ l
    
62.        nodeintree = 0;
    \" g; H\" m; [& T! @( A$ F
63. 
    . v' j$ N, Z$ z7 g$ O
64.        while stack_ptr > 0
    2 j% O- v  Z# {9 b4 M( E( u' r
65.               n = stack(stack_ptr);6 z2 u, m+ Y+ F, m; S- v
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3. T, o' c9 {6 J/ u
    
67.               %如果搜索到值，返回
    5 b0 `0 ~. g* l\" ~
68.                      valueintree = tree_nodevalue(n);
    7 F& \3 {; }9 H0 ]. N! a; P
69.                      nodeintree = tree_nodename(n);
    4 ]8 @9 }6 i+ T5 a; j- `* a
70.                      break;\" p, h# X: R: u/ Z
    
71.               end
    & o1 K! F) }. e- z% j
72. 
    / Y' C* i4 ]: L7 B
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    2 P/ }# J9 M\" `/ l
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    5 y& @* {2 k* T& I/ {, A
75.                      stack_ptr = stack_ptr + 1;% k2 f. e3 ?, A' @3 u% ]! E
    
76.                      m = tree_nodeson(n);
    % S8 h* E2 X( q& ^
77.                      stack(stack_ptr) = m;) }4 }% O+ K; ?0 R
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;) h% }, z/ P) `/ _
    
79.               elseif tree_nodeneighbor(n) ~= 0: K  z' A4 K# Z; I
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈8 u% O5 u- K, q$ i, n
    
81.                      m = tree_nodeneighbor(n);
    9 z2 w6 o  y7 o, ^) U$ K
82.                      stack(stack_ptr) = m;
    ! `% G5 a4 ^. @* A; ^
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    . A# O9 t: @* p4 b( b. ?
84.               else
    8 f' T3 b2 V, j/ ~$ V  e$ N
85.               %再否则，出栈，然后将父亲节点的入栈次数加一: W! ]+ O# J8 O* G/ t
    
86.                      stack_ptr = stack_ptr - 1;* e0 Q' B; A' s( k$ _& `% u
    
87.                      m = stack(stack_ptr);  Y* |( ~0 |- N* K
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;
    ( M  U' [) |7 g\" a
89.               end
    . N4 _. `, \) R: A% l
90.        end

复制代码