- 二叉树的性质 (1) 在二叉树的第 i 层最多有 2^i-1 个结点 (i>=1). (2) 深度为 k 的二叉树最多有 2^k - 1 个结点 (k>=1). (3) 对任何一棵二叉树，如果其叶子结点数为 n0, 度为 2 的结点数为 n2, 则 n0 = n2 + 1. 原因：设度为 1 的结点数为 n1, 则结点总数 n = n0 + n1 + n2; 设分支数为 B, 由于只有根结点没有分支进入, 因此 n = B + 1; 由于分支都是从度为 1 或 2 的结点引出的, 因此 B = n1 + 2 * n2; 联立上述等式可得 n0 = n2 + 1.
- 满二叉树 深度为 k 且有 2^k - 1 个结点的二叉树。
-
完全二叉树
(1) 深度为 k、有 n 个结点的二叉树，其每个结点的编号与深度为 k 的满二叉树中编号从 1~n 的结点一一对应. (2) 叶子结点只可能在层数最大的两层上出现。 (3) 对任意结点，若其右下分支下的子孙的最大层次为 lv, 则其左下分支下的子孙的最大层次必为 lv / lv + 1 (4) 结点数为 n 的完全二叉树，其深度为 logn + 1. (5) 结点数为 n 的完全二叉树，结点按层编号，则对编号为 i 的结点 (1 <= i <= n):若 i==1, 则结点 i 为二叉树的根, 无双亲; 若 i>1 , 则结点 i 的双亲是 i/2; 若 2i>n, 则结点 i 无左孩子, 否则其左孩子是结点 2i; 若 2i+1>n, 则结点 i 无右孩子, 否则其右孩子是结点 2i+1.
-
存储结构
二叉链表的存储表示class BiTNode { int data; BiTNode lchild, rchild;} -
先序遍历: 根-左-右
(1) 递归void preOrderRecursive(BiTNode tree) { if(tree!=null) { visit(tree); preOrderRecursive(tree.lchild); preOrderRecursive(tree.rchild); } }(2) 非递归
栈：初始化栈，并且树的根结点进栈；每次循环都将栈顶结点出栈并打印，然后先后将该结点的右子结点和左子结点进栈，直到栈为空。void preOrder(BiTNode tree) { if(tree==null) { return; } LinkedListstack = new LinkedList (); stack.push(tree); while(stack.size()>0) { BiTNode node = stack.pop(); visit(node); if(node.rchild!=null) { stack.push(node.rchild); } if(node.lchild!=null) { stack.push(node.lchild); } } } -
中序遍历: 左-根-右
(1) 递归void inOrderRecursive(BiTNode tree) { if(tree!=null) { inOrderRecursive(tree.lchild); visit(tree); inOrderRecursive(tree.rchild); } }(2) 非递归
栈：初始化栈，并且树的根结点进栈。每次循环中，首先向左走到尽头并将访问到的每个结点进栈，此时栈顶存在空指针，需要将其出栈，然后将栈顶结点出栈，并访问该结点，同时将该结点的右孩子进栈；直到栈为空。void inOrder(BiTNode tree) { if(tree==null) { return; } LinkedListstack = new LinkedList (); stack.push(tree); while(stack.size()>0) { BiTNode node = stack.peek(); while(node!=null) { stack.push(node.lchild); node = stack.peek(); } stack.pop(); if(stack.size()>0) { node = stack.pop(); visit(node); stack.push(node.rchild); } } } 栈：初始化栈。每次循环中，若当前结点不空时将该结点进栈，并遍历其左子树；否则将该结点出栈并访问该结点，同时将该结点的右孩子进栈；直到当前结点为空并且栈为空。
void inOrder(BiTNode tree) { if(tree==null) { return; } LinkedListstack = new LinkedList (); BiTNode node = tree; while(node!=null || stack.size()>0) { if(node!=null) { stack.push(node); node = node.lchild; } else { node = stack.pop(); visit(node); node = node.rchild; } } } -
后序遍历: 左-右-根
(1) 递归void postOrderRecursive(BiTNode tree) { if(tree!=null) { postOrderRecursive(tree.lchild); postOrderRecursive(tree.rchild); visit(tree); } }(2) 非递归
栈：为每个结点增加一个访问标志位 visited; 初始化栈。每次循环中，首先将根结点及其左子树进栈，并将每个结点的访问标志位置为 true，使得栈顶为最左边的左孩子，栈底为根结点；然后将栈顶结点出栈，若该结点的访问标志位为 true, 即该结点被访问了一次，要将该结点重新进栈, 并置其访问标志位为 false, 再访问该结点的右孩子；若该结点的访问标志位为 false, 即该结点被访问了两次, 要输出该结点的值，并将当前结点置为空；直到当前结点为空而且栈为空。void postOrder(BiTNode tree) { if(tree==null) { return; } Liststack = new LinkedList (); BiTNode node = tree; while(node!=null || stack.size()>0) { while(node!=null) { node.visited = true; stack.push(node); node = node.lchild; } if(stack.size()>0) { BiTNode temp = stack.pop(); if(temp.visited) { temp.visited = false; stack.push(temp); node = temp.rchild; } else { visit(temp); node = null; } } } } -
层次遍历
void levelOrder(BiTNode tree) { if(tree==null) { return; } LinkedListqueue = new LinkedList (); queue.add(tree); while(queue.size()>0) { BiTNode node = queue.remove(); visit(node); if(node.lchild!=null) { queue.add(node.lchild); } if(node.rchild!=null) { queue.add(node.rchild); } } }