【資料結構學習日記一】

前言：以下內容涉及到堆疊以及二叉樹的基本知識，

功能介紹：在一個二叉樹中查詢資料，存在回傳該資料的層數，不存在回傳0，

問題分析：

1.用什么方法遍歷一棵樹

2.怎樣計算樹節點的層數

程式框架：

1 int main()
2 {
3     建樹(); 
4     獲取需要查詢的資料();
5     查詢功能();
6     輸出();  
7 }

主函式代碼：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include "stack.h"
 4 
 5 int main()
 6 {
 7     int high;
 8     BiTree tree=(BiTree)malloc(sizeof(Bitnode));//初始化樹節點 
 9     CreateTree(&tree);//創建一顆樹 
10     
11     printf("先序遍歷：");
12     PreOrder(tree);
13     printf("\n");
14     
15     printf("中序遍歷：");
16     InOrder(tree);
17     printf("\n");
18     
19     DataType str;//存放需要查詢的資料 
20     printf("input word of need to find\n");
21     fflush(stdin);
22     scanf("%c",&str);
23     
24     high=Find(tree,str);//進入功能函式 
25     printf("%d",high);    
26 }

這里有一個小問題，如果把" flush(stdin); "去了會發生什么情況呢？

功能函式代碼：

int Find(BiTree root,DataType ch)//root為樹的根，ch為查詢的資料
{
    int high=0,flag=0;//high為累加器，flag為查詢是否成功的標志，成功為1失敗為0 
    struct TreeNode*TreeRoot;//定義一個temp存放出堆疊后的節點,TreeRoot存放根節點 
    struct Dstack s;//定義一個名為s的堆疊 
    TreeRoot=root; 
    InitStack(&s);//堆疊的初始化 
    while(root||!IsEmpty(&s))
    {
        while(root)
        {
            if(ch==root->data)
            {
                flag=1;break;
            }
            //如果等于根節點的右子節點，則重置高度 
            if(root->data=https://www.cnblogs.com/wyjgr/p/=TreeRoot->RChild->data)
            {
                high=1;
                PushStack(&s,root);
            }
            else if(root->data!=ch)
            {
                PushStack(&s,root);    
            }
            high++;
            root=root->LChild;//當前結點指向左節點 
        }
        if(flag==1)
        {
            break;
        }
        //如果堆疊里還有節點，就pop一個節點，然后root=pop出來的節點的右節點 
        if(!IsEmpty(&s))
        {
            root=PopStack(&s);
            root=root->RChild;
        }    
    }
    if(flag==1)
    {
        return high+1;
    }
    else
    {
        return 0;
    }     
}

 輸入用例：

例1：AB..C..

例2：ABC..D..E.F.G..

為了能讓大家理解的更清晰，我把堆疊和樹的實作代碼也附上

堆疊和樹的實作代碼：

  1 /*                                Stack                                        */
  2 
  3 //-----------------------Structure of Stack-------------------------------------
  4 #define Maxsize 20 
  5 #define NIL NULL
  6 typedef struct Dstack* Stack;//定義Stack為 struct Dstack的指標型別 
  7 typedef struct TreeNode* ElementType; // ElementType為字符型別 
  8 struct Dstack
  9 {
 10     ElementType Data[Maxsize];
 11     int Top;
 12 }S;
 13 //--------------------InitStack Structure of Stack------------------------------
 14 int InitStack(Stack p)
 15 {    
 16     p->Top=-1;
 17     int i;
 18     for(i=0;i<Maxsize;i++)
 19     {
 20         p->Data[i]=NIL;
 21     }
 22 }
 23 //--------------------PushStack Structure of Stack------------------------------
 24 int PushStack(Stack Ptrs,ElementType item)
 25 {
 26     if(Ptrs->Top==Maxsize)
 27     {
 28         printf("堆疊滿了");return 0;
 29     }else if(item==NULL)
 30     {
 31         return 0;
 32     } 
 33     Ptrs->Data[++(Ptrs->Top)]=item;
 34     return 1;
 35 }
 36 //--------------------PopStack Structure of Stack-------------------------------
 37 ElementType PopStack(Stack Ptrs)
 38 {
 39         if(Ptrs->Top==-1)
 40         {
 41             printf("堆疊1空了");return NULL;
 42         }
 43         return(Ptrs->Data[Ptrs->Top--]);    
 44 }
 45 //--------------------IsEmpty Structure of Stack--------------------------------
 46 bool IsEmpty(Stack Ptrs)
 47 {
 48     if(Ptrs->Top==-1)
 49     {
 50         return true;
 51     }
 52     else
 53     {
 54         return false;
 55     }
 56 }
 57 /*                              End Stack                                     */
 58 
 59 //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 60 //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 61 //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 62 
 63 /*                                Tree                                        */
 64 
 65 //-----------------------Structure of Tree--------------------------------------
 66   
 67 typedef char DataType;
 68 typedef struct TreeNode {
 69     DataType data;
 70     struct TreeNode *LChild;
 71     struct TreeNode *RChild;
 72 }Bitnode, *BiTree;
 73 //-----------------------Create Function of Tree-------------------------------- 
 74 void CreateTree(BiTree *t)
 75 {
 76     DataType ch;
 77     ch=getchar();
 78     if(ch!='.'){
 79          (*t)=(BiTree)malloc(sizeof(Bitnode));
 80          (*t)->LChild=(*t)->RChild=NULL;
 81         (*t)->data=https://www.cnblogs.com/wyjgr/p/ch;
 82         CreateTree(&((*t)->LChild));
 83         CreateTree(&((*t)->RChild));
 84     }else
 85     {
 86         (*t)=NULL;
 87     }
 88 }
 89 //-----------------------PreOrder Function of Tree------------------------------
 90 void PreOrder(BiTree root)
 91 {
 92     if ( root!=NULL )
 93     {
 94         printf("%c  ",root->data);//訪問根結點
 95         PreOrder(root->LChild);
 96         PreOrder(root->RChild); 
 97     }     
 98 }
 99 //-----------------------InOrder Function of Tree-------------------------------
100 void InOrder(BiTree root)
101 {
102     if ( root!=NULL )
103     {
104         PreOrder(root->LChild);
105         printf("%c  ",root->data);//訪問根結點
106         PreOrder(root->RChild); 
107     }     
108 }
109 /*                              End Tree                                      */
110 //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
111 //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
112 //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

例

標籤：其他

上一篇：題解——八數碼難題

下一篇：【資料結構】思維導圖