1.二叉树的结点计算
1）在二叉树的第i层上至多有2i-1个结点
提示：可以用归纳法，假若第i层有至多2i-1个结点，那么第i+1层至多就有2*2i-1个结点。
2）深度为k的二叉树至多有2^k -1个结点。
提示：考虑满二叉树的情况，所有结点求和。
3）有n个结点的完全二叉树的高度为
提示：结合2），n<=2^h-1
4）结点编号
对于满二叉树或者完全二叉树，根节点编号为i，那么两个孩子结点的编号分别为2i,2i+1
2.二叉树的建立和遍历（递归方式）
// 二叉树.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> using namespace std; typedef struct BiTreeNode { char data; BiTreeNode * leftTree; BiTreeNode * rightTree; }bitTree,*BitTree; void createTree(BitTree &Node) { char ch; cin>>ch; if(ch==‘#‘) Node=NULL ; //注意，当输入为‘#‘时候 结点为NULL，刚开始一直坚持不出错误。 else { Node=new bitTree; if (!Node) return; Node->data = ch; createTree(Node->leftTree); createTree(Node->rightTree); } } //线序遍历 void Pre_visit(bitTree *t,int level) { if(t) //注意是if { cout<<t->data<<" "<<level<<endl; Pre_visit(t->leftTree,level+1); Pre_visit(t->rightTree,level+1); } } //中序遍历 void Mid_visit(bitTree *t,int level) { if(t) { Mid_visit(t->leftTree,level+1); cout<<t->data<<" "<<level<<endl; Mid_visit(t->rightTree,level+1); } } int main(int argc, char* argv[]) { //使用递归创建二叉树**************// cout<<"请输入数据："<<endl; bitTree * newTree=NULL; createTree(newTree); int level=1; // Pre_visit(newTree,level); Mid_visit(newTree,level); return 0; }
试验中，特别要注意输入的方法：
结果如下：
3.二叉树的非递归遍历
先序遍历:
我们来通过代码和图进行
void pre_visit(bitTree *t) { bitTree *p=t; initStack(S); while(p!=NULL||Empty(S)) { if (p!=NULL) { visit(p->data); //visit可以将元素打印出来 Push(S,p); //保存访问的结点用来访问右结点，不然我们无法退回去访问右结点 visit(p->leftTree) } else { p=Pop(S); //弹出栈顶元素，并接下来访问弹出元素的右结点。 p=p->rightTree; } } }
PS
:
1)每次弹出一个元素就会访问改元素的右结点.
2)visit是起着输出的作用。栈只是用来保存访问过的结点。
中序遍历:
void pre_visit(bitTree *t) { bitTree *p=t; initStack(S); while(p!=NULL||Empty(S)) { if (p!=NULL) { Push(S,p); p=p->leftTree; } else { p=Pop(S); visit(p->data); p=p->rightTree; } } }
步骤:
(1) 首先将二叉树的根T压入栈.
(2) 若T有左子树,则一直将其压入栈中,直到结点左子树为空.
(3) 当其左子树为空,那么就弹出改结点,并visit 该结点data，然后再访问其右子树。
原文：http://www.cnblogs.com/menghuizuotian/p/3768941.html