首先了解一下什么是度:
结点的度:结点所拥有的子树的个数。
叶子结点:度为0的结点。
我们再了解一下什么是深度:
树的深度(高度):树中所有结点的最大层数。
现在我们已经了解到了树的度、深度的概念,下面我们来分别聊聊树的度和深度的计算。
- 叶子结点的计算:
毫无疑问,二叉树的大多树思想思想都是递归,那么在计算度时,该如何利用递归思想呢?对于二叉树每一个元素,都有一个左结点和右结点,无非就是空(即无元素)或非空(即有元素)。那儿问题来了,我的左、右孩子均为空,或者均不为空,或者其中一个为空这三种可能。那我们就可以建立一个函数来实现我们上述的三种选择。传入的参数是结点指针类型的变量。先判断一下当前元素是否为空,如果为空(即无元素),则就返回,如果非空(即有元素),则就判断该结点的左、右孩子空或非空的情况。这里非空(即有元素)的情况要分两种可能。一种是该结点的左、右孩子都为空,则该结点为叶子结点,另一种则是不全为空或者均不为空。
//叶子节点计算函数
int BinaryTree::Leaf(Node *s) {
if (s == nullptr) {
return 0;
}
else if ((s->lchild == nullptr) && (s->rchild == nullptr)) {
return count + 1;
}
else {
count = Leaf(s->lchild) + Leaf(s->rchild); //递归调用Leaf函数
return count;
}
}
- 深度(高度)的计算:
二叉树的深度(高度)计算,就是左子树与右子树的比较,核心思想就是递归调用。先判断当前结点是够为空,如果为空就返回。否则就利用递归的思想调用。那么该如何调用呢?
//二叉树深度计算
int BinaryTree::BinaryTreeDu(Node *s){
if(s==nullptr){
return 0;
}else{
m=BinaryTreeDu(s->lchild);
n=BinaryTreeDu(s->rchild);
if(m>n){
return (m+1);
}else{
return (n+1);
}
}
}
- 二叉树的建立
我们使用输入的方式来建立一个二叉树。如果你看了上面的文字,那你一定知道我们的中心思想就是递归调用。该如何使用递归调用呢?我们每一次输入一个字符的时候都需要判断该字符是否为"#",因为这意味着为空的标志。如果不为空,则就赋值,然后递归调用。注意:建立的函数一定是一个结点类型的指针函数。
//递归建立二叉树函数(Node类型的指针函数,注意建立格式)
Node* BinaryTree::Creat(Node *s) {
char ch;
cin >> ch;
if (ch == '#') s = nullptr;
else {
s = new Node;
s->data = ch;
s->lchild = Creat(s->lchild); //递归调用左子树
s->rchild = Creat(s->rchild); //递归调用右子数
}
return s;
}