Java中二叉树的基础知识及概念是什么？ |
您所在的位置：网站首页 › 树结构概念 › Java中二叉树的基础知识及概念是什么？ |
Java中二叉树的基础知识及概念是什么？
|
1. 树型结构1.1概念 树是一种 非线性 的数据结构，它是由 n （ n>=0 ）个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看 起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的 。
a.节点的度：该节点子树的个数；如上图：A的度为6，J的度为2 b.树的度：该树中，最大结点的度就是该数的度；如上图：树的度为6 c.叶子节点（终端节点）：度为0的节点（没有子树的节点） d.双亲结点/父节点：如上图：D是H的父节点 孩子节点/子节点：如上图：H是D的子节点 e.根节点：没有双亲的节点；如上图：A f.节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推； g.树的高度或深度：树中节点的最大层次； 如上图：树的高度为4 2. 二叉树（重点）2.1 概念每个节点最多只有两颗子树，度 根的左子树 ---> 根的右子树。 //先序遍历 : 根左右 public static void preOrder(TreeNode root){ if(root==null){ return; } System.out.print(root.val+" "); preOrder(root.left); preOrder(root.right); }登录后复制2. LNR ：中序遍历 (Inorder Traversal)—— 根的左子树 ---> 根节点 ---> 根的右子树。 //中序遍历 public static void inOrder(TreeNode root){ if(root==null){ return; } preOrder(root.left); System.out.print(root.val+" "); preOrder(root.right); }登录后复制3. LRN ：后序遍历 (Postorder Traversal)—— 根的左子树 ---> 根的右子树 ---> 根节点。 //后序遍历 public static void postOrder(TreeNode root){ if(root==null){ return; } preOrder(root.left); preOrder(root.right); System.out.print(root.val+" "); }登录后复制2.6.2 二叉树的遍历 (迭代) 1.前序遍历 //方法2(迭代) //先序遍历 (迭代) public static void preOrderNonRecursion(TreeNode root){ if(root==null){ return ; } Deque stack=new LinkedList(); stack.push(root); while (!stack.isEmpty()){ TreeNode cur=stack.pop(); System.out.print(cur.val+" "); if(cur.right!=null){ stack.push(cur.right); } if(cur.left!=null){ stack.push(cur.left); } } }登录后复制2.中序遍历 //方法2(迭代) //中序遍历 (迭代) public static void inorderTraversalNonRecursion(TreeNode root) { if(root==null){ return ; } Deque stack=new LinkedList(); // 当前走到的节点 TreeNode cur=root; while (!stack.isEmpty() || cur!=null){ // 不管三七二十一，先一路向左走到根儿~ while (cur!=null){ stack.push(cur); cur=cur.left; } // 此时cur为空，说明走到了null，此时栈顶就存放了左树为空的节点 cur=stack.pop(); System.out.print(cur.val+" "); // 继续访问右子树 cur=cur.right; } }登录后复制3.后序遍历 //方法2(迭代) //后序遍历 (迭代) public static void postOrderNonRecursion(TreeNode root){ if(root==null){ return; } Deque stack=new LinkedList(); TreeNode cur=root; TreeNode prev=null; while (!stack.isEmpty() || cur!=null){ while (cur!=null){ stack.push(cur); cur=cur.left; } cur=stack.pop(); if(cur.right==null || prev==cur.right){ System.out.print(cur.val+" "); prev=cur; cur=null; }else { stack.push(cur); cur=cur.right; } } }登录后复制2.6.3 二叉树的基本操作 1.求结点个数（递归&迭代） //方法1(递归) //传入一颗二叉树的根节点，就能统计出当前二叉树中一共有多少个节点，返回节点数 //此时的访问就不再是输出节点值，而是计数器 + 1操作 public static int getNodes(TreeNode root){ if(root==null){ return 0; } return 1+getNodes(root.left)+getNodes(root.right); } //方法2(迭代) //使用层序遍历来统计当前树中的节点个数 public static int getNodesNoRecursion(TreeNode root){ if(root==null){ return 0; } int size=0; Deque queue=new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { TreeNode cur = queue.poll(); size++; if (cur.left != null) { queue.offer(cur.left); } if (cur.right != null) { queue.offer(cur.right); } } return size; }登录后复制2.求叶子结点个数（递归&迭代） //方法1(递归) //传入一颗二叉树的根节点，就能统计出当前二叉树的叶子结点个数 public static int getLeafNodes(TreeNode root){ if(root==null){ return 0; } if(root.left==null && root.right==null){ return 1; } return getLeafNodes(root.left)+getLeafNodes(root.right); } //方法2(迭代) //使用层序遍历来统计叶子结点的个数 public static int getLeafNodesNoRecursion(TreeNode root){ if(root==null){ return 0; } int size=0; Deque queue=new LinkedList(); queue.offer(root); while (!queue.isEmpty()){ TreeNode cur=queue.poll(); if(cur.left==null && cur.right==null){ size++; } if(cur.left!=null){ queue.offer(cur.left); } if(cur.right!=null){ queue.offer(cur.right); } } return size; }登录后复制3.求第 k 层结点个数 //求出以root为根节点的二叉树第k层的节点个数 public static int getKLevelNodes(TreeNode root,int k){ if(root==null || k |
【本文地址】
今日新闻 |
推荐新闻 |