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

xiaoxiao2021-02-28  32

二叉树

每个节点最多有两颗子树,即度 <= 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; } } }
转载请注明原文地址: https://www.6miu.com/read-1950399.html

最新回复(0)