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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：6 D) A* |# ]! C& T9 }5 R
   
2.        tree_nodename：节点名字或序号
   # k' b* ?0 i% W: q: h( {
3.        tree_nodevalue：节点对应的值
   ) m! r1 d- k; y* I) |
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   - Q7 O$ ^& G* D! X/ }
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   6 s1 R- D1 Y9 B; E- J
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
   + k) \& l3 w5 C- |5 `/ u
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。0 E  N$ j; m* `2 [
   
8. 
   3 K5 a) \. e: |; j0 Y# E  w* u
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。' l0 ^6 n9 {- y1 |1 p& Y2 H
   
10. 
    6 S\" T$ I/ t8 C- Z
11.        %matlab源程序
    4 d2 i5 D: C! N8 H  }; ?4 c3 F
12.        %输入：树的深度、树的广度、搜索的值
    % a, `2 B7 |% r# N
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    3 v9 F+ i; \5 s
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value): M2 S8 r9 ~6 x. M9 Y* H
    
15.        %根据树的深度、节点的儿子数量计算树总的节点个数6 r\" h/ a' |( o& l
    
16.        node_num = 0;  T7 k- x. C/ c1 s* \
    
17.        for n= 0 : (tree_depth-1)+ y4 g# [* g6 O8 O. P: X
    
18.               node_num = node_num + tree_width ^ n;
      J+ A7 J; y2 g3 i
19.        end
    / y- s1 [9 T0 p; G3 z
20. 
      g\" Z: J$ i$ i! n4 X
21.        %为树的存储空间赋值
    . M$ Y/ O: d) [1 r& L9 T
22.        %node name，按照广度优先为节点排号
    ; C1 o% q0 g- N% M
23.        tree_nodename = (1 : node_num);( G- t. W- g+ p- T
    
24.        %node value4 o7 G# P: ?9 e& j7 o+ a
    
25.        tree_nodevalue = rand(1 : node_num);
    6 E, t  J8 `6 d, x\" U
26.        %node father and son
    , Z' M, B\" f- \, y5 a* p
27.        tree_nodefather(1) = 0;
    ( e, [) E2 ~& q1 s
28.        tree_nodeson = zeros(1, node_num);& j8 G5 p( L( c( s
    
29.        n = 2;
    / N! }( f6 c/ w/ U. a# k1 h! R
30.        k = 1;
      P) O8 g1 a0 r, Q
31.        while n <= node_num
    4 m; ^+ _( \, c& z\" T- `
32.               for m = 1 : tree_width
    : w6 x& w9 q% t7 D$ \# ^
33.                      tree_nodefather(n) = k;
    ' E! I- w4 T6 r8 H! _: \, l
34.                      if m==1' j0 c! \) s- G; `
    
35.                             tree_nodeson(k) = n;
    8 _: J8 P) k# J- J* S8 u$ L0 d
36.                      end
    % y  |, V4 |9 s$ t3 \4 ~
37.                      n = n + 1;' F1 N. W0 P% A7 W- q- m3 p
    
38.               end
    \" t+ `7 }. g- R) M\" d: Z( H3 V- f& _
39.               k = k + 1;
    ; n* Q# w3 G8 h  ~% {
40.        end& E2 H/ b( S% y  a. x! i
    
41.        %node neighbor
    0 G( q' ~1 z4 f0 ~\" A6 ^' h: @9 l0 |\" P
42.        tree_nodeneighbor(1) = 0;9 Z! T( S7 I$ S2 L6 S5 }
    
43.        n = 2;; M9 ]. B+ ]0 m$ ~+ Q
    
44.        while n <= node_num% A% p/ }2 n4 d3 z
    
45.               for m = 1 : tree_width8 t( P6 J( k' }3 O1 y6 O
    
46.                      if m ==tree_width1 O/ L$ P) |3 {* B
    
47.                             tree_nodeneighbor(n) = 0;
    ' s& {8 S5 Y# w7 `/ P+ p; W' J
48.                      else3 q( \( x$ ?9 m5 _
    
49.                             tree_nodeneighbor(n) = n + 1;
    ( Z$ b, @3 G/ `/ e. v! k
50.                      end% J6 B, p1 h  Z8 Y
    
51.                      n = n + 1;0 v' X. T# w* h. B2 u
    
52.               end( R5 v6 m: m) e- j
    
53.        end
    % ]/ M3 |: v7 J- P/ s: H& Q( g+ ~
54. 
    ! F1 L* S7 `: C, e8 k
55.        %下面是有效程序段，用栈实现
    & D' p  l- j+ N8 L0 R4 K% N: x0 l( ?9 f
56.        stack = zeros(1, tree_depth);) x: n; U% X. j! f( B
    
57.        nodeinstack = zeros(1, node_num);
    . u% a& \, h  ]4 ~\" N
58.        stack_ptr = 1;
    - Y! h. a' m2 B; i( |: L/ D/ t
59.        stack(1) = 1;
    # B) M1 n  S! v# J
60.        nodeinstack(1) = 1;
    7 I1 k\" F8 o% v4 y/ ?
61.        valueintree = seek_value;2 c! [) c) s# x/ {
    
62.        nodeintree = 0;
    6 T: b; S; A- o$ G* c2 `' g+ O) `
63. 
    9 s2 h\" P; f# K8 k- y3 @8 T* |
64.        while stack_ptr > 0
    & |' J* d. j0 {: u
65.               n = stack(stack_ptr);
    , ^. q5 [5 a/ l2 J6 x$ ?
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    7 X3 W! Q% w9 @) M0 l# G( b
67.               %如果搜索到值，返回\" F- @7 @7 c7 S+ ~7 j* i, o
    
68.                      valueintree = tree_nodevalue(n);
    1 m: P$ J) i1 @% u, H' x
69.                      nodeintree = tree_nodename(n);
      x& w2 ?\" V, u- ]! r
70.                      break;
    ! V) j+ N2 ~& j+ _6 |
71.               end
    7 a$ u& r, F) r; u; ?7 s% h! ]
72. 
    + J( |4 \( j  V6 T# ?
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1+ b6 F9 S# t3 Q6 ?4 w9 o
    
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    ) D% J\" O: ~% |. U/ u; W/ N6 e
75.                      stack_ptr = stack_ptr + 1;
    4 v# l# h( D+ |+ n- c7 }) r
76.                      m = tree_nodeson(n);
    ; B\" p* A& U0 q' K4 u8 C) y
77.                      stack(stack_ptr) = m;% F! J- F1 C9 t. z0 q. X' h
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    - ^1 T6 f; L+ \/ c
79.               elseif tree_nodeneighbor(n) ~= 02 Z1 {1 c8 }- B\" c
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈# A$ [  d$ Q8 K+ w
    
81.                      m = tree_nodeneighbor(n);( ~+ J# I6 E9 d7 C
    
82.                      stack(stack_ptr) = m;
    \" k; N# ]3 [( d9 e' D
83.                      nodeinstack(m) = nodeinstack(m) + 1;# ~4 T+ d( J( d: N, N3 l2 S
    
84.               else7 a6 o$ D; t+ C2 S. W  y
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    \" ?, E/ r9 Z6 F: d) R7 u% ]
86.                      stack_ptr = stack_ptr - 1;
    3 Z2 F! w# {  ]4 c( O* {
87.                      m = stack(stack_ptr);
    ! f$ e& A\" c4 d
88.                      nodeinstack(m) = nodeinstack(m) + 1;
    . }: T7 [! g! ^7 w* S% B7 D: o' H1 A
89.               end- {. Y4 X& \: m$ O
    
90.        end

复制代码