두 갈래로 나무 노드 찾기

7919 단어
요약: 귀속과 비귀속의 사고방식을 제공하여 두 갈래로 나뭇잎의 수, 노드의 수를 조회한다.주의해야 할 시비귀속의 사고방식은 하나의 창고로 귀속을 모의하고 해당하는 노드를 보존하는 것이다.
#include "stdafx.h"
#include "stdlib.h"
#include "malloc.h"
typedef  struct TreeRecord *Position;
struct TreeRecord 
{
    int Element;
    Position Left;
    Position Right;
};
Position Insert(Position T,int X)
{
    if (T == NULL)
    {
        T = (Position)malloc(sizeof(TreeRecord));
        T->Element = X;
        T->Left = NULL;
        T->Right = NULL;
        return T;
    }

    if (X > T->Element)
        T->Right = Insert(T->Right,X);
    else if (X<T->Element)
        T->Left = Insert(T->Left,X);
    return T;
}
/*int Compute_NodesNumber(Position T)
{
    // 
    int number ;
    if (T == NULL)
    return 0;
        number = 1;
        number += Compute_NodesNumber(T->Right);
        number += Compute_NodesNumber(T->Left);

        return number;
}
*/
int Compute_NodesNumber(Position T)
{
    // 
    int number = 0,top = -1;
    Position Array[100];
    if (T == NULL)
        return 0;
    do
    {
        number++;
        if (T->Left ==NULL)
        {
            if (top == -1)
            break;// root 
            T = Array[top--];
            T = T->Right;
        }
        else
        {
            Array[++top] = T;
            T = T->Left;
        }
    }while(top!=-1);
        do
    {
        number++;
        if (T->Right ==NULL)
        {
            if (top == -1)
            break;// root 
            T = Array[top--];
            T = T->Left;
        }
        else
        {
            Array[++top] = T;
            T = T->Right;
        }
    }while(top!=-1);
    return number-1;// root
}
int Computeleaf(Position T)
{
    // leaf,   
    int number = 0,top = -1;
    Position Array[100];
    if (T == NULL)
        return 0;
    do
    {
        if (T->Left == NULL&&T->Right ==NULL)
        number++;
        if (T->Left ==NULL)
        {
            if (top == -1)
            break;// root 
            T = Array[top--];
            T = T->Right;
        }
        else
        {
            Array[++top] = T;
            T = T->Left;
        }
    }while(top!=-1);

        do
    {
        if (T->Left == NULL&&T->Right ==NULL)
        number++;
        if (T->Right ==NULL)
        {
            if (top == -1)
            break;// root 
            T = Array[top--];
            T = T->Left;
        }
        else
        {
            Array[++top] = T;
            T = T->Right;
        }
    }while(top!=-1);
    return number;// root
    return 0;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int number;
    Position T = NULL;
    for (int i = 1;i<=10;i+=2)
        T = Insert(T,i);
    for (int i = 2;i<=10;i+=2)
        T = Insert(T,i);
    number = Compute_NodesNumber(T);
    number = Computeleaf(T);
    return 0;
}

좋은 웹페이지 즐겨찾기