以圖判樹c語言,c語言關於樹的算法

本文目錄一覽：

• 1、c語言判斷有向圖G是否是一棵以v0為根的有向樹
• 2、C語言，判斷樹的編程
• 3、平衡二叉樹的判定的c語言算法
• 4、判斷完全二叉樹用C語言編寫
• 5、C語言（關於圖最小生成樹方法）

c語言判斷有向圖G是否是一棵以v0為根的有向樹

遍歷一下算出這棵樹的深度k，然後用公式看看深度和點數之間是否具有點數n=2^k-1的關係，具有就是完全二叉樹，否則不是。

C語言，判斷樹的編程

一般構樹的題都用最小生成樹算法，但鑒於你的這題的特殊性，直接深搜，O(n)的時間複雜度就可以過了

#includecstdio

#includecstring

using namespace std;

bool bo[1100];

int n,m,a[1100][1100];

void search(int x){

for(int i=1;i=a[x][0];i++){//詢問與x相連的每一個點是否染了色

int y=a[x][i];

if(!bo[y]){//如果y沒有被染色，就把y染色，並用y去更新別的節點

bo[y]=1;

search(y);

}

}

}

int main(){

scanf(“%d%d”,n,m);//這裡需要你輸入結點個數和邊數，比如你的那組數據就輸入10 9表示10個點，9條邊

if(mn-1){printf(“NO\n”);return 0;}//如果你的邊數比節點數-1還要小的話，那根本不可能聯成一個整體

for(int i=1;i=m;i++){

int x,y;scanf(“%d%d”,x,y);

a[x][++a[x][0]]=y;//記錄下x這個點可以連到y這個點，下同

a[y][++a[y][0]]=x;

}

memset(bo,0,sizeof(bo));//剛開始時除節點1外沒有一個節點是在這個圖中的，然後從1開始往別的點染色

bo[1]=1;

search(1);

for(int i=1;i=n;i++)

if(!bo[i]){//如果有點沒有被染色就說明不能連成一棵樹

printf(“NO\n”);

return 0;

}

printf(“YES\n”);

return 0;

}

平衡二叉樹的判定的c語言算法

設置一個char a[]來保存輸入的Input 然後遍曆數組a[],直到strlen 根據a[]/刪除平衡平衡二叉樹的結點e，並保持平衡二叉樹的性質。 int

判斷完全二叉樹用C語言編寫

用一個線性表和一個隊列，表存放的是邊集，隊列用於按層次遍歷。程序流程如下

1 初始化空表、空隊；

2 輸入結點數、指定根結點，輸入邊到表中；

3 根結點進隊；

4 將隊首出隊到p；

5 若表為空，返回1（真）。不空則在表中查找第一項等於p的邊i。若找到，將邊i的第二項進隊，從表中刪除邊i。若沒有找到，則返回0（假）。

6 若表為空，返回1（真）。不空則在表中查找第二項等於p的邊i。若找到，將邊i的第一項進隊，從表中刪除邊i。若沒有找到，則返回0（假）。

7 跳到4。

補充提供一個相應的程序代碼如下，你可以試試

#include stdio.h

#define N 1024

void main( )

{

    short list[N][2], queue[N], listLength = 0, front = 0, rear = 0, r, n, i, p;/*1  初始化空表，空隊*/

    char flag;   /*flag是判斷結果標識*/

    scanf(“%d%d”, n, r);    /*2  輸入結點數、指定根結點，輸入邊到表中*/

    for(i = 0; i n – 1; i++)

        scanf(“%d%d”, list[i][0], list[i][1]);

    listLength = n – 1;

    queue[rear++] = r;    /*3  根結點進隊*/

    while(1) {

        p = queue[front++];   /*4  將隊首出隊到p*/

        if(listLength == 0) {    /*5  如果表為空，則返回1（真）*/

            flag = 1;  

            break;

        }

        for(i = 0; i listLength list[i][0] != p; i++);  /*尋找第一項等於p的邊i*/

        if(i == listLength) {    /*如果沒有找到，返回0（假）*/

            flag = 0;

            break;

        }

        queue[rear++] = list[i][1];   /*將邊i的第二項進隊*/

        for(; i listLength – 1; i++)        /*刪除邊i*/

            list[i][0] = list[i + 1][0], list[i][1] = list[i + 1][1];

        listLength–;

if(listLength == 0) {   /*6  若表為空，返回1（真）*/

            flag = 1;

            break;

        }

        for(i = 0; i listLength list[i][1] != p; i++);   /*在表中查找第二項等於p的邊i*/

        if(i == listLength) {    /*如果沒有找到，返回0（假）*/

            flag = 0;

            break;

        }

        queue[rear++] = list[i][0];   /*將邊i的第一項進隊*/

        for(; i listLength – 1; i++)           /*刪除邊i*/

            list[i][0] = list[i + 1][0], list[i][1] = list[i + 1][1];

        listLength–;

    }    /*7  跳到4*/

    if(flag)

        printf(“yes\n”);

    else

        printf(“no\n”);

}

運行結果

C語言（關於圖最小生成樹方法）

/*

鄰接矩陣存儲圖

測試數據

6 10

1 2 6

1 3 1

1 4 5

2 3 5

2 5 3

3 4 5

3 5 6

3 6 4

4 6 2

5 6 6

*/

#include stdio.h

#include limits.h

#define N 100

int p[N], key[N], tb[N][N];

void prim(int v, int n)

{

   int i, j;

   int min;

   for (i = 1; i = n; i++)

   {

       p[i] = v;

       key[i] = tb[v][i];

   }

   key[v] = 0;

   for (i = 2; i = n; i++)

   {

       min = INT_MAX;

       for (j = 1; j = n; j++)

           if (key[j]  0  key[j]  min)

           {

                v = j;

                min = key[j];

           }

       printf(“%d%d “, p[v], v);

       key[v] = 0;

       for (j = 1; j = n; j++)

           if (tb[v][j]  key[j])

              p[j] = v, key[j] = tb[v][j];

   }

}

int main()

{

   int n, m;

   int i, j;

   int u, v, w;

   while (scanf(“%d%d”, n, m))

   {

       for(i = 1; i = n; i++)

       {

           for (j = 1; j = n; j++)

               tb[i][j] = INT_MAX;

       }

       while (m–)

       {

           scanf(“%d%d%d”, u, v, w);

           tb[u][v] = tb[v][u] = w;

       }

       prim(1, n);

       printf(“\n”);

   }

   return 0;

}