精华内容
下载资源
问答
  • 思路上也没啥的,和求二叉树结点个数或者说求二叉树叶子结点个数思路很像,博主的前几篇博文有讲 Java 实现 // 结点 class Node { int data; Node left = null; Node right = null; } // 二叉树 public class ...

    文章目录

    思路

    思路上也没啥的,和求二叉树结点个数或者说求二叉树叶子结点个数思路很像,博主的前几篇博文有讲

    Java 实现

    // 结点
    class Node {
        int data;
        Node left = null;
        Node right = null;
    }
    
    // 二叉树
    public class BinaryTree {
        // 根结点
        private Node root;
        // 输入的数组
        private int[] arr_in;
        // 输出的数组
        private int[] arr_out;
        // 记录数组下标
        private static int index;
        
        // 初始化
        public BinaryTree(int[] arr) {
            root = new Node();
            this.arr_in = arr;
            arr_out = new int[arr.length];
            index = 0;
        }
    
    // 得到二叉树非叶子结点的个数(递归)
        public int getNonleafCountRecursion(Node r) {
            // 左右两个结点都是 null,此结点必为叶子
            if (r.left == null && r.right == null)
                return 0;
            else
                return getNonleafCount(r.left) + getNonleafCount(r.right) + 1;
        }
        
        // 得到二叉树非叶子结点的个数(非递归)
        public int getNonleafCount(Node r) {
            Stack stack = new Stack();
            Node node = r;
            int nonleaf = 0;
            while (node || !stack.empty()) {
                if (node.left != null || node.right != null) {
                    stack.push(node);
                    nonleaf++;
                    node = node.left;
                }
                else
                    node = stack.pop().right;
            }
            return nonleaf;
        }
    
    展开全文
  • 算法描述:该算法递归去统计结点个数。值得一提的是该系列算法都是统计根结点以下的符和条件的结点的个数进行了加和。免去的设置全局变量和void的类型的函数。​ int CountNodes(LBTree* lbt) { int n = 0; if ...

    很多书上其实都有提到和该算法。但是经过自己的学习我自己想到一个算法。算是结合了其中的优点吧。

    • 算法描述:该算法递归去统计结点个数。值得一提的是该系列算法都是统计根结点以下的符和条件的结点的个数进行了加和。免去的设置全局变量和void的类型的函数。
    
    int	CountNodes(LBTree* lbt)
    {
    	int n = 0;
    	if (lbt != NULL)
    	{
    		++n;
    		n += CountNodes(lbt->lchild);
    		n += CountNodes(lbt->rchild);
    	}
    	return n;
    }
    
    int CountLeaves(LBTree* lbt)
    {
    	int n = 0;
    	if (lbt != NULL)
    	{
    		if (lbt->lchild == NULL && lbt->rchild == NULL)
    			++n;
    		n += CountLeaves(lbt->lchild);
    		n += CountLeaves(lbt->rchild);
    	}
    	return n;
    }
    
    int CountSingleNode(LBTree* lbt)
    {
    	int n = 0;
    	if (lbt != NULL)
    	{
    		if ((lbt->lchild == NULL && lbt->rchild != NULL) || (lbt->rchild == NULL && lbt->lchild != NULL))
    			++n;
    		n += CountSingleNode(lbt->lchild);
    		n += CountSingleNode(lbt->rchild);
    	}
    	return n;
    }
    
    int	CountDoubleNode(LBTree* lbt)
    {
    	int n = 0;
    	if (lbt != NULL)
    	{
    		if (lbt->lchild != NULL && lbt->rchild != NULL)
    			++n;
    		n += CountDoubleNode(lbt->lchild);
    		n += CountDoubleNode(lbt->rchild);
    	}
    	return n;
    }
    
    
    

    0c4c39510bebfcdb3edecd637c2a5d80.png
    展开全文
  • 前面我们讲了关于数据结构中的堆栈问题,这篇文章主要是为大家简要介绍一下二叉树,并实现二叉树的创建、计算叶子结点个数递归遍历、判断是否是完全二叉树等相关问题~ 一、二叉树的介绍 1、什么是二叉树 一棵...

    前面我们讲了关于数据结构中的堆栈问题,这篇文章主要是为大家简要介绍一下二叉树,并实现二叉树的创建、计算叶子结点个数、递归遍历、判断是否是完全二叉树等相关问题~

    一、二叉树的介绍

    1、什么是二叉树
    一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树 的二叉树组成。

    2、二叉树的特点
    1、 每个结点最多有两棵子树,即二叉树不存在度大于2的结点。
    2、 二叉树的子树有左右之分,其子树的次序不能颠倒。

    3、特殊的二叉树
    1、 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是 说,如果一个二叉树的层数为K,且结点总数是(2^k)-1 则它就是满二叉树。

    2、 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K 的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

    二、二叉树的存储结构

    1、顺序存储
    使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的 浪费。而现实中使用中只有堆才会使用数组来存储,关于堆我们后面的章节会专门讲解。二叉树顺序存储在 物理上是一个数组,在逻辑上是一颗二叉树。
    在这里插入图片描述
    2、链式存储

    二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。
    在这里插入图片描述

    3、二叉树链式结构的实现

    1、递归遍历
    (1)前序遍历:如果二叉树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树,再前序遍历右子树。如下图所示,遍历的顺序是:ABDGHCEIF
    在这里插入图片描述

    代码实现:

    void BinaryTreePrevOrder(BTNode* root)
    {
     if(root == NULL)
      return;
     printf("%c",root->_data);//显示结点数据
     BinaryTreePrevOrder(root->_left);//再先序遍历左子树
     BinaryTreePrevOrder(root->_right);//最后先序遍历右子树
    }

    算法分析:
    1、调用BinaryTreePrevOrder(root)函数,根结点不为空,所以执行printf,打印字母A
    2、调用BinaryTreePrevOrder(root->_left),访问了A结点的孩子,不为null,执行printf显示字母B
    3、再次调用BinaryTreePrevOrder(root->_left),访问了B结点的孩子,不为null,执行printf显示字母D
    4、再次调用BinaryTreePrevOrder(root->_left),访问了D结点的孩子,不为null,执行printf显示字母G
    以此类推…

    (2)中序遍历
    和前序遍历算法仅仅是代码上顺序的差异,相当于把调用左孩子的递归函数提前了。

    代码实现:

    void BinaryTreeInOrder(BTNode* root)
    {
     if(root == NULL)
      return;
     BinaryTreeInOrder(root->_left);
     printf("%c",root->_data);
     BinaryTreeInOrder(root->_right);
    }

    (3)后序遍历
    同理
    代码实现:

    void BinaryTreePostOrder(BTNode* root)
    {
     if(root == NULL)
      return;
     BinaryTreePostOrder(root->_left);
     BinaryTreePostOrder(root->_right);
     printf("%c",root->_data);
    }

    2、层序遍历

    设二叉树的根节点所在 层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层 上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。
    在这里插入图片描述
    代码实现:

    void  BinaryTreeLevelOrder(BTNode* root)
    {
     Queue q;
     QueueInit(&q);
     if(root != NULL)
     {
      QueuePush(&q,root);
      while(QueueEmpty(&q) != 0)
      {
       BTNode* front = QueueFront(&q);
       printf("%c",front->_data);
       QueuePop(&q);
       if(front->_left)
        QueuePush(&q,front->_left);
       if(front->_right)
        QueuePush(&q,front->_right);
      }
      printf("\n");
     }
    }

    算法分析:
    使用队列的方式来存储每一个遍历到的结点值,再依次出队打印。其结果就为程序遍历的结果值。

    3、二叉树的创建——通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
    为了让每个结点确认是否有左右孩子,对其进行了扩展,也就是将二叉树中每个结点的空指针引出一个虚结点,其值为一个特定值“#”
    在这里插入图片描述
    也是利用递归的原理,只不过在原来应该打印结点的地方,改成了生成结点,给结点赋值的操作,利用了数组的存储结构来辅助实现
    代码实现:

    BTNode* BinaryTreeCreate(BTDatatype* array, int* pIndex)
    if(array[(*pIndex)] == '#')
     {
      (*pIndex)++;
      return NULL;
     }
     BTNode* root = (BTNode*)malloc(sizeof(BTNode));
     root->_left = NULL;
     root->_right = NULL;
     root->_data = array[(*pIndex)];
    
    (*pIndex)++;
     root->_left = BinaryTreeCreate(array,pIndex);
     root->_right = BinaryTreeCreate(array,pIndex);
     return root;
     }

    4、计算叶子结点的个数
    如果二叉树为空则空操作返回空;如果左右孩子为空,则返回根结点个数为1;如果左右孩子不为空,则采用递归的方式,递归调用其左右子树计算其叶子结点个数。

    int BinaryTreeLeafSize(BTNode* root)
    {
     if(root == NULL)
      return 0;
     if(root ->_left == NULL && root->_right == NULL)
      return 1;
     return  BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
    }

    5、查找结点
    依然采用递归的方式

    BTNode* BinaryTreeFind(BTNode* root, BTDatatype x)
    {
     BTNode* ret = NULL;
     if(root == NULL)
      return NULL;
     if(root->_data == x)
      return root;
     ret = BinaryTreeFind(root->_left,x);
     if(ret)
      return ret;
     ret = BinaryTreeFind(root->_right,x);
     if(ret)
      return ret;
     return NULL;
    }

    补充结点定义:

    typedef char BTDatatype;
    //二叉树结点定义
    typedef struct BinaryTreeNode
    {
     BTDatatype _data;
     struct BinaryTreeNode* _left;
     struct BinaryTreeNode* _right;
    }BTNode;
    
    typedef BTNode* QDataType;
    //队列结点定义
    typedef struct QueueNode
    {
     QDataType _data;
     struct QueueNode* _next;
    }QueueNode;
    
    //标志结点
    typedef struct Queue
    {
     QueueNode* _head;
     QueueNode* _tail;
    }Queue;
    
    展开全文
  • 递归就是用到了栈,一结点一结点的保存,保存到叶子结点时候,就让叶子出栈,计数+1,然后让栈顶指向右结点再入栈循环执行即可 Java 实现 // 结点 class Node { int data; Node left = null; Node right =....

    文章目录

    思路

    思路这一块没啥可说,递归主要是求左子树叶子结点数+求右子树叶子结点数,递归实现。非递归就是用到了栈,一个结点一个结点的保存,保存到叶子结点时候,就让叶子出栈,计数+1,然后让栈顶指向右结点再入栈循环执行即可

    Java 实现

    // 结点
    class Node {
        int data;
        Node left = null;
        Node right = null;
    }
    
    // 二叉树
    public class BinaryTree {
        // 根结点
        private Node root;
        // 输入的数组
        private int[] arr_in;
        // 输出的数组
        private int[] arr_out;
        // 记录数组下标
        private static int index;
    
    // 得到二叉树叶子结点的个数(递归)
        public int getLeafCountRecursion(Node r) {
            if (r.left == null && r.right == null)
                return 1;
            else
            	return getLeafCountRecursion(r.left) + getLeafCountRecursion(r.right);
        }
        
        // 得到二叉树叶子结点的个数(非递归)
        public int getLeafCount(Node r) {
            Stack stack = new Stack();
            Node node = r;
            int count = 0;
            while (node || !stack.empty()) {
            	if (node) {
    				if (node.left != null || node.right != null) {
    					// 只存中间结点,不存叶子结点
                    	stack.push(node);
                    	node = node.left;
                	}
                	else {
                    	count++;
                    	node = stack.pop().right;
                	}
    			}
                else {
                	if (stack.peek().right)
    					node = stack.pop().right;
    				else {
    					stack.pop();
    					node = stack.pop().right;
    				}
    			}        
            }
        }
    
    展开全文
  • //递归统计二叉树叶子结点的个数(先序) int CountLeaf(BiTree &T) { if (T == NULL) { return 0; } else if (T->lchild == NULL && T->rchild == NULL) { return 1; } else { return (CountLeaf(T->lchild) + ...
  • 算法描述:该算法递归去统计结点个数。值得一提的是该系列算法都是统计根结点以下的符和条件的结点的个数进行了加和。免去的设置全局变量和void的类型的函数。 int CountNodes(LBTree* lbt) { int n = 0; if (lbt...
  • 算法描述:该算法递归去统计结点个数。值得一提的是该系列算法都是统计根结点以下的符和条件的结点的个数进行了加和。免去的设置全局变量和void的类型的函数。 int CountNodes(LBTree* lbt) { int n = 0; if (lbt ...
  • 二叉树叶子结点的个数 求二叉树结点的个数 求二叉树第K层节点的个数 判断一节点是否在一棵二叉树中 获取一节点的双亲节点 获取一节点的左孩子节点 获取一节点的右孩子节点 二叉树高度 (递归) ...
  • 目的:掌握二叉树遍历算法的应用,熟练使用先序、中序、...(2)输出二叉树b的叶子结点个数。 (3)求二叉树b中指定结点值(假设所有节点值不同)的结点层次。 (4)利用层次遍历求二叉树b的宽度。 代码如下: ...
  • 算法描述:该算法递归去统计结点个数。值得一提的是该系列算法都是统计根结点以下的符和条件的结点的个数进行了加和。免去的设置全局变量和void的类型的函数。​ int CountNodes(LBTree* lbt) { int n = 0; if ...
  • {数据结构}计算二叉树叶子结点个数

    万次阅读 多人点赞 2009-11-08 16:26:00
    /**************************************************算法描述:编写递归算法,计算二叉树叶子节点数目(6.42) ****************************************************/int leaf(bitree t){ if(!t) return 0;
  • 展开全部叶子节点:没有孩子节点的节点也就是说,当我们明白了叶子节点的定义62616964757a686964616fe59b9ee7ad9431333363376531后,只需要遍历一遍二叉树,把符合这种条件(左孩子节点和右孩子节点都为NULL的节点)的...
  • 在复习数据结构的过程中,二叉树一直都是重点也是难点,首先回顾了基础的二叉树递归遍历操作,二叉树叶子结点个数以及二叉树的copy操作,以后会进阶二叉树的非递归遍历以及二叉树的创建过程。现在来看一下自己回顾...
  • 齐鲁工业大学实验报告 成绩 课程名称 数据结构 ...实现二义树的先序中序与后序遍历的递归算法与非递归算法 求二义树的结点个数叶子结点个数二义树的高度度为 2的结点个数 二 实验环境 微型计算机vc 三 实验内容 实现二
  • 对于森林,大家可以做这样的理解,一个深度大于1,根节点子树个数大于1的树去掉根节点,就是森林。森林中每棵树的根节点再创建一个共同的双亲结点,就成为了一棵树。所以森林转化为二叉树和树转化为二叉树原理是一样...
  • 齐鲁工业大学实验报告 成绩 课程名称 数据结构 指导教师 单健芳 实验日期 院系 信息学院 专业班级 计科嵌入 ... 求二叉树的结点个数叶子结点个数二叉树的高度度为 2的结点个数 二实验环境 微型计算机 vc 6.0 三实验内容
  • 齐鲁工业大学实验报告 成绩 课程名称 数据结构 指导教师 单健芳 实验日期 院系 信息学院 专业班级 计科...求二叉树的结点个数叶子结点个数二叉树的高度度为2的结点个数 二实验环境 微型计算机vc 6.0 三实验内容 1.实现
  • 以二叉链表作为二叉树的存储结构,统计二叉树的叶结点个数。首先建树,递归走起。 #include<iostream> using namespace std; int ans; //叶子节点数 typedef struct biTnode{ char ...
  • 齐鲁工业大学实验报告 成绩 课程名称 数据结构 指导教师 单健芳 实验日期 院系 信息学院 专业班级 计科嵌入 ... 求二叉树的结点个数叶子结点个数二叉树的高度度为 2的结点个数 二实验环境 微型计算机 vc 6.0 三实验内容
  • v1.0 可编辑可修改 齐鲁工业大学实验报告 成绩 课程名称 数据结构 指导教师 单健芳 实验日期 院系 信息学院 专业班级 计科嵌入 14-1... 求二叉树的结点个数叶子结点个数二叉树的高度度为 2的结点个数 二实验环境 微型计
  • v1.0 可编辑可修改 齐鲁工业大学实验报告 成绩 课程名称 数据结构 指导教师 单健芳 实验日期 院系 信息学院 专业班级 计科嵌入 14-1... 求二叉树的结点个数叶子结点个数二叉树的高度度为 2的结点个数 二实验环境 微型计

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 123
精华内容 49
关键字:

数据结构二叉树叶子结点个数递归

数据结构 订阅