二叉樹的遍歷可以有：先序遍歷、中序遍歷、后序遍歷

先序遍歷：根、左子樹，右子樹

中序遍歷：左子樹、根、右子樹

后序遍歷：左子樹、右子樹、根

下面是我畫圖理解三種遍歷：

二叉樹里都是分為左子樹和右子樹。分治思想：1 將任務(wù)分給2 和 4 ，2又分給 3 和NULL，3又分給 NULL NULL 同樣：4將任務(wù)分給 5 和6 ，5又分給NULL NULL ，6也是分給NULL NULL；

以上就是二叉樹的三種遍歷方法

void PrevOrder(BTNode* root)//先序遍歷
{if(root->data == NULL){printf("NULL");return;}printf("%d",root->data);PrevOrder(root->left);//不為空，就分為左子樹和右子樹PrevOrder(root->right);//
}

下面是我畫的遞歸圖：

二、下面是實現(xiàn)二叉樹的一些計算：

先手動創(chuàng)建和連接結(jié)點，使他成為二叉樹。然后用代碼實現(xiàn)，先序遍歷、中序遍歷、后序遍歷。

typedef int BTDateType;
typedef struct BinaryTreeNode
{BTDateType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyBTNode(BTDateType data)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc error");return;}node->data = data;node->left = node->right = NULL;return node;
}

這是隨便手動連接的結(jié)點，以便于我們測試

接著我們可以寫遍歷順序

//先序遍歷
void PrevOder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%d ", root->data);PrevOder(root->left);PrevOder(root->right);
}//中序遍歷
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}//后序遍歷
void PastOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PastOrder(root->left);PastOrder(root->right);printf("%d ", root->data);
}

從上可以看出，結(jié)果和我們上面自己寫的一樣；

我們將遍歷函數(shù)寫完后，接著就算結(jié)點的數(shù)目：

//求結(jié)點數(shù)目
int TreeSize1(BTNode* root)
{if (root == NULL){return 0;}size++;//全局變量TreeSize1(root->left);TreeSize1(root->right);
}
//求節(jié)點數(shù)目
int TreeSize2(BTNode* root)
{return root == NULL ? 0 :TreeSize2(root->left) + TreeSize2(root->right) + 1;//+1是加根節(jié)點自己
}

求結(jié)點數(shù)，也是分治思想：

從根結(jié)點開始，最后結(jié)點需要匯總到根節(jié)點。要想知道，自己結(jié)點下還有多少結(jié)點，可以向自己的孩子得到；

三、求二叉樹的高度/深度

我以空樹的高度為0；

同樣是分治思想：

//int TreeHeight(BTNode* root)
//{
//    if (root == NULL)
//    {
//        return 0;
//    }
//    //這一種會造成很大的資源浪費
//    return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left)+1 :
//        TreeHeight(root->right)+1;
//}int TreeHeight(BTNode* root)
{if (root == NULL){return 0;}int leftHeight = TreeHeight(root->left); int rightHeight = TreeHeight(root->right);return leftHeight > rightHeight ? leftHeight + 1 :rightHeight + 1;
}

二叉樹的深度大概就是這樣