本文共 2219 字，大约阅读时间需要 7 分钟。

定义二叉树结构

typedef char BTDataType;typedef struct BinTreeNode{     BTDataType _data;//当前节点值域    struct BinTree* _left;//指向当前节点左孩子    struct BinTree* _right;//指向当前节点右孩子}BTNode,*PBTNode;

遵循某种次序，遍历二叉树中的所有节点，使得每个结点被访问一

若规定VLR分别代表：遍历根节点、遍历根节点的左子树、遍历根节点的右子树，则有：

二叉树的遍历 （递归版本）

//二叉树的前序遍历(根->左->右）void PreOrder(PBTNode pRoot){    if (pRoot)    {        printf("%c ", pRoot->_data);        PreOrder(pRoot->_left);        PreOrder(pRoot->_right);    }} //二叉树的中序遍历(左->根->右)void InOrder(PBTNode pRoot){    if (pRoot)    {        InOrder(pRoot->_left);        printf("%c ", pRoot->_data);        InOrder(pRoot->_right);    }}//二叉树的后序遍历(左->右->根)void PostOrder(PBTNode pRoot){    if (pRoot)    {        PostOrder(pRoot->_left);        PostOrder(pRoot->_right);        printf("%c ", pRoot->_data);    }}

求二叉树节点个数

//求二叉树节点个数int SizeBinTree(PBTNode pRoot){    if (pRoot == NULL)        return 0;    return SizeBinTree(pRoot->_left)+SizeBinTree(pRoot->_right)+1;}

销毁二叉树

//销毁二叉树void DestroyBinTree(PBTNode* pRoot){    assert(pRoot);    if (*pRoot)    {        DestroyBinTree(&(*pRoot)->_left);        DestroyBinTree(&(*pRoot)->_right);        free(*pRoot);        *pRoot = NULL;    }}

求叶子节点的个数

//求叶子节点的个数 int GetLeafCount(PBTNode pRoot){    if (pRoot == NULL)        return 0;    if (pRoot->_left == NULL && pRoot->_right == NULL)        return 1;    return  GetLeafCount(pRoot->_left) + GetLeafCount(pRoot->_right);}

求树的高度

//求树的高度int HeightBinTree(PBTNode pRoot){    int Left_Height = 0;    int Right_Height = 0;    if (pRoot == NULL)        return 0;     Left_Height = HeightBinTree(pRoot->_left);    Right_Height = HeightBinTree(pRoot->_right);    return Left_Height > Right_Height ? Left_Height + 1 : Right_Height + 1;}

二叉树的镜像

//二叉树的镜像（递归版本）void Mirror(PBTNode pRoot){    if (pRoot)    {        PBTNode p = pRoot->_left;        pRoot->_left = pRoot->_right;        pRoot->_right = p;        Mirror(pRoot->_left);        Mirror(pRoot->_right);    }}

求二叉树中第K层节点的个数

//求二叉树中第K层节点的个数int GetKLevel(PBTNode pRoot, int K){    if (pRoot == NULL || K <= 0)    {        return;    }    if (K == 1)        return 1;    return GetKLevel(pRoot->_left,K-1) + GetKLevel(pRoot->_right,K-1);}

二叉树的遍历 (非递归版本)

转载地址：http://ltuoi.baihongyu.com/