首页 > 编程札记 > 编程

数据结构（王道笔记）——二叉树

阅读：评论：0

数据结构（王道笔记）——二叉树

一、介绍

1、二叉树

2、满二叉树

3、完全二叉树

4、二叉排序树

5、平衡二叉树

6、扩充二叉树

二、二叉树的实现及遍历

1、存储结构

2、前序遍历

3、中序遍历

4、后序遍历

5、层次遍历

三、由遍历序列构造二叉树

1、从前序与中序遍历序列构造二叉树

2、从中序与后序遍历序列构造二叉树

四、线索二叉树

一、介绍

1、二叉树

特点：每个节点至多只有两棵子树，且子树有左右之分、次序不能任意颠倒。（有序树）

与度为2的有序树的区别：

度为2的有序树至少3给节点
度为2的有序树只有一棵子树时不区分左右，而二叉树一定先有左子树

性质：

（度为0的节点数=度为2的节点数+1）
前 i 层至多有个节点，第 i 层至多有个节点

2、满二叉树

满树、度均为2
从1开始按层编号，则 i 的左孩子为 2i ，右孩子为2i+1

3、完全二叉树

高为h的二叉树，且其每个节点按层编号均与满二叉树的对应编号一致。（即和满二叉树相比，只最后一层不是满的。）

若有度1的节点，则只有1个（有1个左孩子）。
从1开始按层编号，则从第一个度为1或0的节点开始，后面均为叶子节点。
节点为偶数时才存在度为1的节点。

4、二叉排序树

左子树所有节点<根节点<右子树所有节点

5、平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过1。

6、扩充二叉树

在原二叉树的空子树位置添加空树叶所形成的二叉树。结点度均为2。

外节点：扩充二叉树中的空树叶节结点。

内节点：非空结点。

外路径长度：扩充二叉树中所有外部结点到根结点的路径长度之和。

内路径长度：扩充二叉树中所有内部结点到根路径的路径长度之后和。

二、二叉树的实现及遍历

1、存储结构

顺序存储结构：用数组下标代表满二叉树按层的编号，0表示节点不存在。（满二叉树和完全二叉树比较适合）

链式存储结构：数据域+左、右指针域。（含有n个节点的二叉链表中，含有n+1个空指针域）

  public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}}

2、前序遍历

先根节点，再左子树，再右子树。

递归前序遍历：

public void preorderTraversal(TreeNode root) {if (root!=null){System.out.print(root.val);//根preorderTraversal(root.left);preorderTraversal(root.right);}
}

非递归前序遍历：

    /***@MethodName preorderTraversal*@Description TODO 144. 二叉树的前序遍历 /*/public List<Integer> preorderTraversal(TreeNode root) {TreeNode now=root;List<Integer> result=new ArrayList<>();Stack<TreeNode> stack=new Stack<>();while (!pty()||now!=null) {//访问当前元素，然后一直向左走，直到当前节点为null，就出栈其双亲if (now!=null){result.add(now.val);stack.push(now);now=now.left;}else {//栈顶元素出栈，确定其右子树情况now=stack.pop().right;}}return result;}

3、中序遍历

先左子树，再根节点，再右子树。

递归中序遍历：

public void inorderTraversal(TreeNode root) {if (root!=null){inorderTraversal(root.left);System.out.print(root.val);//根inorderTraversal(root.right);}
}

非递归中序遍历：

/***@MethodName inorderTraversal*@Description TODO 94. 二叉树的中序遍历 /*/
public List<Integer> inorderTraversal(TreeNode root) {TreeNode now=root;List<Integer> result=new ArrayList<>();Stack<TreeNode> stack=new Stack<>();while (!pty()||now!=null) {//当前元素一致向左走，直到当前节点为null，就出栈其双亲if (now!=null){stack.push(now);now=now.left;}else {//栈顶元素出栈，并访问，确定其右子树情况TreeNode temp=stack.pop();result.add(temp.val);now=temp.right;}}return result;
}

前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。也就是说前序序列的出栈序列个数=其可能的不同二叉树个数。

4、后序遍历

先左子树，再右子树，再根节点。

递归中后序遍历：

public void postorderTraversal(TreeNode root) {if (root!=null){postorderTraversal(root.left);postorderTraversal(root.right);System.out.print(root.val);//根}
}

非递归后序遍历：

/***@MethodName postorderTraversal*@Description TODO 145. 二叉树的后序遍历 /*/
public List<Integer> postorderTraversal(TreeNode root) {//r 上次访问的对象TreeNode now=root,r=null;List<Integer> result=new ArrayList<>();Stack<TreeNode> stack=new Stack<>();while (!pty()||now!=null) {//当前元素一直向左走，直到当前节点为null，就找其双亲右孩子if (now!=null){stack.push(now);now=now.left;}else {//栈顶元素不出栈，确定其右子树情况,//如果右子树为空，则出栈并访问；//如果右子树刚被访问过说明其左子树之前已进栈、并再出栈被访问了，此时左右子树都被访问，则出栈并访问now=stack.peek();if (now.right!=null&&now.right!=r){now=now.right;}else {//出栈、访问result.add(stack.pop().val);//记录r=now;now=null;}}}return result;
}

5、层次遍历

使用队列

/***@MethodName levelOrder*@Description TODO 102. 二叉树的层序遍历 /*/public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result=new ArrayList<>();Queue<TreeNode> queue=new ArrayDeque<>();int count=1;//每行节点的双亲数if(root!=null){queue.add(root);}while (!queue.isEmpty()) {List<Integer> temp=new ArrayList<>();for (int i = 0; i < count; i++) {TreeNode head&#ve();temp.add(head.val);if (head.left!=null){queue.add(head.left);}if (head.right!=null){queue.add(head.right);}}result.add(temp);count=queue.size();}return result;}

三、由遍历序列构造二叉树

1、从前序与中序遍历序列构造二叉树

非递归：

/***@MethodName buildTree*@Description TODO 105. 从前序与中序遍历序列构造二叉树 /*/public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder == null || preorder.length == 0) {return null;}TreeNode root=new TreeNode(preorder[0]);//用栈存储未确定右孩子的节点Stack<TreeNode> stack=new Stack<>();stack.push(root);int index=0;//中序 的指针，从左往右扫描元素的顺序 恰好是 前序做到最左端后的回序迭代。//流程：识别左孩子->入栈，直到没有左孩子，按一步步迭代回去 出栈 找右孩子 再迭代//从左开始扫描前序，如果一个节点不是它前一个结点的左孩子，那一定是它前面某个结点的右孩子（因为前面所有结点都确定了左孩子）//  且一定是离它最近的有右孩子的结点。for (int i = 1; i < preorder.length; i++) {TreeNode parent = stack.peek();//根据当前扫描的中序的结点 和 前序是否相等，判断是否前序是否遍历到了当前最左端。if (preorder[i - 1] != inorder[index]) {//不相等表示没到最左端，要一直向左构建左子树,相等的那个也要构建进去、所以是i-1parent.left = new TreeNode(preorder[i]);stack.push(parent.left);} else {//相等表示到了最左端，而没有右节点出现前，中序顺序和前序的回溯即栈中顺序 相同//找到当前结点（前序到达最左端后的下一个结点，是栈中第一个有右节点的 结点的右节点 ）在中序中的位置while (!pty() && stack.peek().val == inorder[index]) {parent = stack.pop();index++;}//找到后parent.right = new TreeNode(preorder[i]);stack.push(parent.right);}}return root;}

递归：

//left=0,riht=inorder.length-1,pos=0
public TreeNode buildTree(int[] preorder, int[] inorder, int left, int right ,int pos)｛if(pos>=preorder.lenth)return null;if(left==right){return new TreeNode(mid[left]);}TreeNode node=null;for(int i=left;i<=riht;i++){if(preorder[pos]==inorder[i]);{node=new TreeNode(inorder[i]);node.left=buildTree(preorder,inorder,left,i-1,++pos);node.right=buildTree(preorder,inorder,i+1,right,++pos);break;}}return node;
｝

2、从中序与后序遍历序列构造二叉树

非递归：

    /***@MethodName buildTree*@Description TODO 106. 从中序与后序遍历序列构造二叉树 /*/public TreeNode buildTree2(int[] inorder, int[] postorder) {if (inorder == null || inorder.length == 0) {return null;}int n=postorder.length;TreeNode root=new TreeNode(postorder[n-1]);//用栈存储未确定左孩子的节点Stack<TreeNode> stack=new Stack<>();stack.push(root);int index=n-1;//中序 的指针，从左往右扫描元素的顺序 恰好是 前序做到最左端后的回序迭代。//流程：向右检索 识别右孩子->入栈，直到没有右孩子，按一步步迭代回去 出栈 找左孩子 入栈再迭代//从右开始扫描后序，如果一个节点不是它后一个结点的右孩子，那一定是它前面某个结点的左孩子（因为前面所有结点都确定了右孩子）//  且一定是离它最近的有左孩子的结点。for (int i = n-2; i >=0; i--) {TreeNode parent = stack.peek();//根据当前扫描的中序的结点 和 后序是否相等，判断是否前序是否遍历到了当前最左端。if (postorder[i+1] != inorder[index]) {//不相等表示没到最右端，要一直向右构建左子树,相等的那个也要构建进去、所以是i+1parent.right = new TreeNode(postorder[i]);stack.push(parent.right);} else {//相等表示到了最右端，而没有左节点出现前，中序顺序和后序的回溯即栈中顺序 相同//找到当前结点（后序从右向左扫描到达最右端后的下一个结点，是栈中第一个有左节点的 结点的左节点 ）在中序中的位置while (!pty() && stack.peek().val == inorder[index]) {parent = stack.pop();index--;}//找到后parent.left = new TreeNode(postorder[i]);stack.push(parent.left);}}return root;}

递归：

//left=0,riht=inorder.length-1,pos=postorder.length
public TreeNode buildTree(int[] postorder, int[] inorder, int left, int right ,int pos)｛if(pos<0)return null;if(left==right){return new TreeNode(mid[left]);}TreeNode node=null;for(int i=right;i>=left;i--){if(preorder[pos]==inorder[i]);{node=new TreeNode(inorder[i]);node.left=buildTree(preorder,inorder,left,i-1,--pos);node.right=buildTree(preorder,inorder,i+1,right,--pos);break;}}return node;
｝