1.1.

前序遍历又叫先根遍历。

每一个节点的遍历顺序都是按照“根——左子树——右子树”的顺序来遍历每遇到一个新的结点都看作是一棵新的树。

如果遇到空则递归回上一个节点。

A的右子树遍历过程也如下所以前序遍历的结果为“ABDCEF”。

1.2.

中序遍历的顺序为“左子树——根——右子树”遇到一个结点先去遍历左子树如果该节点的根为空才能递归回来进行打印。

所以中序遍历的结果为“DBAECF”。

1.3.

后序遍历的顺序为“左子树——右子树——根”遍历过程与上面两种都差不多这里不再多说。

后序遍历的顺序为“DBEFCA”。

1.4.

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

);PrevOrder(root.left);PrevOrder(root.right);}public

void

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

void

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

);}

BinaryTree();BinaryTree.TreeNode

root

binaryTree.CreateTree();System.out.print(前序遍历);binaryTree.PrevOrder(root);System.out.println();System.out.print(中序遍历);binaryTree.InOrder(root);System.out.println();System.out.print(后序遍历);binaryTree.PostOrder(root);}

2.1.

我们先回想以下如何获取链表中的结点个数。

我们定义一个ListNode

cur变量当cur不为空时count递增。

同样的我们上面已经实现了二叉树结点的遍历我们也只需要再定义一个计数器只要root不为空countNode就递增。

public

null){return;}CountSize;NodeSize(root.left);NodeSize(root.right);}

上面的是遍历思路还有一种子问题思路。

整棵树的结点个数等于左树的结点数和右树的结点数再加一只要root为空那么我们就可以结束递归。

public

NodeSize2(root.left)NodeSize2(root.right)1;return

tmp;}

叶子结点就是没有左右子树的结点递推公式为左子树叶子结点加右子树结点结束条件为结点的左右子树都为空。

//获取叶子结点个数public

getLeafNodeCount(root.right);}}public

int

null){LeafCount;}getLeafNodeCount2(root.left);getLeafNodeCount2(root.right);}

2.3.

比如我们要想获取第3层结点的个数就要求root.left第2层和root.right的第二层相当于左树的第一层和右树的第一层。

当k1时已经找到这一层此时也是递归的结束条件。

int

getLevelNodeCount(root.right,k-1)

getLevelNodeCount(root.left,k-1);}

2.4.

求二叉树的高度整棵树的高度等于左子树高度的最大值或者右子树高度的最大值加一当root为空的时候高度为0。

由于我们不知道是左子树高还是右子树高所以两边都需要遍历。

int

我们先检查根结点是不是然后再遍历左子树和右子树当我们找到了val值直接返回不用再递归下面了。

TreeNode

find(root.right,val);if(rightVal

null){return

BinaryTree();BinaryTree.TreeNode

root

binaryTree.CreatTree();binaryTree.NodeSize(root);System.out.println(结点个数binaryTree.CountSize);System.out.println(结点个数binaryTree.NodeSize2(root));System.out.println(叶子结点个数binaryTree.getLeafNodeCount(root));binaryTree.getLeafNodeCount2(root);System.out.println(叶子结点个数binaryTree.LeafCount);System.out.println(第3层结点个数binaryTree.getLevelNodeCount(root,3));System.out.println(二叉树的高度binaryTree.getHeight(root));}