二叉树的三种遍历

二叉树的遍历可以有：先序遍历、中序遍历、后序遍历

先序遍历：根、左子树，右子树

中序遍历：左子树、根、右子树

后序遍历：左子树、右子树、根

下面是我画图理解三种遍历：

二叉树里都是分为左子树和右子树。分治思想：1 将任务分给2 和 4 ，2又分给 3 和NULL，3又分给 NULL NULL 同样：4将任务分给 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);//
}

下面是我画的递归图：

二、下面是实现二叉树的一些计算：

先手动创建和连接结点，使他成为二叉树。然后用代码实现，先序遍历、中序遍历、后序遍历。

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;
}

这是随便手动连接的结点，以便于我们测试

接着我们可以写遍历顺序

//先序遍历
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);
}

从上可以看出，结果和我们上面自己写的一样；

我们将遍历函数写完后，接着就算结点的数目：

//求结点数目
int TreeSize1(BTNode* root)
{if (root == NULL){return 0;}size++;//全局变量TreeSize1(root->left);TreeSize1(root->right);
}
//求节点数目
int TreeSize2(BTNode* root)
{return root == NULL ? 0 :TreeSize2(root->left) + TreeSize2(root->right) + 1;//+1是加根节点自己
}

求结点数，也是分治思想：

从根结点开始，最后结点需要汇总到根节点。要想知道，自己结点下还有多少结点，可以向自己的孩子得到；

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

我以空树的高度为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;
}

二叉树的深度大概就是这样