自助建站工具,电子商务网站开发与应用,兴华建设集团有限公司网站,网络公司做什么业务一、二叉树的定义 树的每个结点至多只有二棵子树(不存在度大于2的结点)#xff0c;树的子树有左右之分#xff0c;次序不能颠倒。 二、二叉树的性质 (1) 在非空二叉树中#xff0c;第i层的结点总数不超过, i1#xff1b;(2) 深度为h的二叉树最多有个结点(h1)#…一、二叉树的定义 树的每个结点至多只有二棵子树(不存在度大于2的结点)树的子树有左右之分次序不能颠倒。 二、二叉树的性质 (1) 在非空二叉树中第i层的结点总数不超过 , i1 (2) 深度为h的二叉树最多有 个结点(h1)最少有h个结点 (3) 对于任意一棵二叉树如果其叶结点数为N0而度数为2的结点总数为N2则N0N21 (4) 具有n个结点的完全二叉树的深度为 (5)有N个结点的完全二叉树各结点如果用顺序方式存储则结点之间有如下关系 若I为结点编号则 如果I1则其父结点的编号为I/2 如果2*IN则其左儿子即左子树的根结点的编号为2*I若2*IN则无左儿子 如果2*I1N则其右儿子的结点编号为2*I1若2*I1N则无右儿子。 (6)给定N个节点能构成h(N)种不同的二叉树。 h(N)为卡特兰数的第N项。h(n)C(2*nn)/(n1)。 三、二叉树的遍历 二叉树的遍历顺序分为三种先序遍历、中序遍历和后序遍历。而遍历方式又分为递归遍历和非递归遍历。 1.先序遍历 前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。 a.递归实现: 1 void preOrder1(BinTree *root) //递归前序遍历
2 {
3 if(root!NULL)
4 {
5 coutroot-data ;
6 preOrder1(root-lchild);
7 preOrder1(root-rchild);
8 }
9 } b.非递归实现 根据前序遍历访问的顺序优先访问根结点然后再分别访问左孩子和右孩子。即对于任一结点其可看做是根结点因此可以直接访问访问完之后若其左孩子不为空按相同规则访问它的左子树当访问其左子树时再访问它的右子树。因此其处理过程如下 对于任一结点P 1)访问结点P并将结点P入栈; 2)判断结点P的左孩子是否为空若为空则取栈顶结点并进行出栈操作并将栈顶结点的右孩子置为当前的结点P循环至1);若不为空则将P的左孩子置为当前的结点P; 3)直到P为NULL并且栈为空则遍历结束。 1 void preOrder2(BinTree *root) //非递归前序遍历 2 {3 stackBinTree* s;4 BinTree *proot;5 while(p!NULL||!s.empty())6 {7 while(p!NULL)8 {9 coutp-data ;
10 s.push(p);
11 pp-lchild;
12 }
13 if(!s.empty())
14 {
15 ps.top();
16 s.pop();
17 pp-rchild;
18 }
19 }
20 } 2.中序遍历 中序遍历按照“左孩子-根结点-右孩子”的顺序进行访问。 a.递归实现 1 void inOrder1(BinTree *root) //递归中序遍历
2 {
3 if(root!NULL)
4 {
5 inOrder1(root-lchild);
6 coutroot-data ;
7 inOrder1(root-rchild);
8 }
9 } b.非递归实现 根据中序遍历的顺序对于任一结点优先访问其左孩子而左孩子结点又可以看做一根结点然后继续访问其左孩子结点直到遇到左孩子结点为空的结点才进行访问然后按相同的规则访问其右子树。因此其处理过程如下 对于任一结点P 1)若其左孩子不为空则将P入栈并将P的左孩子置为当前的P然后对当前结点P再进行相同的处理 2)若其左孩子为空则取栈顶元素并进行出栈操作访问该栈顶结点然后将当前的P置为栈顶结点的右孩子 3)直到P为NULL并且栈为空则遍历结束 1 void inOrder2(BinTree *root) //非递归中序遍历2 {3 stackBinTree* s;4 BinTree *proot;5 while(p!NULL||!s.empty())6 {7 while(p!NULL)8 {9 s.push(p);
10 pp-lchild;
11 }
12 if(!s.empty())
13 {
14 ps.top();
15 coutp-data ;
16 s.pop();
17 pp-rchild;
18 }
19 }
20 } 3.后序遍历 后序遍历按照“左孩子-右孩子-根结点”的顺序进行访问。 a.递归实现 1 void postOrder1(BinTree *root) //递归后序遍历
2 {
3 if(root!NULL)
4 {
5 postOrder1(root-lchild);
6 postOrder1(root-rchild);
7 coutroot-data ;
8 }
9 } b.非递归实现 后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点这就为流程的控制带来了难题。 要保证根结点在左孩子和右孩子访问之后才能访问因此对于任一结点P先将其入栈。如果P不存在左孩子和右孩子则可以直接访问它或者P存在左孩子或者右孩子但是其左孩子和右孩子都已被访问过了则同样可以直接访问该结点。若非上述两种情况则将P的右孩子和左孩子依次入栈这样就保证了每次取栈顶元素的时候左孩子在右孩子前面被访问左孩子和右孩子都在根结点前面被访问。 1 void postOrder3(BinTree *root) //非递归后序遍历2 {3 stackBinTree* s;4 BinTree *cur; //当前结点 5 BinTree *preNULL; //前一次访问的结点 6 s.push(root);7 while(!s.empty())8 {9 curs.top();
10 if((cur-lchildNULLcur-rchildNULL)||
11 (pre!NULL(precur-lchild||precur-rchild)))
12 {
13 coutcur-data ; //如果当前结点没有孩子结点或者孩子节点都已被访问过
14 s.pop();
15 precur;
16 }
17 else
18 {
19 if(cur-rchild!NULL)
20 s.push(cur-rchild);
21 if(cur-lchild!NULL)
22 s.push(cur-lchild);
23 }
24 }
25 } 四、参考资料 http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html 转载于:https://www.cnblogs.com/wangjzh/p/4695700.html
