树形结构

树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。

把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。

有一个特殊的结点称为根(root)结点根结点没有直接前驱结点,

0)个互不相交的集合T1、T2、......、Tm其中每一个集合Ti

又是一棵与树类似的子树。

每棵子树的根结点有且只有一个前驱可以有0个或多个直接后继树是递归定义的。

如上图A的度为6树的度(唯一性)一棵树中所有结点度的最大值称为树的度

如上图B、C、H、I...等结点点为叶子结点双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点

如上图A是B的父结点孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点

如上图B是A的孩子结点根结点一棵树中没有双亲结点的结点如上图A结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推树的高度或深度树中结点的最大层次

树的以下概念只需了解只要知道是什么意思即可非终端结点或分支结点度不为0的结点

如上图D、E、F、G...等节点为分支结点兄弟结点具有相同父结点的结点互称为兄弟结点

如上图B、C是兄弟结点堂兄弟结点双亲在同一层的结点互为堂兄弟如上图H、I互为堂兄弟结点结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先子孙以某结点为根的子树中任一结点都称为该结点的子孙。

如上图所有结点都是A的子孙有序树与无序树:若一棵树中所有子树从左到右的排序是有顺序的不能颠倒次序称该树为有序树反之称为无序树。

class

或者是由一个根结点加上两棵别称为左子树和右子树的互不相交的二叉树组成。

或者说

一棵二叉树如果每层的结点数都达到最大值则这棵二叉树就是满二叉树。

也就是说如果一棵二叉树的层数为K且结点总数是2^k

完全二叉树:

完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。

对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。

要注意的是满二叉树是一种特殊的完全二叉树。

练习题

二叉树的链式存储是通过一个一个的结点引用起来的常见的表示方式有二叉和三叉表示方式具体如下

孩子表示法

此处手动快速创建一棵简单的二叉树快速进入二叉树操作学习等二叉树结构了解的差不多时我们反过头再来研究二叉树真正的创建方式。

public

BinaryTree();binaryTree.createBinaryTree();}

注意上述代码并不是创建二叉树的方式真正创建二叉树方式后序详解重点讲解.

从概念中可以看出二叉树定义是递归式的因此后序基本操作中基本都是按照该概念实现的。

(Traversing

设二叉树的根结点所在层数为1层序遍历就是从所在二叉树的根结点出发首先访问第一层的树根结点然后从左到右访问第2层上的结点接着是第三层的结点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。

总结:

学习二叉树结构最简单的方式就是遍历。

所谓遍历(Traversal)是指沿着某条搜索路线依次对树中每个结点均做一次且仅做一次访问。

访问结点所做的操作依赖于具体的应用问题(比如打印节点内容、节点内容加1)。

在遍历二叉树时如果没有进行某种约定每个人都按照自己的方式遍历得出的结果就比较混乱如果按照某种规则进行约定则每个人对于同一棵树的遍历结果肯定是相同的。

如果D代表根结点L代表根结点的左子树R代表根结点的右子树则根据遍历根结点的先后次序有以下遍历方式

DLR前序遍历(Preorder

亦称先序遍历)——访问根结点---根的左子树---根的右子树。

LDR中序遍历(Inorder

Traversal)——根的左子树---根节点---根的右子树。

LRD后序遍历(Postorder

Traversal)——根的左子树---根的右子树---根结点。

分析前序递归遍历中序与后序图解类似

2.二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK;中序遍历HFIEJKG.则二叉树根结点为()A:

3.设一课二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列为()

adbce

{return;}System.out.print(root.val

);preOrder(root.left);preOrder(root.right);}//

中序遍历void

{return;}inOrder(root.left);System.out.print(root.val

后序遍历void

{return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val

);}

TestBinaryTree();TestBinaryTree.TreeNode

root

testBinaryTree.createTree();testBinaryTree.preOrder(root);System.out.println();testBinaryTree.inOrder(root);System.out.println();testBinaryTree.postOrder(root);}

非递归实现-先序中序后序遍历:

{stack.push(cur);System.out.print(cur.val

);cur

但是不能进入最内层while循环然后弹出栈顶的元素*///如果右边不为空,

void

stack.pop();System.out.print(top.val

);cur

但是不能进入最内层while循环然后弹出栈顶的元素*///如果右边不为空,

void

null;//这个引用用来记录已经打印过的节点DequeTreeNode

stack

{//如果栈顶元素的右边为空或者栈顶元素的右边已经打印过---直接打印

弹出这个栈顶元素不需要要再往后遍历不然会重复打印顺便记录刚刚这个栈顶元素也被打印过了下次也不要打印它了System.out.print(top.val

);stack.pop();prev

TestBinaryTree();TestBinaryTree.TreeNode

root

testBinaryTree.createTree2();testBinaryTree.preOrderNor(root);System.out.println();testBinaryTree.inOrderNor(root);System.out.println();testBinaryTree.postOrderNor(root);}

时间复杂度:O(N)//

{return;}nodeSize;size2(root.left);size2(root.right);}

public

TestBinaryTree();TestBinaryTree.TreeNode

root

testBinaryTree.createTree();System.out.println((size1方法)结点个数:

testBinaryTree.size(root));//8testBinaryTree.size2(root);int

nodeSize

TestBinaryTree.nodeSize;System.out.println((size2方法)结点个数:

nodeSize);//8System.out.println(----------------);TestBinaryTree

testBinaryTree2

TestBinaryTree();TestBinaryTree.TreeNode

root2

testBinaryTree2.createTree();System.out.println((size1方法)结点个数:

testBinaryTree.size(root));//8testBinaryTree.size2(root);int

nodeSize2

TestBinaryTree.nodeSize;System.out.println((size2方法)结点个数:

nodeSize2);//16,

getLeafNodeCount(root.left);int

rightSize

getLeafNodeCount(root.right);return

leftSize

{//遇到叶子结点了.leafSize;}getLeafNodeCount2(root.left);getLeafNodeCount2(root.right);}

public

TestBinaryTree();TestBinaryTree.TreeNode

root

testBinaryTree.createTree();System.out.println(叶子结点的个数:

testBinaryTree.getLeafNodeCount(root));testBinaryTree.getLeafNodeCount2(root);System.out.println(叶子结点的个数:

root,

TestBinaryTree();TestBinaryTree.TreeNode

root

testBinaryTree.createTree();System.out.println(第k层的结点个数:

testBinaryTree.getKLevelNodeCount(root,

3));}

TestBinaryTree();TestBinaryTree.TreeNode

root

testBinaryTree.createTree();System.out.println(树的高度:

testBinaryTree.getHeight(root));}

TreeNode

TestBinaryTree();TestBinaryTree.TreeNode

root

testBinaryTree.createTree();TestBinaryTree.TreeNode

E);if

null){System.out.println(查找到了E元素,

E.val);}

{System.out.println(没有此元素!);}TestBinaryTree.TreeNode

J);if

null){System.out.println(查找到了J元素,

J.val);}

LinkedList();//先将头结点入队queue.offer(root);while

(!queue.isEmpty())

queue.poll();System.out.print(cur.val

(cur.left

{queue.offer(cur.right);}}}public

class

TestBinaryTree();TestBinaryTree.TreeNode

root

testBinaryTree.createTree();testBinaryTree.levelOrder(root);}

boolean

LinkedList();queue.offer(root);while

(!queue.isEmpty())

{queue.offer(cur.left);queue.offer(cur.right);}

else

匹配一次的时间复杂度是O(T)//空间复杂度:O(max(ds,

dt)),

false;}//检查两棵树是否相同//时间复杂度和空间复杂度:

O(min(m,

invertTree(root.right);//方法2:利用返回值TreeNode

left

invertTree(root.right);//翻转root.left

right;root.right

isSymmetricChild(leftTree.left,

rightTree.right)

isSymmetricChild(leftTree.right,

rightTree.left);}

createTree(str);inOrder(root);}}public

static

TreeNode(str.charAt(i));i;root.left

createTree(str);}

{return;}inOrder(root.left);System.out.print(root.val

/***

LinkedList();queue.offer(root);while

(!queue.isEmpty())

queue.poll();tmp.add(cur.val);size--;if

(cur.left

{queue.offer(cur.right);}}list.add(tmp);}return

list;}

lowestCommonAncestor(root.left,

q);//

lowestCommonAncestor(root.right,

q);//

{stack2.pop();size--;}}//通过上述操作---栈里面的元素个数是一样的.while

(!stack1.isEmpty()

TreeNode(preorder[i]);//每次放入先序遍历的节点//找到当前根,

rootIndex

TreeNode(postorder[i]);//每次放入后序遍历的节点//找到当前根,

rootIndex

StringBuilder();tree2strChild(root,

stringBuilder.toString();}public

void

{return;}stringBuilder.append(t.val);//把根节点先加入if

(t.left

{//左边不为空stringBuilder.append(();tree2strChild(t.left,

stringBuilder);//递归左边stringBuilder.append());}

else

{//右边不为空stringBuilder.append(());}

else

{//右边不为空stringBuilder.append(();tree2strChild(t.right,

stringBuilder);//递归右边stringBuilder.append());}}

12.

因为每次递归ret都是新的值.所以要把ret提到函数外面if(root

null)

ret;}//System.out.print(root.val

);ret.add(root.val);preorderTraversal(root.left);preorderTraversal(root.right);return

ListInteger

ArrayList();//这儿放到函数内是因为递归调用的不是本身的函数,不会让ret每次是新的值,

而是另一个函数func.func(root,ret);return

ret;}public

{return;}//System.out.print(root.val

);ret.add(root.val);func(root.left,ret);func(root.right,ret);}*///子问题思路//

public

preorderTraversal(root.left);//

ret.addAll(leftTree);//addAll(Collection?

extends

传入的参数是实现了collection接口且泛型类型Integer//

ListInteger

preorderTraversal(root.right);//

return

{stack.push(cur);//System.out.print(cur.val

cur.left;}//左边为空,

但是不能进入最内层while循环然后弹出栈顶的元素*///如果右边不为空,

ret;}

ret.addAll(leftTree);//addAll(Collection?

extends

传入的参数是实现了collection接口且泛型类型Integer//

ret.add(root.val);//

inorderTraversal(root.right);//

return

stack.pop();//System.out.print(cur.val

top.right;/*如果右边为空,

但是不能进入最内层while循环然后弹出栈顶的元素*///如果右边不为空,

ret;}

postorderTraversal(root.left);//

ret.addAll(leftTree);//addAll(Collection?

extends

传入的参数是实现了collection接口且泛型类型Integer//

ListInteger

postorderTraversal(root.right);//

ret.add(root.val);//

null;//这个引用用来记录已经打印过的节点DequeTreeNode

stack

{//如果栈顶元素的右边为空或者栈顶元素的右边已经打印过---打印

弹出栈顶元素//System.out.print(top.val

);ret.add(top.val);stack.pop();prev

top;}

最外层的while循环也进入不了,//但是如果此时栈内还有元素,

再判断.//如果右边不为空,