二叉树的链式实现

目录

一、二叉树的基础操作

二、二叉树代码图解

2.1 遍历

2.2 求大小

2.3 创建与销毁

2.4 与队列结合解决问题

三、二叉树C语言源码汇总

---

二叉树的代码实现运用了函数递归的思想，了解函数递归的知识请见博主的另一篇博客：

http://t.csdnimg.cn/PoMtd

一、二叉树的基础操作

typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data; // 当前结点值域	struct BinaryTreeNode* left; // 指向当前节点左孩子struct BinaryTreeNode* right; // 指向当前节点右孩子
}BTNode;//创建二叉树
BTNode* CreatBinaryTree();
//前序遍历
void PrevOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//结点个数
int	TreeSize(BTNode* root);
//叶子结点个数
int TreeLeafSize(BTNode* root);
//二叉树高度
int TreeHeight(BTNode* root);
//二叉树第k层结点个数
int TreeLevelKSize(BTNode* root, int k);
//二叉树查找值为x的结点
BTNode* TreeFind(BTNode* root, int x);
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* CreateTree(char* a, int* pi);
//二叉树的销毁
void BinaryTreeDestory(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
//层序遍历
void TreeLevelOrder(BTNode* root);

二、二叉树代码图解

2.1 遍历

详见博主的另一篇博客：http://t.csdnimg.cn/YnlIr

2.2 求大小

详见博主的另一篇博客：http://t.csdnimg.cn/Ce2Fs

2.3 创建与销毁

详见博主的另一篇博客：http://t.csdnimg.cn/LXt8P

2.4 与队列结合解决问题

详见博主的另一篇博客：http://t.csdnimg.cn/zbNis

三、二叉树C语言源码汇总

BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}
//手动造树（测试用）
BTNode* CreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);BTNode* node7 = BuyNode(7);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;node5->right = node7;return node1;
}
//前序遍历
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);
}
//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}
//结点个数
int TreeSize(BTNode* root)
{if (root == NULL){return 0;}return TreeSize(root->left) + TreeSize(root->right) + 1;
}
//叶子结点个数
int TreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return TreeLeafSize(root->left) + TreeLeafSize(root->right);}
//二叉树高度
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;
}
//求第K层的节点数目
int TreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}
//查找值为x的节点
BTNode* TreeFind(BTNode* root, int 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;
}
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* CreateTree(char* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc");exit(1);}root->data = a[(*pi)++];root->left = CreateTree(a, pi);root->right = CreateTree(a, pi);return root;
}
//二叉树的销毁
void BinaryTreeDestory(BTNode* root)
{//判空if (root == NULL){return NULL;}//释放左子树BinaryTreeDestory(root->left);//释放右子树BinaryTreeDestory(root->right);//释放本身结点free(root);
}
//层序遍历
void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (QueueEmpty(&q)==false){BTNode* 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);
}
//判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root != NULL){QueuePush(&q, root);}//入队遇到空停止入队while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}QueuePush(&q, front->left);QueuePush(&q, front->right);}//判断后面是否还有非空while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){return false;}}QueueDestroy(&q);return true;
}