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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   1 D\" V+ x( P  u+ L7 S* Y9 w0 W
2.        tree_nodename：节点名字或序号
   $ @& @1 o: R$ k. g% x4 J9 N
3.        tree_nodevalue：节点对应的值
   ; [/ Z/ d0 x  W9 `* a
4.        tree_nodefather：节点父亲，如果没有父亲，值为空3 O( Y! N5 A5 }' c
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   0 W' F- D. r$ e8 k. {; L& ^
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
   2 K+ b- k. W; J0 R  P# F
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。. W1 s& ]9 z6 N3 y
   
8. 
   * D$ D, E\" \! O4 u% }1 `9 J
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。/ q0 W3 m( q\" x' J0 W/ Y
   
10. 
    ! n1 d( ]7 ~% F' b, Q: r\" b
11.        %matlab源程序
    ' ?; S2 R# L9 X1 X# m
12.        %输入：树的深度、树的广度、搜索的值
    4 J- {0 w) W* y5 {! _& z6 U! v$ k& M
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空) W# d$ H5 Z) o: Y0 p! L
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
      T: W8 Y$ a! ]6 \. t8 l9 Z
15.        %根据树的深度、节点的儿子数量计算树总的节点个数0 J6 O3 g$ [; A( M
    
16.        node_num = 0;6 K) Q  ^8 m' [- Z! i* `5 i4 e
    
17.        for n= 0 : (tree_depth-1)
      H* c# c# u0 q' V# f& Y
18.               node_num = node_num + tree_width ^ n;% v9 c1 C* Y3 \; W, {& e- R, j
    
19.        end1 K5 H1 _# N7 ~\" n/ S
    
20. 
    $ l6 m; M0 \# G( m$ ~5 Q
21.        %为树的存储空间赋值7 }5 F- n  N$ d\" c3 b5 O; V. j7 Q& d
    
22.        %node name，按照广度优先为节点排号8 p4 B# A) y1 D1 V: V& M- w
    
23.        tree_nodename = (1 : node_num);
    ; J8 H( V2 z  U- v% W0 M
24.        %node value
    + `+ C* Q4 [/ x( z. G
25.        tree_nodevalue = rand(1 : node_num);
    : v1 @6 [8 \. \; x; p7 Y
26.        %node father and son/ m\" i* V9 q. z  m! q
    
27.        tree_nodefather(1) = 0;0 k9 s( J1 j1 B+ _: t+ }
    
28.        tree_nodeson = zeros(1, node_num);  ]3 O( i/ V' j/ i2 u! p+ j  R% s
    
29.        n = 2;  k! h: W, k6 |. S. F
    
30.        k = 1;
    & J% j, ^) ]4 n/ v$ g9 J: P  N
31.        while n <= node_num& G% O( X6 y- b
    
32.               for m = 1 : tree_width; I1 j- X) \4 p6 b
    
33.                      tree_nodefather(n) = k;
    3 |; }3 }; P, \- P2 }. j* w
34.                      if m==1
    % y3 |4 d- ^) n4 {* c. g
35.                             tree_nodeson(k) = n;
    5 t% B( @' _& H  u/ N3 x' B) C6 P\" H
36.                      end
    * M0 a. v; S0 U% t' T6 V
37.                      n = n + 1;8 s  s/ w- G( b. ~
    
38.               end; Q! m0 Y0 [( ^1 @
    
39.               k = k + 1;
    $ P; m# n1 A' ^' \
40.        end
    + [5 E- o5 R+ `  l, z0 k8 h
41.        %node neighbor5 b' `$ z( ?0 x+ [; A1 Z5 q
    
42.        tree_nodeneighbor(1) = 0;; }# `2 C7 u- l# F- M
    
43.        n = 2;7 R8 e! O4 B\" ]7 Q, j9 ~\" T0 l' l6 |
    
44.        while n <= node_num
    + a4 m( Q& O4 c7 N4 A. y
45.               for m = 1 : tree_width
    ( B2 G% Y\" X/ N# l+ F! B
46.                      if m ==tree_width9 t+ `% P6 w9 q1 ?6 Z1 p# `5 ~
    
47.                             tree_nodeneighbor(n) = 0;
    # }, }( w0 P1 e% k* A% t
48.                      else
    : X$ o% U! ?) C8 y  k
49.                             tree_nodeneighbor(n) = n + 1;: N0 Z5 X5 i+ X4 x
    
50.                      end( k3 e  O7 J6 Y
    
51.                      n = n + 1;
    ' n9 U- L3 Q3 s5 d' @. b& R
52.               end
    ! k# w$ ~6 k/ E
53.        end
    5 W! g% W! Z) Z$ M9 u\" U
54. ) f( P7 D$ b% q% |
    
55.        %下面是有效程序段，用栈实现2 R, X% I& m: m' W8 h
    
56.        stack = zeros(1, tree_depth);! w* n- G: \; N
    
57.        nodeinstack = zeros(1, node_num);& J. E  s: H* W: _) I( W( U! {
    
58.        stack_ptr = 1;
    3 K5 e% z+ ]% n3 t
59.        stack(1) = 1;
    5 c* ?' \2 U. Y8 N( m
60.        nodeinstack(1) = 1;
    7 B, U7 v( }% _/ k+ w; Z) d0 p; n
61.        valueintree = seek_value;
      z6 P% G, X1 U  O
62.        nodeintree = 0;
    : L) l& u: U, B& _1 b# O
63. 9 Q# }) Y( @' D3 b8 G
    
64.        while stack_ptr > 0
    ' {/ d. f  k2 P% c& O
65.               n = stack(stack_ptr);+ Y0 c3 h- |7 X5 M# T
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    3 {6 b6 I! I1 m) [1 k) R
67.               %如果搜索到值，返回
    5 q4 C) g/ c7 h$ M
68.                      valueintree = tree_nodevalue(n);
    9 Y9 ^% d2 N# q# \! M
69.                      nodeintree = tree_nodename(n);
    ( R5 o' r: N8 J. _: A$ V& t
70.                      break;
    $ c2 u# l\" f; B$ {0 A) t
71.               end
    ' X  b1 l% ^7 f1 u4 {\" ^# U
72. 
    $ ~5 m$ Q: E# Y; Q' U3 z( H
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 15 ]3 B1 Y/ u4 {1 F1 L, z0 A/ m
    
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈7 D% I4 x! o6 C6 n6 t: r  f4 D
    
75.                      stack_ptr = stack_ptr + 1;
    5 E7 K: v1 ~( D, O8 O& J+ d4 |) U
76.                      m = tree_nodeson(n);# W\" n' ~, |! i4 i! _; T8 V
    
77.                      stack(stack_ptr) = m;% d5 h- B\" {; E) `# Z5 Q
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;8 M* Q9 X$ D: T+ c1 ?- B
    
79.               elseif tree_nodeneighbor(n) ~= 0
    \" B- o# m2 E/ a$ ]% y9 G
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈! [6 b: P( v5 a' I' H2 Q8 P9 x
    
81.                      m = tree_nodeneighbor(n);
    ! ~- b3 B\" ?) b9 J\" s% }
82.                      stack(stack_ptr) = m;
    8 H% L& c! E' x# M4 f0 u
83.                      nodeinstack(m) = nodeinstack(m) + 1;2 t' e' v7 i4 A4 F& ~
    
84.               else
    + T7 L( Y; K\" s. |  R1 Z- W
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    * I  B) O: Y' c; |0 [% I
86.                      stack_ptr = stack_ptr - 1;
    : @6 ~6 X# a+ G$ D  a+ E
87.                      m = stack(stack_ptr);, Q5 D( F\" ~5 |, k- o& ?' v1 Y
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;+ h; e9 k9 \+ g$ x( i
    
89.               end* F' `. Q3 C$ q  q
    
90.        end

复制代码