sponsored links

二叉树

求树的最大宽度(层次遍历法)

November 30
求树的最大宽度(层次遍历法)
二叉树宽度:使用队列,层次遍历二叉树.在上一层遍历完成后,下一层的所有节点已经放到队列中,此时队列中的元素个数就是下一层的宽度.以此类推,依次遍历下一层即可求出二叉树的最大宽度. 怎么一层一层地分开呢?用一个变量len来记录当前层的结点数,出一个结点就len–,len==0的时候就退出循环,然后又把队列中的节点数赋值给len int getWidth(BiNode head) { if(head==null) return 0; int max=1; LinkedList<BiNode>ll=

判断一棵二叉树是否为二叉搜索树(BST)

November 30
判断一棵二叉树是否为二叉搜索树(BST)
这里先简单介绍一下二叉查找树的性质: 递归定义节点的左子树中任意节点值小于根节点的值,节点的右子树中任意节点值大于根节点,且当前节点左右子树都必须是二叉查找树,不允许存在重复节点. 假设: 节点的数据结构: struct node { int value; node* left; node* right; }; 方法1(错误示范:自己踩的坑) 首先BST是一个递归定义:这样我们首先想到用递归的方式进行判断: //对于每个节点,检测它的左孩子节点是否小于它,且右孩子节点是否大于它. bool is