3.1求二叉树节点数量

在学习二叉树的基本操作前需先要创建一棵二叉树然后才能学习其相关的基本操作。

由于现在我们对二叉树结构掌握还不够深入为了降低学习成本此处手动快速创建一棵简单的二叉树快速进入二叉树操作学习等二叉树结构了解的差不多时我们反过头再来研究二叉树真正的创建方式。

typedef

(BTNode*)malloc(sizeof(BTNode));assert(node);node-data

data;node-left

学习二叉树结构最简单的方式就是遍历。

所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作一次。

访问结点所做的操作依赖于具体的应用问题。

遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。

前序遍历(Preorder

亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

中序遍历(Inorder

Traversal)——访问根结点的操作发生在遍历其左右子树之中间。

后序遍历(Postorder

Traversal)——访问根结点的操作发生在遍历其左右子树之后。

subtree和R(Right

根、根的左子树和根的右子树。

NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

对于二叉树的遍历代码写起来很简单但是对于初学者来说要理解起来就有点难了这里先给出三种遍历的代码大家可以先看看

前序遍历

root-data);PreOrder(root-left);PreOrder(root-right);

中序遍历

);return;}InOrder(root-left);printf(%d

root-data);InOrder(root-right);

后序遍历

);return;}PostOrder(root-left);PostOrder(root-right);printf(%d

root-data);

看完代码后是不是觉得这三种遍历都非常的相似呢?我们在编译器上运行一下三种遍历的代码

int

CreatBinaryTree();PreOrder(root);printf(\n);InOrder(root);printf(\n);PostOrder(root);return

运行结果

二叉树的层序遍历是一种广度优先搜索BFS的方法。

它按层级顺序逐层遍历二叉树即从根节点开始先遍历第一层节点然后遍历第二层节点依次类推直到遍历完所有层级。

出队一个节点将其值存储到结果列表中。

若该节点有左孩子则将左孩子入队。

若该节点有右孩子则将右孩子入队。

这样当队列为空时遍历过程就完成了结果列表中存储着层序遍历的结果。

void

(front-left){a.push(front-left);}if

(front-right){a.push(front-right);}}

}int

CreatBinaryTree();LevelOrder(root);return

输出结果

定义一个全局变量count然后遍历每一个节点每遍历一个节点count就自加1

int

NULL){return;}count;TreeSize1(root-left);TreeSize1(root-right);

int

CreatBinaryTree();printf(TreeSize2:

%d\n,

首先检查根节点是否为空如果为空说明这是一个空树直接返回0。

如果根节点不为空则递归调用自身来计算左子树和右子树的节点数然后将左子树节点数、右子树节点数以及根节点本身1个节点的数量相加最后返回结果。

3.2求二叉树叶子节点数量

0。

接着通过判断根节点的左子树和右子树是否都为空来确定当前节点是否为叶子节点。

如果是叶子节点返回

1。

如果不是叶子节点递归调用自身来计算左子树和右子树的叶子节点数并将其相加作为结果返回。

int

CreatBinaryTree();printf(TreeLeafSize:

%d\n,

首先检查根节点是否为空如果为空说明这是一个空树直接返回0。

如果k等于1说明当前层即为目标层返回1。

如果k大于1则递归调用自身来计算左子树和右子树中第k-1层节点的数量并将其相加作为结果返回。

int

CreatBinaryTree();printf(TreeKLevel:

%d\n,

2));//第2层节点数量printf(TreeKLevel:

%d\n,

3));//第3层节点数量printf(TreeKLevel:

%d\n,

CreatBinaryTree();printf(TreeDepth:

%d\n,

首先检查根节点是否为空如果为空说明这是一个空树直接返回深度0。

接着函数通过递归调用自身来计算左子树和右子树的深度分别将结果存储在变量l和r中。

然后通过比较l和r的大小选择较大的值并将其加1代表当前节点的深度作为整棵二叉树的深度。

BTNode*

ret-data);}else{printf(找不到\n);}return

首先检查根节点是否为空如果为空说明这是一个空树直接返回NULL。

接着函数检查当前节点的数据是否等于目标值x如果等于说明找到了目标节点返回指向当前节点的指针。

如果不等于递归调用函数分别在左子树和右子树中查找目标值x如果返回的指针非空说明在子树中找到了目标节点直接返回该指针。

如果左右子树都没有找到目标节点则返回NULL。

通过这种递归的方式函数可以在二叉树中查找特定值的节点并返回指向该节点的指针。

如果找不到目标值则返回NULL。

对于二叉树的销毁我们不能使用先序遍历因为如果使用先序遍历会将二叉树的根节点先销毁掉这样就无法找到根节点的左子树和右子树了如果一定要使用先序遍历那就得先把节点的左子树和右子树先保存下来。

但如果使用后序遍历就可以轻松解决了。

void

NULL){return;}TreeDestory(root-left);TreeDestory(root-right);free(root);

int

CreatBinaryTree();PreOrder(root);TreeDestory(root);root

NULL;