简单实现二叉树（链表实现）

接着上一节。我们接着学习二叉树，学习使用链表建立二叉树时，最好把每个子程序的递归展开图，都画一下

前言

在学习二叉树的基本结构前，需先要创建一颗二叉树，然后才能学习其相关的基本操作，由于现在大家二叉树的结构了解的不够深入，为了减低学习成本，这里手动快速创建一颗简单的而二叉树，快速进入二叉树操作学习，等二叉树结了解的差不多时，我们反过头来研究二叉树真正的创建方式

4. 二叉树链式结构的简单实现

4.1创建二叉树

->1.快速手搓二叉树

二叉树图示：

代码实现：

typedef int BTDataType;typedef struct BinaryTreenode
{struct BinaryTreenode* left;struct BinaryTreenode* right; BTDataType data;
}BT;BT* BuyNode(BTDataType x)
{BT* newnode = (BT*)malloc(sizeof(BT));if(NULL == newnode){perror("BuyNode::malloc");return NULL;}newnode->data = x;newnode->left = NULL;newnode->right = NULL;return newnode;
}int main()
{BT* node1 = BuyNode(1);BT* node2 = BuyNode(2);BT* node3 = BuyNode(3);BT* node4 = BuyNode(4);BT* node5 = BuyNode(5);BT* node6 = BuyNode(6);BT* node7 = BuyNode(7);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return 0;
}

创建七个结点使用前六个组成一个二叉树，留一个备用

->2.二叉树的前序，中序，后序遍历

前序：根节点->左子树->右子树

代码实现：

//前序
void PrevOrder(BT* root)
{if (NULL == root){printf("NULL ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}

前序递归展开图：只要有节点它就一定有子节点例如3，他就需要遍历它的两颗空树（NULL），大家可以画一下递归展开图，利于我们理解递归

前序大致的顺序：1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL

测试：

中序：左子树->根节点->右子树

代码实现：

//中续
void InOrder(BT* root)
{if (NULL == root){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

中序递归展开图：

中序顺序：NULL NULL 3 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL 

测试：

后序：左子树->右子树->根

代码实现：

void PostOrder(BT* root)
{if(NULL == root){printf("NULL");return;}PostOrder(root->left);PostOrder(root->right);printf("%d\n", root->data);
}

后续递归展开图：

后序顺序：NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1

测试：

->3.二叉树节点个数

代码实现：

//求二叉树所有节点方法一:
int size = 0; //全局变量
int TreeSize(BT* root)
{//使用静态变量//static int size = 0; 不行！因为初始化一次之后就不能在初始化了，会造成累加if (NULL == root){return;}++size;TreeSize(root->left);TreeSize(root->right);return size;
}方法二:
int TreeSize1(BT* root, int* Size1)
{if (NULL == root){return;}++(*Size1);TreeSize1(root->left, Size1);TreeSize1(root->right, Size1);return *Size1;
}// 方法三 对比以上面两个代码，大大的减少了代码量，使用起来更有效率
int TreeSize3(BT* root)
{return root == NULL ? 0 :TreeSize3(root->left) + TreeSize3(root->right) + 1;
}

方法三递归展开图：

总节点为: 6

测试：

->4.二叉树的高度/深度

代码实现：

int BinaryTreeHeight(BT* root)
{if(root == NULL){return 0;}int lHeight = BinaryTreeHeight(root->lrft);int rHeight = BinaryTreeHeight(root->right);return lHeight > rHeight ? lHeight + 1 : rHeight + 1;
}

递归展开图：

这张图只标记了左子树的递归展开，右子树也是一样的，最后左子树和右子树深度相比将大那个加1输出就可以了

测试：

->5.求二叉树k层的个数

代码实现：

//求k层的个数
int TreeLevelK(BT* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}int leftk = TreeLevelK(root->left, k - 1);int right = TreeLevelK(root->right, k - 1);return leftk + right;
}

递归展开图：

求二叉树第三层的节点个数

测试：

->6.二叉树查找值为x的节点

代码实现：

//二叉树查找值为x的结点
BT* BinaryTreeFind(BT* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;BT* lret = BinaryTreeFind(root->left, x);if (lret)return lret;BT* rret = BinaryTreeFind(root->right, x);if (rret)return rret;return NULL;
}

递归展开图：

测试：

->7.层序遍历

层序遍历是使用队列实现的，这里没有使用递归，这里看我上几节写的队列

将链表的成员换为二叉树的节点，用来存储二叉树的节点，然后利用队列的性质，将二叉树的值层序输出就可以了

//层序遍历
void LevelOrder(BT* root)
{Queue q;QueueInit(&q);if(root)QueuePush(&q, root);printf("LevelOrder: ");while (!QueueEmpty(&q)){BT* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}QueueDestroy(&q);
}

测试：