诚信企业品牌网站建设,wordpress滑动解锁代码,wordpress中文免费主题下载地址,html网页设计代码作业代码目录 1. 前言2. 二叉树的实现2.1 创建一棵树2.2 前序遍历2.2.1 分析2.2.2 代码实现2.2.3 递归展开图 2.3 中序遍历2.3.1 分析2.3.2 代码实现2.3.3 递归展开图 2.4 后序遍历2.4.1 分析2.4.2 代码实现2.4.3 递归展开图 2.5 求节点个数2.5.1 分析2.5.2 代码实现 2.6 求叶子节点个数… 目录 1. 前言2. 二叉树的实现2.1 创建一棵树2.2 前序遍历2.2.1 分析2.2.2 代码实现2.2.3 递归展开图 2.3 中序遍历2.3.1 分析2.3.2 代码实现2.3.3 递归展开图 2.4 后序遍历2.4.1 分析2.4.2 代码实现2.4.3 递归展开图 2.5 求节点个数2.5.1 分析2.5.2 代码实现 2.6 求叶子节点个数2.6.1 分析2.6.2 代码实现 2.7 求树高度2.7.1 分析2.7.2 代码实现 2.8 求第K层节点的个数2.8.1 分析2.8.2 代码实现 1. 前言
在前面的博客中写了有关二叉树的介绍那这次来写关于用C语言来实现与二叉树有关的一些操作。 与之前链表和顺序表不同的是这里不实现增删查改。
2. 二叉树的实现
2.1 创建一棵树
直接手动创建一棵树也就是直接malloc所有的节点。 直接创建6个节点然后让node1的数据直接是1让node2的数据直接是2依次下去。 然后直接让node1的left node2它的right node4;就按照上面的图来构建。 代码如下
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}TreeNode;TreeNode* CreateTree()
{TreeNode* node1 (TreeNode*)malloc(sizeof(TreeNode));assert(node1);TreeNode* node2 (TreeNode*)malloc(sizeof(TreeNode));assert(node2);TreeNode* node3 (TreeNode*)malloc(sizeof(TreeNode));assert(node3);TreeNode* node4 (TreeNode*)malloc(sizeof(TreeNode));assert(node4);TreeNode* node5 (TreeNode*)malloc(sizeof(TreeNode));assert(node5);TreeNode* node6 (TreeNode*)malloc(sizeof(TreeNode));assert(node6);node1-data 1;node2-data 2;node3-data 3;node4-data 4;node5-data 5;node6-data 6;node1-left node2;node1-right node4;node2-left node3;node2-right NULL;node3-left NULL;node3-right NULL;node4-left node5;node4-right node6;node5-left NULL;node5-right NULL;node6-left NULL;node6-right NULL;
}但是这个代码局限性太大已经是写固定了的代码不好再修改下面这种会好一些。 不用管空。 想要其它形状的可以修改代码做一定的增加或者就行。 代码如下
TreeNode* BuyTreeNode(int x)
{TreeNode* node (TreeNode*)malloc(sizeof(TreeNode));assert(node);node-data x;node-left NULL;node-right NULL;return node;
}TreeNode* CreateTree()
{TreeNode* node1 BuyTreeNode(1);TreeNode* node2 BuyTreeNode(2);TreeNode* node3 BuyTreeNode(3);TreeNode* node4 BuyTreeNode(4);TreeNode* node5 BuyTreeNode(5);TreeNode* node6 BuyTreeNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;return node1;
}2.2 前序遍历
2.2.1 分析
前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。 就实现这颗树的前序遍历。 先根然后左子树再右子树初学时把NULL也带上方便理解。 也就是下面这样。 先访问根然后找左子树左子树又得拆成根和左子树一直到空。使用递归来实现。
2.2.2 代码实现
void PrevOrder(TreeNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-data);PrevOrder(root-left);PrevOrder(root-right);
}结果和分析的一样
2.2.3 递归展开图 2.3 中序遍历
2.3.1 分析
中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。 同样以上面那棵树为例子。 先左子树再根再右子树。 这里遇到根先不是NULL先走它的左子树是空就打印返回。
2.3.2 代码实现
void InOrder(TreeNode* root)
{if (root NULL){printf(N );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}结果与分析的是一样的
2.3.3 递归展开图 2.4 后序遍历
2.4.1 分析
.后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。 同样是以上面那棵树为例子它的后序遍历就是 先访问它的左子树然后右子树最后才是根。 要当左右都为空时才访问第一个节点。
2.4.2 代码实现
void PostOrder(TreeNode* root)
{if (root NULL){printf(N );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}递归展开方式也是一样的
2.4.3 递归展开图 2.5 求节点个数
2.5.1 分析
只要节点不为空就加加然后再调用左子树右子树。 用全局的size每次调用前先置空一些。 局部的使用不了因为不能置空再调用一次就会再上次的基础上累计。 同样是这课树节点数为6。
2.5.2 代码实现
int size 0;
void TreeSize(TreeNode* root)
{if (root NULL)return;size;TreeSize(root-left);TreeSize(root-right);
}int main()
{ TreeNode* root CreateTree();size 0;TreeSize(root);printf(TreeSize:%d\n, size);return 0;
}还有另一种实现把树拆成左子树加右子树加1. 代码如下
int TreeSize(TreeNode* root)
{return root NULL ? 0 :TreeSize(root-left) TreeSize(root-right) 1;
}结果还是一样的。 采用的就是分治法
2.6 求叶子节点个数
2.6.1 分析
先得判断一下树是不是空树不是才能就行进行。 不是空树而且左右节点都为空就是叶子节点就返回1 不是空也不是叶子节点就采用分治树的节点就等于左右叶子节点的和。 同样是这棵树叶子节点就是3.
2.6.2 代码实现 int TreeLeafSize(TreeNode* root)
{// 空 返回0if (root NULL)return 0;// 不是空是叶子 返回1if (root-left NULL root-right NULL)return 1;// 不是空 也不是叶子 分治左右子树叶子之和return TreeLeafSize(root-left) TreeLeafSize(root-right);
}
int main()
{TreeNode* root CreateTree();printf(TreeLeafSize:%d\n, TreeLeafSize(root))return 0;
}
和分析的一样叶子节点个数就是3.
2.7 求树高度
2.7.1 分析
先要判断一下树是不是空树是就为0。 不是空树就要判断一下左子树和右子树那个更高然后高的那个就加1。 同样以这棵树计算这棵树的高度就是3
2.7.2 代码实现
int TreeHeight(TreeNode* root)
{if (root NULL)return 0;int leftHeight TreeHeight(root-left);int rightHeight TreeHeight(root-right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
}int main()
{TreeNode* root CreateTree();printf(TreeHeight:%d\n, TreeHeight(root));return 0;
}int TreeHeight(TreeNode* root)
{if (root NULL)return 0;return fmax(TreeHeight(root-left), TreeHeight(root-right)) 1;
}这里使用fmax返回大的数需要包一个头文件math.h 结果也是一样的。
2.8 求第K层节点的个数
2.8.1 分析
同样采用分治。 如果是空树就返回0 如果不为空k1第一层就返回1 如果不为空且k1,就返回左子树的k-1层加上右子树的k-1层。 同样以这棵树计算k1就说明再第一层的下面。这棵树的第三层的节点数就是第二层的左加第二层的右第二层的左又转化成第一层的左加第一层的右为空就返回0。
2.8.2 代码实现
int TreeLevelK(TreeNode* root, int k)
{assert(k 0);if (root NULL)return 0;if (k 1)return 1;return TreeLevelK(root-left, k - 1) TreeLevelK(root-right, k - 1);
}
int main()
{TreeNode* root CreateTree();printf(TreeLevelK:%d\n, TreeLevelK(root, 3));return 0;
}结果如下 有问题请指出大家一起进步
