网站改版开发公司,邯郸教育平台网站建设,互联网创业项目网站,做外贸常用的网站有哪些目录
1.手搓二叉树
2.二叉树的遍历
2.1前序、中序以及后序遍历
2.2二叉树的层序遍历
3.二叉树的常见操作
3.1求二叉树节点数量
3.2求二叉树叶子节点数量
3.3求二叉树第k层节点个数
3.3求二叉树的深度
3.4二叉树查找值为x的节点
4.二叉树的销毁 1.手搓二叉树
在学习… 目录
1.手搓二叉树
2.二叉树的遍历
2.1前序、中序以及后序遍历
2.2二叉树的层序遍历
3.二叉树的常见操作
3.1求二叉树节点数量
3.2求二叉树叶子节点数量
3.3求二叉树第k层节点个数
3.3求二叉树的深度
3.4二叉树查找值为x的节点
4.二叉树的销毁 1.手搓二叉树
在学习二叉树的基本操作前需先要创建一棵二叉树然后才能学习其相关的基本操作。由于现在我们对二叉树结构掌握还不够深入为了降低学习成本此处手动快速创建一棵简单的二叉树快速进入二叉树操作学习等二叉树结构了解的差不多时我们反过头再来研究二叉树真正的创建方式。 定义二叉树的节点
typedef int BTDataType;
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType data;
}BTNode;
根据上图的二叉树结构手写二叉树
BTNode* BuyNode(BTDataType data)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));assert(node);node-data data;node-left 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);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;return node1;
}
这样我们就写出了一个简单的二叉树。 2.二叉树的遍历
2.1前序、中序以及后序遍历
学习二叉树结构最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。 按照规则二叉树的遍历有前序/中序/后序的递归结构遍历
前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
由于被访问的结点必是某子树的根所以N(Node、L(Left subtree和R(Right subtree又可解释为 根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。 对于二叉树的遍历代码写起来很简单但是对于初学者来说要理解起来就有点难了这里先给出三种遍历的代码大家可以先看看
前序遍历
void PreOrder(BTNode* root)
{if (root NULL){printf(# );return;}printf(%d , root-data);PreOrder(root-left);PreOrder(root-right);
}
中序遍历
void InOrder(BTNode* root)
{if (root NULL){printf(# );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}
后序遍历
void PostOrder(BTNode* root)
{if (root NULL){printf(# );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}
看完代码后是不是觉得这三种遍历都非常的相似呢?我们在编译器上运行一下三种遍历的代码
int main()
{BTNode* root CreatBinaryTree();PreOrder(root);printf(\n);InOrder(root);printf(\n);PostOrder(root);return 0;
}
运行结果 前序遍历的递归展开图 中序遍历和后续遍历和这图也差不多。 2.2二叉树的层序遍历
二叉树的层序遍历是一种广度优先搜索BFS的方法。它按层级顺序逐层遍历二叉树即从根节点开始先遍历第一层节点然后遍历第二层节点依次类推直到遍历完所有层级。
实现层序遍历的一种常见方法是使用队列。具体思路如下 创建一个空队列并将根节点入队。循环执行以下步骤直到队列为空 出队一个节点将其值存储到结果列表中。若该节点有左孩子则将左孩子入队。若该节点有右孩子则将右孩子入队。 这样当队列为空时遍历过程就完成了结果列表中存储着层序遍历的结果。 下面代码的使用了CSTL中的队列来完成避免了手写队列的麻烦
void LevelOrder(BTNode* root)
{assert(root);queueBTNode* a;a.push(root);while (!a.empty()){BTNode* front a.front();a.pop();printf(%d , front-data);if (front-left){a.push(front-left);}if (front-right){a.push(front-right);}}
}int main()
{BTNode* root CreatBinaryTree();LevelOrder(root);return 0;
}
输出结果 3.二叉树的常见操作
3.1求二叉树节点数量
方法一
定义一个全局变量count然后遍历每一个节点每遍历一个节点count就自加1
代码
int count 0;
void TreeSize1(BTNode* root)
{if (root NULL){return;}count;TreeSize1(root-left);TreeSize1(root-right);
}
int main()
{BTNode* root CreatBinaryTree();count 0;TreeSize1(root);printf(%d\n, count);return 0;
}
方法二
int TreeSize2(BTNode* root)
{if (root NULL){return 0;}return TreeSize2(root-left) TreeSize2(root-right) 1;
}
int main()
{BTNode* root CreatBinaryTree();printf(TreeSize2: %d\n, TreeSize2(root));return 0;
}
首先检查根节点是否为空如果为空说明这是一个空树直接返回0。如果根节点不为空则递归调用自身来计算左子树和右子树的节点数然后将左子树节点数、右子树节点数以及根节点本身1个节点的数量相加最后返回结果。
通过这种递归的方式函数可以计算出二叉树中所有节点的总数。 3.2求二叉树叶子节点数量
具体思路
首先检查根节点是否为空如果为空说明这是一个空树直接返回 0。接着通过判断根节点的左子树和右子树是否都为空来确定当前节点是否为叶子节点。如果是叶子节点返回 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 main()
{BTNode* root CreatBinaryTree();printf(TreeLeafSize: %d\n, TreeLeafSize(root));return 0;
} 3.3求二叉树第k层节点个数
思路
首先检查根节点是否为空如果为空说明这是一个空树直接返回0。如果k等于1说明当前层即为目标层返回1。如果k大于1则递归调用自身来计算左子树和右子树中第k-1层节点的数量并将其相加作为结果返回。
通过这种递归的方式函数可以计算出二叉树中第k层节点的总数。
int TreeKLevel(BTNode* root, int k)
{assert(k 1);if (root NULL) return 0;if (k 1) return 1;return TreeKLevel(root-left, k - 1) TreeKLevel(root-right, k - 1);
}
int main()
{BTNode* root CreatBinaryTree();printf(TreeKLevel: %d\n, TreeKLevel(root, 2));//第2层节点数量printf(TreeKLevel: %d\n, TreeKLevel(root, 3));//第3层节点数量printf(TreeKLevel: %d\n, TreeKLevel(root, 4));//第4层节点数量return 0;
}
函数的递归展开图 3.3求二叉树的深度
int TreeDepth(BTNode* root)
{if (root NULL) return 0;int l TreeDepth(root-left); //左子树的深度int r TreeDepth(root-right); //右子树的深度return (l r ? l : r) 1; //返回左右子树深度的较大值加自身的深度1
}
int main()
{BTNode* root CreatBinaryTree();printf(TreeDepth: %d\n, TreeDepth(root));return 0;
}
首先检查根节点是否为空如果为空说明这是一个空树直接返回深度0。接着函数通过递归调用自身来计算左子树和右子树的深度分别将结果存储在变量l和r中。然后通过比较l和r的大小选择较大的值并将其加1代表当前节点的深度作为整棵二叉树的深度。
通过这种递归的方式函数可以计算出二叉树的深度高度。 3.4二叉树查找值为x的节点
在二叉树查找值为x的节点时尽量使用前序遍历可以提高效率。
BTNode* TreeFind(BTNode* root, BTDataType 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;
}int main()
{BTNode* root CreatBinaryTree();BTNode* ret TreeFind(root, 3);if (ret){printf(找到了%d\n, ret-data);}else{printf(找不到\n);}return 0;
}
首先检查根节点是否为空如果为空说明这是一个空树直接返回NULL。接着函数检查当前节点的数据是否等于目标值x如果等于说明找到了目标节点返回指向当前节点的指针。如果不等于递归调用函数分别在左子树和右子树中查找目标值x如果返回的指针非空说明在子树中找到了目标节点直接返回该指针。如果左右子树都没有找到目标节点则返回NULL。
通过这种递归的方式函数可以在二叉树中查找特定值的节点并返回指向该节点的指针。如果找不到目标值则返回NULL。 4.二叉树的销毁
对于二叉树的销毁我们不能使用先序遍历因为如果使用先序遍历会将二叉树的根节点先销毁掉这样就无法找到根节点的左子树和右子树了如果一定要使用先序遍历那就得先把节点的左子树和右子树先保存下来。但如果使用后序遍历就可以轻松解决了。
采用后序遍历销毁按照左孩子右孩子根节点的顺序销毁一颗二叉树。
void TreeDestory(BTNode* root)
{if (root NULL){return;}TreeDestory(root-left);TreeDestory(root-right);free(root);
}
int main()
{BTNode* root CreatBinaryTree();PreOrder(root);TreeDestory(root);root NULL;
}
