二叉树总结—建树和4种遍历方式(递归&&非递归)

 二叉树最重要的就是 建立、4种遍历方式,简单应用,如何判断两颗二叉树是否相似 二叉树分为 :1、完全二叉树  2、满二叉树结构性质:1).满二叉树 高度为h ,节点数则为 2^h - 1,且叶子节点全在最下层,且叶子节点数为2^(n-1)个{n代表二叉树层数,也叫深度}2).n个节点的 完全二叉树 深度为 int(log2n)(以2为底n的对数)+ 1; 3).非空二叉树 叶子节点个数==双分支节点数+14).非空二叉树 某节点编号 n  若有

二叉树的创建和遍历

1、查找问题:分静态查找和动态查找2、同样n个元素的查找,二分查找比顺序查找快很多。判定树深度:[log2 n]+1,还可计算平均查找次数,11个节点仅为4.3、树:根与子树,要求子树是不能相交的。于是树的特点:除根节点外,每个节点只有1个父节点。n个节点,n-1条线。树是连通的,且是保证所有节点联通但同时线条树最少的状态。4、节点的度树的度 取最大的节点度5、用什么表示树?链表 (兄弟-儿子表示法):每一个元素1个数据+2个指针(firstChild+nextSibling)转化为二叉树:度为

广义表使用栈链构建二叉树

依次读取广义表中的字符,根据不同情况按照以下方式处理:(1)遇到左括号,可能接下来读取的元素是左孩子,需要将双亲结点入栈,同时将标志k置为1;(2)遇到逗号,下一个读取的元素一定是右孩子,将标志置为2;(3)遇到右括号,表明当前层读取结束,需要回退到上一层,上一层的栈元素将成为新的双亲结点;(4)遇到字符,创建一个新结点,将当前字符ch存入数据域,然后将该结点插入对应的子树中。根据k的值进行以下处理:①k为1,则使该结点成为栈顶元素结点的左孩子结点;②k为2,则使该结点成为栈顶元素结点的右孩子结