数学建模社区-数学中国

标题: 求树的节点个数求法，求助啊！！！ [打印本页]
作者: qiandongdong    时间: 2014-8-20 23:31
标题: 求树的节点个数求法，求助啊！！！
求树的节点个数的求法啊或matlab代码，我是新手，真心编了好久没结果。请前辈们帮帮忙啊~
作者: madio    时间: 2014-8-21 00:16
就是一个遍历树的所有节点的算法，我帮你找到一个
  1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
    " Z6 P; k- x/ \  x. G$ T" f1 J
  2.        tree_nodename：节点名字或序号
    ) Z( u8 Z" y4 E8 _0 K/ Y
  3.        tree_nodevalue：节点对应的值
    % b* O; }' M7 P. H
  4.        tree_nodefather：节点父亲，如果没有父亲，值为空3 _! ^1 c  h$ [9 d( s
  5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空8 @8 d3 K3 [1 S; q! W( R
  6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
    % c8 `: }$ N$ T+ m6 N% {) p
  7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
    7 @0 M- K- R9 c/ r

  8. 4 K0 |' R! Q: {2 x
  9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
    . W. G! i( w! g* E- T

  10. + J( y& u3 m) E  d" r. s& L% P
  11.        %matlab源程序- T5 x& ^6 G/ a) F2 V
  12.        %输入：树的深度、树的广度、搜索的值
    % K6 X+ E$ J$ f% X) V
  13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    ' A5 I. J  ?$ M- c, Y
  14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    0 `4 l) O0 U7 c# I& A
  15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    ! m8 a% [& S/ a" n9 [2 r
  16.        node_num = 0;
    4 H: m6 d7 q0 W$ }' S8 M; C; E
  17.        for n= 0 : (tree_depth-1)" n$ f0 D5 ?: a; a2 L
  18.               node_num = node_num + tree_width ^ n;
    ) H% C5 X; s1 O+ P, K' R3 R
  19.        end3 R" {. @8 v( v) |' ~1 O6 M$ O" Q
  20. % Z6 C9 N* v. p1 z  I# w" b
  21.        %为树的存储空间赋值# Y, S8 \# f; C; Z& ~3 ~" L
  22.        %node name，按照广度优先为节点排号
      }# ^9 X3 F. J4 D. o1 T! Q1 f+ O
  23.        tree_nodename = (1 : node_num);5 ^' f) t, v- V  a3 G; v: E
  24.        %node value
    3 K4 ^# P, P4 U# }
  25.        tree_nodevalue = rand(1 : node_num);
    3 s- y8 x; v: s
  26.        %node father and son
    ' F7 l/ f. d. f8 x2 J, \3 K
  27.        tree_nodefather(1) = 0;2 |" q( K) R  M/ g) |# N
  28.        tree_nodeson = zeros(1, node_num);
    ; L0 `' a$ j# ~: }* j" X. K, q
  29.        n = 2;
    5 X0 g8 R- w4 Y- V* g$ e
  30.        k = 1;7 S6 _- m$ b. b. c
  31.        while n <= node_num+ _* ~. o8 A* d6 B
  32.               for m = 1 : tree_width6 Q. T8 y0 N% A( E9 f
  33.                      tree_nodefather(n) = k;/ `/ C: Y5 G: w5 S6 S6 d
  34.                      if m==1, i/ H6 @+ K: ?
  35.                             tree_nodeson(k) = n;
    : X* _( ], J7 b( T3 k
  36.                      end2 T/ \! P, A; a, C, P0 K3 C$ ]
  37.                      n = n + 1;
    / z/ [4 _* ?) e& _
  38.               end
    ! T8 l9 r1 o- O
  39.               k = k + 1;) w/ t- ]0 r; Z5 V1 f) ^
  40.        end
    ! N) m% z( S6 I
  41.        %node neighbor
    7 G' [' W$ ]8 \( y% |4 ^
  42.        tree_nodeneighbor(1) = 0;# ]2 _4 l' R- ^2 o* B2 _" q9 R: |
  43.        n = 2;
    : [+ d* n. @" t" V, w9 y
  44.        while n <= node_num
    * f; ~1 {: z$ B- P. c; M9 f% K
  45.               for m = 1 : tree_width
    6 E7 x, W, k- G1 V  f
  46.                      if m ==tree_width6 G7 }+ Q3 G4 O  F3 T
  47.                             tree_nodeneighbor(n) = 0;& x# V% U/ w3 `+ i# M9 }3 G
  48.                      else  q2 ~0 w% L% e" R' S
  49.                             tree_nodeneighbor(n) = n + 1;
    . v% b' a; ?. q# r" w
  50.                      end/ C5 c  V6 A: M. k
  51.                      n = n + 1;( A4 n% S" W5 t. y6 x$ G- J$ M
  52.               end3 P- P) S; d# O% M: e+ G5 s
  53.        end
    $ i! {. {$ g4 T( r' W1 Q6 B
  54. & }  o) s; n2 @3 `- M" u
  55.        %下面是有效程序段，用栈实现
    % L7 @6 J9 w- u
  56.        stack = zeros(1, tree_depth);. r5 g! t' r: _( ^  ?. X
  57.        nodeinstack = zeros(1, node_num);
    5 f4 P$ f) B/ F
  58.        stack_ptr = 1;
    ' h# b) w7 B. m3 `+ M) r1 l! m
  59.        stack(1) = 1;
    + |# |: M% m5 k* Y: R
  60.        nodeinstack(1) = 1;) ^7 f" U4 L" t; U7 o$ f; z
  61.        valueintree = seek_value;
    % \2 X- p# G; k( m7 {
  62.        nodeintree = 0;
    # ?7 z" j! B8 c; [
  63. - G" }8 p! }. o. T( m2 y0 g
  64.        while stack_ptr > 0
    ; }; b& ^; v8 x3 l1 v% i4 l
  65.               n = stack(stack_ptr);) _: _0 l9 n9 J
  66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    , j" p! I. I! E" [$ v9 s4 Z
  67.               %如果搜索到值，返回
    & O" B% q; W7 S: ?2 @) E
  68.                      valueintree = tree_nodevalue(n);2 l8 Y; C$ V4 f! q
  69.                      nodeintree = tree_nodename(n);
    * N# [) I6 C* @) F
  70.                      break;
    . b% ~3 b' @9 N+ s# {& n3 c9 {
  71.               end
    7 v4 W( G% p& F& W- I
  72. $ F7 w0 C" N. E  K1 q( |
  73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1( B9 \2 G" S0 D" j( |% D) w
  74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    2 E( e0 h& l, I( B  |
  75.                      stack_ptr = stack_ptr + 1;5 b1 k+ r* k' b' Q
  76.                      m = tree_nodeson(n);
    : M9 F* e7 K& \9 M/ k& N
  77.                      stack(stack_ptr) = m;
    + F* v- O' d- i. @1 a: o
  78.                      nodeinstack(m) = nodeinstack(m) + 1;
    1 O4 G7 j* `+ j. G" B; l# [
  79.               elseif tree_nodeneighbor(n) ~= 0
    7 u' |) y- U  }, |
  80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    / \  Q, a  }, U! l5 @/ N# B
  81.                      m = tree_nodeneighbor(n);5 z; h  S" C: d- U" `' E( \
  82.                      stack(stack_ptr) = m;
    # i6 L" A! T. n! b" n7 B# F0 O
  83.                      nodeinstack(m) = nodeinstack(m) + 1;3 o8 w* @; C5 N( d
  84.               else
    ; E, {5 }  ]+ t1 f
  85.               %再否则，出栈，然后将父亲节点的入栈次数加一  z' u" r& s% @5 _) V- o
  86.                      stack_ptr = stack_ptr - 1;
    & S! C5 Y, s8 n# w. l. _6 E
  87.                      m = stack(stack_ptr);
    1 d8 A2 c7 B6 A" s5 V( X; D* n
  88.                      nodeinstack(m) = nodeinstack(m) + 1;$ S) }% U6 W  d
  89.               end% s7 E  x( h5 Y: o" J' _6 Z* d
  90.        end
复制代码




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5