二叉樹的基本結構

用指標來指向兩個子樹節點，依次來把節點來連接起來

二叉樹的遍歷（前序，中序，后序）

#include<stdio.h>
#include<stdlib.h>
typedef char btdata;

typedef struct BinaryTreeNode
{
    //指標域
    struct BinaryTreeNode *left;//鏈接左孩子
    struct BinaryTreeNode *right;//鏈接右孩子
    btdata data;//資料域
}btnode;


//開辟節點
btnode* buynode(btdata x)
{
    

    btnode*node=malloc(sizeof(btnode));
    if(node==NULL)//判定是否動態開辟成功
    {
        exit(-1);//沒開辟成功就退出
    }

node->data=x;//鏈接資料
node->left=NULL;//還沒鏈接其他指標就置成空
node->right=NULL;
}


//暴力造一個樹
btnode*creatbinarytree()
{

    btnode*nodeA=buynode('A');
    btnode*nodeB=buynode('B');
    btnode*nodeC=buynode('C');
    btnode*nodeD=buynode('D');
    btnode*nodeE=buynode('E');
    btnode*nodeF=buynode('F');
    nodeA->left=nodeB;
    nodeB->left=nodeD;
    nodeA->right=nodeC;
    nodeC->left=nodeE;
    nodeC->right=nodeF;
    return nodeA;//回傳的是根節點
}

//前序
void preorder(btnode*root)
{
    //如果當前三一個空樹
    if(root==NULL)
    {
        printf("NULL->");
        return ;
    }
//不是一個空樹
printf("%c->",root->data);//先遍歷根，后再遍歷左右
preorder(root->left);//左子樹
preorder(root->right);//右子樹

}

//中序   左根右
void inorder(btnode*root)
{
    //如果當前三一個空樹
    if(root==NULL)
    {
        printf("NULL->");
        return ;
    }
//不是一個空樹

inorder(root->left);//左子樹
printf("%c->",root->data);//根
inorder(root->right);//右子樹
}

//后序   左右根
void postorder(btnode*root)
{
    //如果當前三一個空樹
    if(root==NULL)
    {
        printf("NULL->");
        return ;
    }
//不是一個空樹

postorder(root->left);//左子樹
postorder(root->right);//右子樹
printf("%c->",root->data);//根

}

計算二叉樹的節點的個數

//一.計算節點的個數
//錯誤方法
int binarytreesize(btnode*root)
{
    if(root==NULL)
    {
        return 0;
    }
    static int count=0;//用了static的話，每次呼叫都會在原來的基礎上對count進行++，
    //如果不加static的話，cout在堆疊上開辟，呼叫完就會銷毀
    count++;
    binarytreesize(root->left);
    binarytreesize(root->right);
    return count;//這樣計算出來的結果永遠都是1
}

//正確的做法1.
void binarytreesize2(btnode*root,int*x)//用指標進行操作，這樣每次都是對同一個空間進行操作
{
    if(root==NULL)
    {
        return;
    }
    ++(*x);//對地址進行操作就不會出現static和銷毀的情況了
    binarytreesize2(root->left,x);
    binarytreesize2(root->right,x);
}
//正確的做法2.
int binarytreesize3(btnode*root)
{
    return root==NULL?0:binarytreesize3(root->left)+binarytreesize3(root->right)+1;//把問題分為了左右子樹，和自己，不斷的細分，左右+1
}

//二.計算葉子節點的個數，就是沒有子樹節點的個數，度為0的個數

int binaryleafsize2(btnode*root)//左子樹的葉子節點和右子樹的葉子節點加起來
{
if(root==NULL)//并非一定整個樹都是空，后面遞回可能三左子樹或右子樹是空
{
return 0;
}

    return (root->left==NULL)&&(root->right==NULL)?1:binaryleafsize2(root->left)+binaryleafsize2(root->right);//葉子節點左右都沒有節點，則+1，為葉子就回傳一，不為葉子就繼續把左右子樹的葉子加起來
}

在這里插入代碼片

計算第k層的節點

//三.計算第k層節點的個數
//如，要求第4層，就求的3層的左子樹節點數量加上右子樹第3層的節點

//這里我們用了一個相對距離的概念
int binarytreelevelsize(btnode*root,int k)
{
 if(root==NULL)//沒有節點，就通通回傳0
 {
     return 0;
 }
 if(k<1)
 {
     return 0;
 }
 //走到了這里，就不為空
 else if(k==1)
 {
     return 1;//如果要我們求第一層就回傳1,不用求了
 }
//root不為空，k大于1
//說明root第k層的節點在子樹里面，
//就轉化為了左右子樹的第k-1層節點的數量
//如要求我的第4層，相當于求為左子樹的第三層和右子樹的第3層,
//直到為第一層，本層
return binarytreelevelsize(root->left,k-1)+binarytreelevelsize(root->right,k-1);
}

```c

二叉樹的深度

//計算樹的深度（高度）層次
//我們一般規定第一層為1，空樹就算0,從1開始
//計算深度就是左子樹深度和右子樹深度中大的+1
int binarytreedepth(btnode*root)
{
if(root==NULL)
{
    return 0;
}
//這樣寫會重復計算，因為前面比較的時候已經算出結果了，但因為沒有保存結果，嚴重的浪費了，
//return binarytreedepth(root->left)>binarytreedepth(root->right)?binarytreedepth(root->left)+1:binarytreedepth(root->right)+1;//大的那個+1

//用一個變數來記錄
int leftdepth=binarytreedepth(root->left);//一層一層留一個大的回傳區
int rightdepth=binarytreedepth(root->right);
//相當于后序
return leftdepth>rightdepth?leftdepth+1:rightdepth+1;

}




```c

查找一個節點

//二叉樹中查找值為x的節點
//找到了就回傳他的地址
btnode* binarytreefind(btnode*root,btdata x)
{
//根左右的遍歷
//先找根
if(root==NULL)
{
    return NULL;//回傳null是為了告訴上一層我沒找到
}
if(root->data==x)//找到了
{
    return root;
}
      btnode*leftret=binarytreefind(root->left,x);
      if(leftret)//不為空，也就是左邊找到了
      {
            return leftret;
      }
    btnode*rightret=binarytreefind(root->right,x);
     if(rightret)//沒走上面的就走下面的，右邊找到了
     {
      return rightret;
     }
return NULL;//左邊沒找到，右邊也沒找到
}

test.c

int main()
{
    btnode*root=creatbinarytree();//造一個樹
   // preorder(root);//前序遍歷，根，左子樹，右子樹
    //用分治，：分而治之，大事化小，小事化了
    //如校長想知道學校有多少人，讓10個院報人數，院讓專業老師統計人數，老師叫班長，一步一步化小，
   //inorder(root);
     postorder(root);
     int n1=0;
     binarytreesize2(root, &n1);//把n1地址傳過去，每次都對這個地址進行操作，就沒有銷毀的問題了
     printf("\n");
     printf("n1=%d\n",n1);
     int n2=0;
    printf("n2=%d\n",binarytreesize3(root));
     int leafn=0;;
    printf("leafn=%d\n",leafn);
    printf("leaf2=%d\n",binaryleafsize2(root));
    int n3=0;
    printf("levelk=%d\n",binarytreelevelsize(root,3));
printf("depth=%d\n",binarytreedepth(root));

    return 0;
}