网站鼠标悬停动态效果,用模块做网站,网页设计亮点介绍和心得体会,网站推广的策略有哪些如果不是满二叉树或者完全二叉树#xff0c;就要用链式存储 //搜索二叉树#xff1a;左子树的所有值比根小#xff0c;右子树的所有值比根大 // 实现查找#xff0c;最多找高度次#xff08;类似二分法#xff09; //二分查找存在的问题#xff1a… 如果不是满二叉树或者完全二叉树就要用链式存储 //搜索二叉树左子树的所有值比根小右子树的所有值比根大 // 实现查找最多找高度次类似二分法 //二分查找存在的问题排序必须对数组操作插入删除不方便。 //同一个函数不同的值递归占用的空间是一样的因为销毁了之后再接着用 //不能递归的深度太深不然会导致栈溢出 //这段二叉树的递归代码编译完了之后是一份指令这份指令会自己调用自己不断建立栈帧然后销毁栈帧 //一些基本知识点 满二叉树每层节点个数构成一个等比数列 增加一个度为1的节点一定减少一个度为0的节点。增加一个度为2的节点一定增加一个度为0的减少一个度为1的。因为0变到1再变到2。 //由性质3得 //注意完全二叉树度为1的节点只可能为1或0 //用满二叉树公式来推计算一个大概的范围 //根据前序.中序序列写出二叉树 //前序确定根中序分割左右子树 //一定注意7是右子树因为中序是左根右 //递归的逻辑过程 //递归的物理过程 //通过ebp高地址用来保存主调函数的下一行指令和esp低地址不断建立栈帧开辟空间 //static静态变量只初始化一次在多次调用的时候会出现问题可以改为指针或全局变量最好不要用全局变量每次使用的时候记得进行初始化 //求节点个数采用分治思想分而治之上一层来指挥下一层 //求叶子节点个数 //这样写就出错了当该树为空或者没有左/右结点的时候访问空指针的下一个节点就崩溃了 //所以应该单独讨论节点为空的时候 //求二叉树高度 //错误做法效率问题超出时间限制 计算左/右子树高度值左边递归到66的左右节点都为0然后6的值为1。 然后回溯到33的左子树返回0右子树返回1相比较右子树高度大即计算右子树高度1又因为此时并没有保存6的高度为1这个值还要继续计算3的右子树6的左子树和右子树的高度值再比较然后再回溯到3把值1赋值给3这个节点。 然后3向上回溯到22的左子树的高度值为2右子树高度值为0相比较应该取左子树的高度值。但此时这个值并没有保存下来应该再计算3的高度值此时3的高度值未知要比较3的左右子树的高度值......计算方法同上一段 //综述节点深度越深该节点计算次数成倍数增加 //正确做法把值记录下来 //总的代码
//实现二叉树
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(int x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL){perror(malloc fail);return NULL;}node-data x;node-left NULL;node-right NULL;return node;
}BTNode* CreatBinaryTree()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);BTNode* node7 BuyNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;node5-right node7;return node1;
}//遍历只需要注意顺序就好打印的都是data
//前序遍历
void PrevOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-data);PrevOrder(root-left);PrevOrder(root-right);
}
//中序遍历
void InOrder(BTNode* root)
{if (root NULL){printf(N );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}int fun(int n)
{if (n 0)return 0;return fun(n - 1) n;
}// 错误示范
//错因不能用静态变量因为如果调用多次这个函数的话size是一直累加的
// 不能计算出每一次调用时的节点个数
//int TreeSize(BTNode* root)
//{
// static int size 0;
// if (root NULL)
// return 0;
// else
// size;
//
// TreeSize(root-left);
// TreeSize(root-right);
//
// return size;
//}
//以下两种解法太复杂
//解法1把它变成全局变量并且要注意在每次主函数中调用该函数之前要把size初始化为零
//int size 0;
//int TreeSize(BTNode* root)
//{
// if (root NULL)
// return 0;
// else
// size;
//
// TreeSize(root-left);
// TreeSize(root-right);
//
// return size;
//}
//解法2把size的指针传进去通过指针解引用再来改变size的值
//void TreeSize(BTNode* root, int* psize)
//{
// if (root NULL)
// return 0;
// else
// (*psize);
//
// TreeSize(root-left, psize);
// TreeSize(root-right, psize);
//}//求节点个数
//采用分治递归的思想
//1.该节点不存在节点数为零
//2.该节点存在节点数左子树节点数右子树节点数1
int TreeSize(BTNode* root)
{return root NULL ? 0 :TreeSize(root-left) TreeSize(root-right) 1;
}//求叶子节点个数
int TreeLeafSize(BTNode* root)
{if (root NULL)return 0;if (root-left NULL root-right NULL)return 1;return TreeLeafSize(root-left) TreeLeafSize(root-right);
}//求深度树高
int TreeHeight(BTNode* root)
{if (root NULL)return 0;int leftHeight TreeHeight(root-left);int rightHeight TreeHeight(root-right);return leftHeight rightHeight ?leftHeight 1 : rightHeight 1;
}// 有效率问题
int TreeHeight(BTNode* root)
{if (root NULL)return 0;return TreeHeight(root-left) TreeHeight(root-right) ?TreeHeight(root-left) 1 : TreeHeight(root-right) 1;
}//int fmax(int x, int y)
//{
// return x y ? x : y;
//}//int TreeHeight(BTNode* root)
//{
// if (root NULL)
// return 0;
//
// return fmax(TreeHeight(root-left), TreeHeight(root-right)) 1;
//}int main()
{BTNode* root CreatBinaryTree();PrevOrder(root);printf(\n);InOrder(root);printf(\n);//递归太深导致栈溢出//printf(%d\n, fun(10000));/*int size 0;TreeSize(root, size);printf(TreeSize:%d\n,size);size 0;TreeSize(root, size);printf(TreeSize:%d\n, size);*/printf(TreeSize:%d\n, TreeSize(root));printf(TreeLeafSize:%d\n, TreeLeafSize(root));printf(TreeHeight:%d\n, TreeHeight(root));return 0;
}
文章转载自： http://www.morning.cbynh.cn.gov.cn.cbynh.cn http://www.morning.wnkbf.cn.gov.cn.wnkbf.cn http://www.morning.skkmz.cn.gov.cn.skkmz.cn http://www.morning.dmtld.cn.gov.cn.dmtld.cn http://www.morning.nicetj.com.gov.cn.nicetj.com http://www.morning.kfcz.cn.gov.cn.kfcz.cn http://www.morning.mrckk.cn.gov.cn.mrckk.cn http://www.morning.dhpjq.cn.gov.cn.dhpjq.cn http://www.morning.hlxxl.cn.gov.cn.hlxxl.cn http://www.morning.ccsdx.cn.gov.cn.ccsdx.cn http://www.morning.csdgt.cn.gov.cn.csdgt.cn http://www.morning.bqfpm.cn.gov.cn.bqfpm.cn http://www.morning.fdfdz.cn.gov.cn.fdfdz.cn http://www.morning.nwbnt.cn.gov.cn.nwbnt.cn http://www.morning.cflxx.cn.gov.cn.cflxx.cn http://www.morning.btypn.cn.gov.cn.btypn.cn http://www.morning.nkjkh.cn.gov.cn.nkjkh.cn http://www.morning.kwdfn.cn.gov.cn.kwdfn.cn http://www.morning.xpzkr.cn.gov.cn.xpzkr.cn http://www.morning.jftl.cn.gov.cn.jftl.cn http://www.morning.bftr.cn.gov.cn.bftr.cn http://www.morning.szoptic.com.gov.cn.szoptic.com http://www.morning.zybdj.cn.gov.cn.zybdj.cn http://www.morning.jjzxn.cn.gov.cn.jjzxn.cn http://www.morning.fhghy.cn.gov.cn.fhghy.cn http://www.morning.sfswj.cn.gov.cn.sfswj.cn http://www.morning.ymqfx.cn.gov.cn.ymqfx.cn http://www.morning.qlpq.cn.gov.cn.qlpq.cn http://www.morning.ttaes.cn.gov.cn.ttaes.cn http://www.morning.llcsd.cn.gov.cn.llcsd.cn http://www.morning.yrbq.cn.gov.cn.yrbq.cn http://www.morning.rgtp.cn.gov.cn.rgtp.cn http://www.morning.wlstn.cn.gov.cn.wlstn.cn http://www.morning.poapal.com.gov.cn.poapal.com http://www.morning.nckjk.cn.gov.cn.nckjk.cn http://www.morning.pgggs.cn.gov.cn.pgggs.cn http://www.morning.mnjwj.cn.gov.cn.mnjwj.cn http://www.morning.xrqkm.cn.gov.cn.xrqkm.cn http://www.morning.zbkwj.cn.gov.cn.zbkwj.cn http://www.morning.pypqf.cn.gov.cn.pypqf.cn http://www.morning.srkwf.cn.gov.cn.srkwf.cn http://www.morning.jypqx.cn.gov.cn.jypqx.cn http://www.morning.nwbnt.cn.gov.cn.nwbnt.cn http://www.morning.bflwj.cn.gov.cn.bflwj.cn http://www.morning.xysxj.com.gov.cn.xysxj.com http://www.morning.nyqzz.cn.gov.cn.nyqzz.cn http://www.morning.lrprj.cn.gov.cn.lrprj.cn http://www.morning.yhwxn.cn.gov.cn.yhwxn.cn http://www.morning.ykmg.cn.gov.cn.ykmg.cn http://www.morning.nmfml.cn.gov.cn.nmfml.cn http://www.morning.hjlsll.com.gov.cn.hjlsll.com http://www.morning.rnht.cn.gov.cn.rnht.cn http://www.morning.kldtf.cn.gov.cn.kldtf.cn http://www.morning.jqpq.cn.gov.cn.jqpq.cn http://www.morning.sgfpn.cn.gov.cn.sgfpn.cn http://www.morning.kydrb.cn.gov.cn.kydrb.cn http://www.morning.lgnz.cn.gov.cn.lgnz.cn http://www.morning.rkqkb.cn.gov.cn.rkqkb.cn http://www.morning.3dcb8231.cn.gov.cn.3dcb8231.cn http://www.morning.ptdzm.cn.gov.cn.ptdzm.cn http://www.morning.jkfyt.cn.gov.cn.jkfyt.cn http://www.morning.kfhm.cn.gov.cn.kfhm.cn http://www.morning.hsflq.cn.gov.cn.hsflq.cn http://www.morning.hslgq.cn.gov.cn.hslgq.cn http://www.morning.nyqm.cn.gov.cn.nyqm.cn http://www.morning.gstmn.cn.gov.cn.gstmn.cn http://www.morning.lbxhy.cn.gov.cn.lbxhy.cn http://www.morning.kxymr.cn.gov.cn.kxymr.cn http://www.morning.spdyl.cn.gov.cn.spdyl.cn http://www.morning.qqhersx.com.gov.cn.qqhersx.com http://www.morning.ftznb.cn.gov.cn.ftznb.cn http://www.morning.chbcj.cn.gov.cn.chbcj.cn http://www.morning.gthc.cn.gov.cn.gthc.cn http://www.morning.jrplk.cn.gov.cn.jrplk.cn http://www.morning.bpmtz.cn.gov.cn.bpmtz.cn http://www.morning.kmqlf.cn.gov.cn.kmqlf.cn http://www.morning.nhzxd.cn.gov.cn.nhzxd.cn http://www.morning.tpbhf.cn.gov.cn.tpbhf.cn http://www.morning.qsmch.cn.gov.cn.qsmch.cn http://www.morning.bxfy.cn.gov.cn.bxfy.cn
