初阶数据结构【TOP】- 12.普通二叉树的介绍 - 2. (细致,保姆~~!)

---

前言

本篇文章接续上一篇普通二叉树 - 1 , 会涉及 : 二叉树节点个数相关问题 , 二叉树节点高度.

---

一、二叉树节点个数相关问题

● 求普通二叉树的节点

对于普通二叉树 , 节点间父子关系不会像特殊二叉树一样有规律 , 对于这样的问题我们一般都是用递归来解决问题!

如以下树 :

利用递归思想:

★ 求总节点的个数问题可以拆解成求 : 左子树 + 右子树 + 根(1) .

★ 左子树可以拆解成 : 左子树 + 右子树 + 根(1).

★ 右子树可以拆解成 : 左子树 + 右子树 + 根(1).

这样不断地拆解 , 大问题逐渐化解为小问题 .

代码:

//求总节点个数
int NodeNumber(OBTree* tree)
{if (tree == NULL)return 0;return NodeNumber(tree->Left) + NodeNumber(tree->Right) + 1;}

看似代码很简单 ,这里笔者给出递归思考图 .

● 求叶子节点的个数

叶子节点 : 度为 0 的节点 . 具体概念笔者前几篇有介绍 .

代码:

//求叶子节点的个数
int LeafNodeNumber(OBTree* tree)
{if (tree == NULL)return 0;if (tree->Left == NULL && tree->Right == NULL)return 1;return LeafNodeNumber(tree->Left) + LeafNodeNumber(tree->Right);
}

● 求二叉树第 K 层节点的个数

★ 分析

要求求第3层的节点个数 , 那么利用递归的思想 , 相对于节点的第一层来说就是求第三层的节点个数 , 但相对节点的第二层来说就是求第二层的节点的个数 , 相对第三层来说就是求本层的节点个数 , 此时 k == 1 ,那么就开始执行归 .

★ 遍历顺序 : 左子树 , 右子树 .

★ 代码

求第 k 层节点个数
int Node_K_Num(OBTree* tree , int k)
{if (tree == NULL)return 0;if (k == 1)return 1;return Node_K_Num(tree->Left , k- 1) + Node_K_Num(tree->Right, k -1);
}

---

二、 二叉树节点高度(特殊)

如以上树 , 我们可以清楚的看出来本树的高度是 4 , 这个 4 是怎么得到的 , 我们做以下分析 .

首先 , 树是由 根 , 子树构成 , 根单独占据树的一层 , 那么 4 = 1 + 3 , 继续往下拆 , 3 = 1 + 2 , 2 = 1 + 1 …

由此发现这就是递归啊 , 递归就可以解决了 .

★ 思路

有了以上思路 , 我们进一步分析 , 看以上树分析得 : 左树的高度为 2 , 右树的高度为 3 , 那么树最终的高度一定是由大树决定的 , 故 ; 3 + 1 = 4 .

★ 规则

▲ 若树为空 , 则高度为 0

▲若树的高度不为空 , 则树的高度为 左 , 右 子树中较大的树 + 1.

★ 正确代码

//求树的高度
int TreeHight(OBTree* tree)
{if (tree == NULL)return 0;//注意必须要记录高度int LeftHight = TreeHight(tree->Left);int RightHight = TreeHight(tree->Right);return LeftHight > RightHight ? LeftHight + 1 : RightHight + 1;
}

★ 错误代码

//求树的高度
int TreeHight(OBTree* tree)
{if (tree == NULL)return 0;//errreturn TreeHight(tree->Left) > TreeHight(tree->Right) ? TreeHight(tree->Left)+1 : TreeHight(tree->Right)+1;
}

第二种写法是不符合的 , 会重复很多次的计算 , 递归的深度特别深 . 因为没有记录值 ,则当计算出该值时,进行其它代码的执行此前计算的值就会被遗忘 ,故需重新计算 . 以下给出分析 :

---

三、 二叉树查找值为 x 的节点

这里我们采用 前序遍历 , 因为 : 当找到该值时 , 就没有必要进行下一轮寻找了 .

//查找值为 x 的节点OBTree* FindNode(OBTree* tree , int x)
{if (tree == NULL)return NULL;if (tree->data == x)return tree;OBTree* sl = FindNode(tree->Left , x);if (sl)return sl;OBTree* sl2 = FindNode(tree->Right , x);if (sl2)return sl2;return NULL;
}

---

四、整体代码

#include <stdio.h>
#include <stdlib.h>typedef int OrdBinTreeDataType;// 普通二叉树的链式声明
typedef struct OrdBinTree
{OrdBinTreeDataType data;struct OrdBinTree* Left;struct OrdBinTree* Right;
}OBTree;//手动造树
OBTree* ByNode(int x)
{OBTree* node = (OBTree*)malloc(sizeof(OBTree));if (node == NULL){perror("malloc fail! ");return NULL;}node->data = x;node->Left = node->Right = NULL;return node;
}OBTree* CreatTree()
{OBTree* node1 = ByNode(1);OBTree* node2 = ByNode(2);OBTree* node3 = ByNode(3);OBTree* node4 = ByNode(4);OBTree* node5 = ByNode(5);OBTree* node6 = ByNode(6);OBTree* node7 = ByNode(7);//连接node1->Left = node2;node1->Right = node4;node2->Left = node3;node4->Left = node5;node4->Right = node6;node5->Right = node7;return node1;}//求总节点个数
int NodeNumber(OBTree* tree)
{if (tree == NULL)return 0;return NodeNumber(tree->Left) + NodeNumber(tree->Right) + 1;}//求叶子节点的个数
int LeafNodeNumber(OBTree* tree)
{if (tree == NULL)return 0;if (tree->Left == NULL && tree->Right == NULL)return 1;return LeafNodeNumber(tree->Left) + LeafNodeNumber(tree->Right);
}求第 k 层节点个数
int Node_K_Num(OBTree* tree , int k)
{if (tree == NULL)return 0;if (k == 1)return 1;return Node_K_Num(tree->Left , k- 1) + Node_K_Num(tree->Right, k -1);
}//求树的高度
int TreeHight(OBTree* tree)
{if (tree == NULL)return 0;//注意必须要记录高度int LeftHight = TreeHight(tree->Left);int RightHight = TreeHight(tree->Right);return LeftHight > RightHight ? LeftHight + 1 : RightHight + 1;
}//查找值为 x 的节点OBTree* FindNode(OBTree* tree , int x)
{if (tree == NULL)return NULL;if (tree->data == x)return tree;OBTree* sl = FindNode(tree->Left , x);if (sl)return sl;OBTree* sl2 = FindNode(tree->Right , x);if (sl2)return sl2;return NULL;
}
int main()
{OBTree* tree = CreatTree();int num1 = NodeNumber(tree);printf("总节点个数  = %d\n", num1);int num2 = LeafNodeNumber(tree);printf("叶子节点个数  = %d\n", num2);printf("请输入 k 的值 >: ");int k = 0;scanf("%d", &k);int num3 = Node_K_Num(tree , k);printf("第 %d 层节点个数 = %d\n", k,num3);int num4 = TreeHight(tree);printf("树的高度  = %d\n", num4);OBTree* find = FindNode(tree , 8);if (find == NULL)printf("未找到该值\n");elseprintf("%d ", find->data);return 0;}

五、总结

以上是对二叉树部分的讲解 , 为基础二叉树部分 , 下篇笔者将会对二叉树的应用进行细致的讲解 , 希望学者持续关注哦 ~