ツリー番号

バイナリツリー

バイナリツリーのノード総数

各サブツリーに自分を含めて数を追加し、1

を追加します.

// 버전1 (족보 버전)
Algorithm get_count(node)
  count = 0
  if(node != NULL) then
    count <- 1     // 자신 노드의 개수를 1 추가하고
    count <- count + get_count(node.left()) // 왼쪽 서브트리에서 구해진 외부노드 개수 추가
    count <- count + get_count(node.right())  // 오른쪽 서브트리에서도 구해진 개수 추가
  return count
  
  
  
// 버전2
Algorithm get_count(node)
  if node = NULL then
    return 0
  result <- 1
  result <- result + get_count(node.left())
  result <- result + get_count(node.right())
  return result



// 버전3
Algorthm get_count(node)
  if node == NULL
    return 0
  else
    return 1 + get_count(node.left()) + get_count(node.right())

バイナリツリーの外部ノード数

各サブツリーから求めた外部ノード数を加算すればよい.

外部ノードの場合、1を返すと終了します!

// 버전1
Algorithm get_external(node)
  count <- 0
  if node != NULL then   
    if(node->left == NULL and node->right == NULL)    // external 노드라면 1리턴
      return 1                       
    else                                             // external 노드가 아나라면 왼쪽, 오른쪽으로 부터 카운팅된 노드개수 리턴받음
      count = get_external(node.left()) + get_external(node.right())
  return count                                       // node가 external 노드라면 0이 리턴되고, 아니라면 왼쪽과 오른쪽 서브트리로부터 합산된 노드의 개수를 리턴할 것이다.
 
 
 
// 버전2
Algorthm get_external(node)
 if node == NULL                                // external 노드라면
   return 0
 if node.left() == NULL && node.right() == NULL // 자식 노드 계산할게 없는 경우
   return 1                                    // 자신 노드만을 카운팅
 else                                    // external 노드도 아니고, 자신과 자식 서브트리에 대해 계산할게 모두 존재한다면
   return get_external(node.left()) + get_external(node.right())  // 자신 노드 + 왼쪽 서브트리 + 오른쪽 서브트리 노드 총 개수 
    

バイナリツリーの高さを求める(深さを求める)

サブツリーで、サブツリーの高さの最短値を返し、

を返します.
戻り

高さ値プラス1(自己を含む)戻り

// 버전1 - 족보 버전
Algorithm get_height(node)    
  int height = 0;
  if(node != NULL)
    height = 1 + max( get_height(node.left()), get_height(node.right()) )
  return height;      // node 가 NULL 이라면 0이 리턴되고, 아니라면 왼쪽 오른쪽 서브트리로 부터 계산된 결과값이 리턴
  
  
  
// 버전2 
Algorithm get_height(node)
  left_height = 0;
  right_height = 0;
  if (node.left() != NULL)
    left_height <- get_height(node.left()) + 1;
    right_height <- get_height(node.right()) + 1;
  return left_height > right_height ? : left_height : right_height;

化油器巡回

def eulerTour(v):
	visitLeft(v)	#전위 순회
    if isInternal(v):
    	eulerTour(left(v))
    visitBelow(v)	#중위 순회
    if isInternal(v):
        eulerTour(right(v))
    visitRight(v)	#후위 순회

一般ツリー

日半の木のノードの総数の

を求めます

// 버전1
Algorithm get_count(T,p)
  count = 0
  if p.isExternal() then
    return 1
  else
    count <- 1
    for each q ∈ p.childern() do
      count <- count + get_count(T,q)
  return count 
  
// 버전2
Algorithm get_count(T,p)
  count = 0
  if p != NULL then
    count = 1
    for each ∈ p.childern() do
      count <- count + get_count(T,q)
  return count

日半木の外部ノード数

// 버전1
Algorithm get_external(node)
  count <- 0
  if node.isExternal()
    return 1
  else
    for each child p of node
      count <- count + get_external(p)
  return count

// 버전2
Algorithm get_external(node)
  if node == NULL
    return 0
  if node.isExternal()
    return 1
  else
    count = 0
    for each child v of node
      count <- count + get_external(v)
    return count

日半木の高さ

を得る

// 버전1 (족보 버전)
Algorithm CCC(T, p)
  if p.isExternal() then
    return 0
  else
    h <- 0
    for each q ∈ p.childern() do
      if h < CCC(T,q) then  // 자신의 자식들에 대해 높이의 최댓값 리턴받기 
        h <- CCC(T,q)
    return h + 1 // 자신 노드까지 높이에다 추가해서 리턴한다
  

 // 버전 2
Algorithm get_height(node)
  height = 0;
    if node != NULL then
      for each q ∈ p.childern() do
        if height < get_height(q)
          height = get_height(q)
          height = height + 1
  return height

通常のツリーバイナリツリーで実装

型材ノード位置出力関数

Algorithm sibling(u)
  Create a new pointer of node 
  
  while(tmp != tmp.parent().left())
    print(tmp)
    tmp <- tmp.parent()
    
  while(u != NULL)
    print(u)
    u <- u.right()

検索

親ノード

Algorithm find_parent(u)
  Create a new pointer of node
  
  while(tmp != tmp.parent().left())
    tmp <- tmp.parent()
  
  print(tmp.parent().data)

サブツリーの高さ(=uの深さ)

を求める

Algorithm get_depth(u)
  Create a new pointer of node
  count = 0
  
  while(tmp != root)
  { 
    while(tmp != tmp.parent().left())
      tmp <- tmp.parent()
    
    tmp <- tmp.parent()
    count = count + 1
  }
  return count

Tで後続のシーケンスが実行すると、バイナリツリーは

を実現する.

位、

理由

:後列巡りの特徴は自分の最初の子供から、n番目の子供まで仕事を終え、自分に仕事をしたことです.

Algorithm postOrder(v)  // 실제 이진트리 구현은 중위순회 방식이므로, 알고리즘 이름을 inOrder 로 적어도 상관x 일듯?
  if ㄱv.isExternal()
    postOrder(v.left())
  visit(v)
  if ㄱv.isExternal()
    postOrder(v.right())

Tで前列順が実行すると、バイナリツリーは

を実現する.

も電位巡回で実現されるだけである.ただし,バイナリツリーには順序ペアの順序があるため,一般的な電位巡回方式とは異なりアクセス(処理)順序を指定している.

Algorithm preOrder(v)
  visit(v)    // 자신 방문
  if ㄱv.isExternal()       // for each child w of v 
    preOrder(v.left())      //   preOrder(v) 
  if ㄱv.isExternal()       // => 이렇게 그냥 전위순회로 적으면 무작위로 막 방문할수도 있으니까 왼쪽 먼저 방문하고 오른쪽 방문
    preOrder(v.right())

T中尉巡り
=>は実装できません.

,一般木では中位数の巡回はできないため.