目錄
1.介紹
（1）前序遍歷
（2）定義結構體
（3）前序遍歷實現
（4）中序遍歷實現
（5）二叉樹的節點個數
（6）二叉樹樹葉節點個數
（7）二叉樹的高度
（8）二叉樹節點的開辟
（9）建立一個測試二叉樹
（10）測試二叉樹相關函數的功能
（11）第k層的數據個數
（12）二叉樹里面查找節點
1.介紹
（1）前序遍歷
前序遍歷就是針對于樹根而言的，就是這個樹的樹根是先被我們遍歷的，因為這個二叉樹里面劃分為樹根，左子樹和右子樹，這個前中后表示的就是這三個里面的樹根的訪問順序，樹根先被訪問就是前序遍歷，樹根是第二個被訪問的就是中序遍歷，最后被訪問到就是后序遍歷；
（2）定義結構體
下面看一下這個前序遍歷的具體實現；
首先我們要進行這個結構體的定義，這個結構體就是表示的每一個節點，具體來講就是包括這個節點數據，節點的左節點，節點的右節點；
（3）前序遍歷實現
這個代碼里面的N表示的就是這個位置的節點是不存在的，因為不是所有的節點都存在，就是標準情況下，一個節點應該是有兩個子節點的，一個左節點，一個右節點，但是不可避免的有的節點是沒有左節點，或者是沒有右節點的，這個時候我們不會不打印任何數據，而是使用N代替說明這個位置的節點不存在；
（4）中序遍歷實現
這個就是先訪問左邊的節點，再訪問根節點，最后訪問右邊的節點，沒有字節點的就會打印N代替
（5）二叉樹的節點個數
這個地方是使用的遞歸的方法，如果自己沒有根節點，說明這個二叉樹的節點的個數是0，否則就是用遞歸去進行節點個數的計算；
（6）二叉樹樹葉節點個數
這個也是分為有樹根節點，沒有樹根節點，以及正常的使用遞歸進行計算的情況，這個時候使用遞歸進行計算就不需要加上1，因為上面的加1表示這個要加上樹根節點，但是這個地方計算的是樹葉節點，所以不需要加上1；
（7）二叉樹的高度
這個地方是使用這個leftheight表示這個左子樹的高度，rightheight表示這個右子樹的高度，這個地方其實是可以直接寫到返回值里面的，但是這個地方使用的是遞歸，如果不進行這個臨時變量的定義而是直接寫到這個return里面，這個調用的次數就會增加，放到oj里面運行就不會通過，顯示這個運行時間過長，我們定義兩個中間變量就可以去解決這個問題；
（8）二叉樹節點的開辟
使用malloc函數開辟內存空間，需要包含對應的文件stdlib.h
（9）建立一個測試二叉樹
調用上面的buynode函數進行這個節點開辟，并建立不同的節點之間的連接關系，最后返回第一個節點；
（10）測試二叉樹相關函數的功能
打印輸出這個二叉樹的高度，節點個數，樹葉節點個數進行這個功能的測試；
（11）第k層的數據個數
使用遞歸，把下一層即k-1層的左子樹和右子樹節點數量的和作為這個返回值；
（12）二叉樹里面查找節點
這個里面就是查找某一個特定的節點，這個節點作為返回值，我們定義兩個臨時變量作為左子樹和右子樹的返回值，如果左子樹找到這個節點，我們就可以直接返回，否則的話，我們就需要去右子樹去查找，找到這個節點后作為返回值，如果左子樹，右子樹找不到的話就返回NULL；
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
typedef int btdatatype;
typedef struct binarytreenode
{btdatatype data;struct binarytree* left;struct binarytree* right;
}btnode;void prevorder(btnode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);prevorder(root->left);prevorder(root->right);
}void inorder(btnode* root)
{if (root == NULL){printf("N ");return;}inorder(root->left);printf("%d ", root->data);inorder(root->right);
}int treesize(btnode* root)
{if (root == NULL){return 0;}return treesize(root->left) + treesize(root->right) + 1;
}int leafsize(btnode* root)
{if (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;return leafsize(root->left) + leafsize(root->right);
}int heightsize(btnode* root)
{if (root == NULL)return 0;int leftheight = heightsize(root->left);int rightheight = heightsize(root->right);return leftheight > rightheight ? heightsize(root->left) + 1 : heightsize(root->right) + 1;
}int treesizek(btnode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return treesizek(root->left, k - 1) + treesizek(root->right, k - 1);
}//二叉樹里面查找指定的節點
btnode* treefind(btnode* root, btdatatype x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}btnode* ret1 = treefind(root->left, x);if (ret1){return ret1;}btnode* ret2 = treefind(root->right, x);if (ret2){return ret2;}return NULL;
}btnode* buynode(int x)
{btnode* node = (btnode*)malloc(sizeof(btnode));if (node == NULL){perror("malloc fail");return;}node->data = x;node->left = NULL;node->right = NULL;
}btnode* creattree()
{btnode* node1 = buynode(1);btnode* node2 = buynode(2);btnode* node3 = buynode(3);btnode* node4 = buynode(4);btnode* node5 = buynode(5);btnode* node6 = buynode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}
int main()
{btnode* root = creattree();prevorder(root);printf("\n");inorder(root);printf("\n");int size = treesize(root);printf("treesize：%d\n", size);int size2 = leafsize(root);printf("leafsize：%d\n", size2);int size3 = heightsize(root);printf("heightsize：%d\n", size3);int size4 = treesizek(root,3);printf("treesizek：%d\n", size4);return 0;
})
