二叉树的原理和3种遍历方式（C++实现）

二叉树

每个节点最多有两颗子树，即度 <= 2， 有序树

性质

二叉树的第i层上最多有2^i个节点，i从0开始；深度为k的二叉树上至多有2^(k+1) - 1个节点，k从0开始；当前节点编号为i，则其子节点（如果有）为2i+1和2i+2；

完全二叉树

叶子节点只在最大两层出现； 对于任一节点，其右侧分支最大层次为l，则左分支为l或者l+1

满二叉树

深度为k且有2^(k+1) - 1个节点的二叉树

树的节点

struct BiTreeNode { char data; BiTreeNode *lChild; BiTreeNode *rChild; BiTreeNode *Parent; };

前序遍历

递归解决

void BiTree::PreTraverse(BiTreeNode *root) const { if (root != NULL) { cout << root->data; PreTraverse(root->lChild); PreTraverse(root->rChild); } }

栈解决

//先输出当前节点的值，并将该节点放入栈中，继续访问左节点直到终端， //输出节点值，退栈,访问右节点 void BiTree::PreOrderTraverse(BiTreeNode *root) const { stack<BiTreeNode *> Tree; while (!Tree.empty() || root != NULL) { while (root != NULL) { cout << root->data; Tree.push(root); root = root->lChild; } root = Tree.top(); Tree.pop(); root = root->rChild; } }

中序遍历

递归解决

void BiTree::InTraverse(BiTreeNode *root) const { if (root != NULL) { InTraverse(root->lChild); cout << root->data; InTraverse(root->rChild); } }

栈解决

//访问左节点直到NULL输出栈顶节点值，退栈访问右节点 void BiTree::InOrderTraverse(BiTreeNode *root) const { stack<BiTreeNode *> Tree; while (!Tree.empty() || root != NULL) { while (root != NULL) { Tree.push(root); root = root->lChild; } root = Tree.top(); cout << root->data; Tree.pop(); root = root->rChild; } }

后序遍历

递归解决

void BiTree::PostTraverse(BiTreeNode *root) const { if (root != NULL) { PostTraverse(root->lChild); PostTraverse(root->rChild); cout << root->data; } }

栈解决

//对父节点出现在栈顶的次数进行计数：第一次出现的时候不出栈， //第二次再出现，表明右孩子子树已经遍历完毕，这个时候再出栈并完成遍历。 void BiTree::PostOrderTraverse(BiTreeNode *root) const { stack<BiTreeNode *> Tree; stack<int> Times; //计数 while (!Tree.empty() || root != NULL) { while (root != NULL) { Tree.push(root); Times.push(0); //首次访问该节点 root = root->lChild; } if (Times.top() == 1) //已经访问了2次 { cout << Tree.top()->data; Times.pop(); //删除栈顶元素 Tree.pop(); } else { root = Tree.top(); Times.top() = 1; //第二次访问该节点 root = root->rChild; } } }