精华内容
下载资源
问答
  • package class_04; import java.util.LinkedList;... * 判断一棵树是否是搜索二叉树 * 判断一棵树是否是完全二叉树 * */ public class Code_07_IsBSTAndCBT { public static class Node { public int v...
    package class_04;
    
    import java.util.LinkedList;
    import java.util.Queue;
    /**
     * 
     * 判断一棵树是否是搜索二叉树
     * 判断一棵树是否是完全二叉树
     *
     */
    public class Code_07_IsBSTAndCBT {
    
    	public static class Node {
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int data) {
    			this.value = data;
    		}
    	}
    	//判断一棵树是否是搜索二叉树
    	public static boolean isBST(Node head) {
    		if (head == null) {
    			return true;
    		}
    		boolean res = true;
    		Node pre = null;
    		Node cur1 = head;
    		Node cur2 = null;
    		while (cur1 != null) {
    			cur2 = cur1.left;
    			if (cur2 != null) {
    				while (cur2.right != null && cur2.right != cur1) {
    					cur2 = cur2.right;
    				}
    				if (cur2.right == null) {
    					cur2.right = cur1;
    					cur1 = cur1.left;
    					continue;
    				} else {
    					cur2.right = null;
    				}
    			}
    			if (pre != null && pre.value > cur1.value) {
    				res = false;
    			}
    			pre = cur1;
    			cur1 = cur1.right;
    		}
    		return res;
    	}
    	//判断一棵树是否是完全二叉树
    	public static boolean isCBT(Node head) {
    		if (head == null) {
    			return true;
    		}
    		Queue<Node> queue = new LinkedList<Node>();
    		boolean leaf = false;
    		Node l = null;
    		Node r = null;
    		queue.offer(head);
    		while (!queue.isEmpty()) {
    			head = queue.poll();
    			l = head.left;
    			r = head.right;
    			if ((leaf && (l != null || r != null)) || (l == null && r != null)) {
    				return false;
    			}
    			if (l != null) {
    				queue.offer(l);
    			}
    			if (r != null) {
    				queue.offer(r);
    			} else {
    				leaf = true;
    			}
    		}
    		return true;
    	}
    
    	// for test -- print tree
    	public static void printTree(Node head) {
    		System.out.println("Binary Tree:");
    		printInOrder(head, 0, "H", 17);
    		System.out.println();
    	}
    
    	public static void printInOrder(Node head, int height, String to, int len) {
    		if (head == null) {
    			return;
    		}
    		printInOrder(head.right, height + 1, "v", len);
    		String val = to + head.value + to;
    		int lenM = val.length();
    		int lenL = (len - lenM) / 2;
    		int lenR = len - lenM - lenL;
    		val = getSpace(lenL) + val + getSpace(lenR);
    		System.out.println(getSpace(height * len) + val);
    		printInOrder(head.left, height + 1, "^", len);
    	}
    
    	public static String getSpace(int num) {
    		String space = " ";
    		StringBuffer buf = new StringBuffer("");
    		for (int i = 0; i < num; i++) {
    			buf.append(space);
    		}
    		return buf.toString();
    	}
    
    	public static void main(String[] args) {
    		Node head = new Node(4);
    		head.left = new Node(2);
    		head.right = new Node(6);
    		head.left.left = new Node(1);
    		head.left.right = new Node(3);
    		head.right.left = new Node(5);
    
    		printTree(head);
    		System.out.println(isBST(head));
    		System.out.println(isCBT(head));
    
    	}
    }

     

    展开全文
  • 这是一个很经典的算法题,听起来好像挺难的,但是其实很... 首先要判断一棵树是不是另一棵树的子树,我们只需遍历一棵树,用这个树的每一个节点去和另一棵树比较。那么这个问题就被 转化成了,如何遍历一棵树和如何

            这是一个很经典的算法题,听起来好像挺难的,但是其实很简单。我觉得我们接触到的问题,并没有难题,只有复杂不复杂。一个再难的问题,也可以分解成一个个简单的问题,再将这些简单的问题交给不同的人去做就构成了一个项目。其实写算法也是这个思想。

             首先要判断一棵树是不是另一棵树的子树,我们只需遍历一棵树,用这个树的每一个节点去和另一棵树比较。那么这个问题就被

    转化成了,如何遍历一棵树和如何判断2棵树是否相等。

              我选择用层次遍历的方式来遍历这棵树

              public static boolean levelSearch(Node root,Node child){

                   Deque<Node> deque = new Deque<Node>();

                   deque.add(root);

                   while(deque.size()!=0){

                       Node node = deque.peekFirst();

                       if(node.isSame(child)==true)

                       return true;

                       if(node.left!=null)

                       deque.add(node.left);

                      if(node.right!=null)

                       deque.add(node.right);

                  }

                  return false;

             }

             很明显上面就是一个广度优先遍历算法,那么接下来我们只需要实现isSame()方法了,这个也很简单

             public static boolean isSame(Node node1,Node node2){

             if((node1==null&&node2!==null)||((node2==null&&node1!==null)))

             return false;

            if(node1==null&&node2==null){

            }

             if(node1!=null&&node2!=null){

              if(node1.value!=node2.value)

              return false;

              if(!isSame(node1.left,node2.left))

              return false;

              if(!isSame(node1,right,node2.right))

              return false;

            }

             }

         这里很简单,将所有不同的情况都列举出来,一旦出现就返回false,如果在整个遍历过程中都没有出现false,最后返回true。

    展开全文
  • 数据结构与算法之判断一棵树是否为搜索二叉树、判断一棵树是否是完全二叉树 目录 判断一棵树是否为搜索二叉树 判断一棵树是否是完全二叉树 1. 判断一棵树是否为搜索二叉树 概念:搜索树就是中序遍历的结果是...

    数据结构与算法之判断一棵树是否为搜索二叉树、判断一棵树是否是完全二叉树


    目录

    1. 判断一棵树是否为搜索二叉树
    2. 判断一棵树是否是完全二叉树

    1. 判断一棵树是否为搜索二叉树

    1. 概念:搜索树就是中序遍历的结果是升序,就是搜索二叉树。如下图
      在这里插入图片描述
    2. 我们可以改中序遍历非递归版,在打印时机换成比较。即如代码为中序遍历非递归版
    public static void inOrderUnRecur(Node head) {
    		System.out.print("in-order: ");
    		if (head != null) {
    			Stack<Node> stack = new Stack<Node>();
    			while (!stack.isEmpty() || head != null) {
    				if (head != null) {
    					stack.push(head);
    					head = head.left;
    				} else {
    					head = stack.pop();
    					System.out.print(head.value + " ");
    					head = head.right;
    				}
    			}
    		}
    		System.out.println();
    	}
    

    我们设置一个变量记录当前值,和后一个需要打印的值比较,如果前一个值大于后一个值,即不是搜索二叉树,则返回false。改后的搜索二叉树代码为:

    public static boolean isBST1(Node head) {
            if (head != null) {
                Stack<Node> stack = new Stack<>();
                int pre = 0;
                while (!stack.isEmpty() || head != null) {
                    if (head != null) {
                        stack.push(head);
                        head = head.left;
                    } else {
                        head = stack.pop();
                        if (pre<=head.value){
                            pre = head.value;
                        }else {
                            return false;
                        }
                        head = head.right;
                    }
                }
            }
            return true;
        }
    

    另外一种搜索二叉树的代码

    public static boolean isBST2(Node head) {
            if (head == null) {
                return true;
            }
            boolean res = true;
            Node pre = null;
            Node cur1 = head;
            Node cur2 = null;
            while (cur1 != null) {
                cur2 = cur1.left;
                if (cur2 != null) {
                    while (cur2.right != null && cur2.right != cur1) {
                        cur2 = cur2.right;
                    }
                    if (cur2.right == null) {
                        cur2.right = cur1;
                        cur1 = cur1.left;
                        continue;
                    } else {
                        cur2.right = null;
                    }
                }
                if (pre != null && pre.value > cur1.value) {
                    res = false;
                }
                pre = cur1;
                cur1 = cur1.right;
            }
            return res;
        }
    

    2. 判断一棵树是否是完全二叉树

    1. 思路

      1. 如果有右孩子,没有左孩子,那肯定不是完全二叉树
      2. 当第一次发现左右两个孩子不是双全的时候,后面遍历到的节点全部都是叶节点,否则返回false
    2. 流程

      1. 判断head是否为null,如果为null返回true,否则创建一个队列和创建一个布尔值leaf,表示判断是否开启叶子阶段
      2. 当队列不为null时,从队列弹出一个数,然后获取左右节点。
      3. 判断:如果左孩子为null,右孩子不为null,或者开启叶子判断并且左孩子节点或者右孩子节点不为null,则返回false。
      4. 如果左节点不为null,加入队列。如果右节点不为null,加入队列。
      5. 如果左节点为null或者右节点为null,则开启叶子判断。
    3. 代码实现

    public static boolean isCBT(Node head) {
            if (head == null) {
                return true;
            }
            Queue<Node> queue = new LinkedList<Node>();
            boolean leaf = false;
            Node l = null;
            Node r = null;
            queue.offer(head);
            while (!queue.isEmpty()) {
                head = queue.poll();
                l = head.left;
                r = head.right;
                if ((leaf && (l != null || r != null)) || (l == null && r != null)) {
                    return false;
                }
                if (l != null) {
                    queue.offer(l);
                }
                if (r != null) {
                    queue.offer(r);
                }
                if (l == null || r == null) {
                    leaf = true;
                }
            }
            return true;
        }
    
    展开全文
  • ~判断一棵树是否是完全二叉树~

    千次阅读 2017-05-03 20:56:25
    判断一棵树是否是完全二叉树

    二叉树经典面试题之一:判断一棵树是否是完全二叉树

     

    解题思路:

    既然求两个节点的最近公共祖先,那么我们首先画一个普通的二叉树来分析:

    完全二叉树的定义为:深度为k的二叉树,除第 k 层外,其它各层 (1~k-1) 的结点数都达到最大个数,第 k 层所有的结点都连续集中在最左边。

    根据完全二叉树的定义,判断一棵树是否是完全二叉树需要做到两步:

    1)判断当前节点的左子树是否存在

         存在:判断右子树是否为空,若是空子树,则返回true,若不是空子树,则需要看下一层节点的情况;

         不存在:判断右子树是否为空,若是空子树,则返回true,若不是空子树,则返回false;

    2)判断当前节点的右子树是否存在

         存在:判断左子树是否为空,若是空子树,则返回false,若不是空子树,则需要看下一层节点的情况;

         不存在:判断左子树是否为空,若是空子树,则返回true,若不是空子树,则返回true;

     

    完整的源代码及测试用例如下:

    #include <queue>
    
    queue<BinaryTreeNode<int> *> q;
    bool flag = true;
    
    bool Isflag(BinaryTreeNode<int>* node)
    {
    	if(node == NULL)
    	{
    		flag = false;
    	}
    	else
    	{
    		if(flag == false)
    		{
    			return false;
    		}
    		
    		q.push(node);
    	}
    
    	return true;
    }
    
    bool IsComplete(BinaryTreeNode<int>* root)
    {
    	//空树也是一颗完全二叉树
    	if(root == NULL)
    	{
    		return true;
    	}
    
    	q.push(root);
    
    	while(!q.empty())
    	{
    		BinaryTreeNode<int> *front = q.front();
    		q.pop();
    
    		if(!Isflag(front->_left))
    		{
    			return false;
    		}
    
    		if(!Isflag(front->_right))
    		{
    			return false;
    		}
    	}
    
    	return true;
    }
    
    void TestIsComplete()
    {
    	int array[] = {1,2,3,'#','#',4,'#','#',5,6};
    	int len = sizeof(array)/sizeof(array[0]);
    
    	BinaryTree<int> t(array, len, '#');
    
    	cout<<"IsComplete: "<<IsComplete(t._root)<<endl;
    }


     

    展开全文
  • 一棵树

    万次阅读 2018-01-27 21:51:11
    对自己当前行为不满 明知这种做法对,却偏不做;明知不对,却停不下来 最该做的事情往往不是简简单单就...种一棵树最好在10年前,其次是现在 与其纠结于现在,不如着眼于现在,未来 做当前最重要的,拒绝拖延 是否符合你
  • 判断一棵树是否为满二叉树

    千次阅读 2016-06-23 16:42:00
    那么,我们要怎么判断一棵树是否为满二叉树呢? 思路:在层序遍历的过程中,找到第一个非满节点(non-full node)。满节点(full-node)指的是同时拥有左右孩子的节点。在找到第一个非满节点之后,剩下的节点不应该有...
  • 例如,下图中的两棵树 A 和 B ,由于 A 中有部分子树的结构和 B 是一样的,因此 B 就是 A 的子结构。  1 8  / \ / \  8 7 9 2  / \  9 2  / \  4 7 分析:这是 ...
  • 问题:判断一棵树是否为排序二叉树(二叉搜索树) 思路:二叉排序树的中序遍历为一递增的排序,若果不满足这一条件,则,不是二叉树 程序实现: #include &lt;iostream&gt; #include&lt;limits&...
  • 判断两棵树是否相同 方法:对两棵树同时做相同的递归判断其值或者是结构是否相同。 以下代码用的是前序遍历。递归方法(毕竟递归好理解而且代码少得可怜)。 比较啰嗦的是指针为空的情况,只要把这些情况单独列...
  • 如何将一棵树转化成二叉树

    万次阅读 多人点赞 2019-02-21 01:44:59
    从这棵树的根结点开始,从上到下,看每个结点,把你正在看的结点的孩子放在左子树,兄弟放在又子树。 口诀: 1. 将 节点的孩子 放在左子树; 2. 将 节点的兄弟 放在右子树。 关于这个问题,最好的办法就是记住...
  • 判断一棵树是否是另一棵树的子树

    千次阅读 2015-08-24 15:36:47
    bool containsTree(TreeNode t1, TreeNode ...if (t2 == NULL)//空一定是子树 { return true; }  return subTree(t1,t2); } bool matchTree(TreeNode r1, TreeNode r2) { if (r2 == NULL && r1 == NULL)//若
  • 判断一棵树是否为AVL树

    千次阅读 2015-10-10 23:23:55
    NO.12判断一棵树是否为AVL树: 平衡二叉树(AVL树)是满足下面条件的二叉树:要么是一棵空树,要么左右子树都是AVL树,并且左右子树的深度之差的绝对值不大于1。由此可知,要判断一棵树是不是AVL树,只要判断它的...
  • 判断一棵树是不是另一棵树的子树

    千次阅读 2011-08-17 22:15:34
    特殊情况,空为任何(包括空)的子树 struct node { int val; struct node *left; struct node *right; node(int t) { val = t; left = 0; right = 0; }
  • 判断一棵树是否为二叉排序树

    千次阅读 多人点赞 2017-11-23 19:18:08
    概要由于二叉排序的中序遍历时得到的一定是个个升序序列,我们可以根据这性质,利用中序遍历进行判定。算法1)设置全局变量max为无穷小。 2)若为空,则返回true。 3)否则递归判断左子树是否为二叉排序...
  • 一棵树转换为二叉树

    千次阅读 2017-09-01 15:13:18
    如何将一棵树转化为对应的二叉树? 解答: 1. 将 节点的孩子 放在左子树; 2. 将 节点的兄弟 放在右子树。 例题: 答案:     延伸: 任何一棵树都可以表示成二叉树,并不是任何一棵二叉树都可以表示成树。那么树...
  • T1是一棵含有几百万个节点的,T2含有几百个节点。判断T2是否是T1 的子树。 首先考虑小数据量的情况,可以根据的前序和中序遍历所得的字符串,来通过判断T2生成的字符串是否是T1字符串的子串,来判断T2是否是T1的...
  • 思路:对于一棵二叉树,最简单的方法就是中序遍历,看是不是一个递增数列,如果是,则是一棵二叉搜索,如果不是,则不是二叉搜索。在这里用一个lastVisit去记录上一次搜索的节点。这个过程就是先找到最左下角的...
  • 初始化一棵树

    千次阅读 2014-03-13 12:39:02
    #include #include //定义一个树节点的结构 struct treeNode{ ...//初始化一棵树的根节点 int initial_tree(struct treeNode**); int main(){ //定义一个指向树节点的指针,并初始化为空 struct tre
  • 判断一棵树是否是二叉查找树

    千次阅读 2016-03-30 18:55:32
    判断一棵树是否是二叉查找树 利用该节点对应的最大值和最小值来判断该节点是否符合二叉查找树的性质。public boolean isValidBST(TreeNode root) { return isValidBST(root, null, null); }public boolean ...
  • 剑指OFFER——判断一棵树是否是平衡二叉树 java实现 题目描述:输入一棵二叉树,判断该二叉树是否是平衡二叉树。 题目解析:首先要明白平衡二叉树的性质才做判断:平衡二叉树就是左子树和右子树的高度差不能超过1...
  • 克隆一棵树 【数据结构】

    千次阅读 2018-07-06 16:11:39
    克隆一棵树 树的创建是递归的,那么树的克隆也采用递归的方式 如下为先序遍历的方法克隆一棵树 1 根据树的根节点创建新的根节点 2 根据已知树的左子树递归创建新的左子树 3 根据已知树的右子树递归创建新的右子...
  • 树的c++实现--建立一棵树

    千次阅读 2019-11-05 21:38:17
    树的c++实现--建立一棵树 在学习二分查找树的时候,在递归的问题上遇到不少的问题,在这里和大家分享一下自己的学习过程 我在学习树的知识的时候,没有把树当做一个类,只把一个结点当做一个类。树的实现都在函数...
  • 随机生成一棵树

    千次阅读 2019-04-14 20:56:14
    并查集的简单介绍 1、初始情况四个点的父节点都为本身:FA[1]=1,FA[2]=2… 2、当生成的随机数为1,2时找到1,2的父节点分别为FA[1]=1,FA[2]=2,父节点不同进行连接。 ...3、生成的随机数为1,3,连接1,3这条边。...
  • XGBOOST下一棵树的输入是什么?

    千次阅读 2018-08-10 23:35:25
    最近研究XGBOOST,发现看完大篇理论推导之后根本不知道训练完一棵树后,下一棵树的输入是什么。 我想到了提升树(Boosting Tree),以平方误差损失函数为例,训练完一棵树后,只需要计算训练值和实际值的残差,再对...
  • 判断一棵树是否为完全二叉树

    千次阅读 2020-07-02 09:14:25
    一棵二叉树,给定它的根节点root,请设计一个算法判断它是否是完全二叉树 分析 一边对二叉树进行BFS将每一个节点都加入到队列,一边执行下面的判断 当前节点有右孩子,但没有左孩子,直接返回false 当前节点有左...
  • opengl 做的很漂亮的一棵树,用分形算法实现 含代码
  • 如何将一棵树转换成二叉树

    万次阅读 2012-09-29 14:34:26
    如何将一棵树转换成二叉树?   解答: 1. 将 节点的孩子 放在左子树; 2. 将 节点的兄弟 放在右子树。   延伸: 任何一棵树都可以表示成二叉树,并不是任何一棵二叉树都可以表示成树。那么树多还是二叉树多...
  • 验证一棵树是否为二叉搜索树

    千次阅读 多人点赞 2018-10-10 17:14:59
    给予个二叉树的根节点,验证该是否是二叉搜索,在O(n)时间内,用熟悉的语言写出算法。 不了解二叉搜索的盆友可以先移步《数据结构二叉树之闲死攻略(二)》 二叉搜索两个基本的性质 1. 顺序性(左&...
  • 如何判断一棵树是平衡二叉树

    千次阅读 2012-09-04 22:36:53
    由此可知,要判断一棵树是不是AVL树,只要判断它的左右子树的深度之差。问题落到了如何求一棵树的深度上去了。下面使用递归的方法求一棵树的深度: #include #include #include typedef struct BTr
  • 红黑树的插入数据时,什么时候该调整,什么时候不用调整,什么时候需要旋转,该怎样调节结点的颜色呢?以及如何判断一棵树是否是红黑树,超级详细的图解过程!!!

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 330,554
精华内容 132,221
关键字:

一棵树还是一棵树