C/C++程序基础 （八）数据结构

非递归先序遍历

• 　　 // 输出， 遍历左子树，遍历右子树 void firstOrder(Node* root) {stack<Node*> leftNodes;Node* curr = root;// deal each nodewhile(curr != NULL && !leftNodes.empty()){// deal with left subtreewhile(curr != NULL){cout << curr -> data << " ";// store curr node for reading right subtree leftNodes.push(curr);curr = curr -> left;}// deal with right subtreeif(!leftNodes.empty()){curr = leftNodes.top();leftNodes.pop();curr = curr -> right;}} }

   

非递归中序遍历

• // 输出， 遍历左子树，遍历右子树 void middleOrder(Node* root) {stack<Node*> leftNodes;Node* curr = root;// deal each nodewhile(curr != NULL && !leftNodes.empty()){// deal with left subtreewhile(curr != NULL){// store curr node for reading right subtree leftNodes.push(curr);curr = curr -> left;}// deal with right subtreeif(!leftNodes.empty()){curr = leftNodes.top();leftNodes.pop();// cout curr nodecout << curr -> data << " ";curr = curr -> right;}} }

   　　

非递归后序遍历

• // 输出， 遍历左子树，遍历右子树 void lastOrder(Node* root) {stack<Node*> leftNodes;stack<bool> tags;bool curr_tag = true;Node* curr = root;// deal each nodewhile(curr != NULL && !leftNodes.empty()){// deal with left subtreewhile(curr != NULL){// store curr node for reading right subtree leftNodes.push(curr);// mark have not seen right nodestags.push(false);curr = curr -> left;}// deal with right subtreeif(!leftNodes.empty()){curr = leftNodes.top();curr_tag = tags.top();tags.pop();if(curr_tag){cout << curr -> data << " ";leftNodes.pop();// have already dealt right subtreep = NULL;}else{curr = curr -> right;// mark has dealt with rightsubtreetags.push(true); }}} }

二叉排序树：左<父<右

哈弗曼树

• 哈夫曼编码：带权路径最短
• 构建方法：从最远端构建

平衡二叉（搜索）树：每个节点的左右子树深度差的绝对值小于等于1。

• 一种实现：红黑树
• 基本失衡情况：左左（右旋），右右（左旋），左右，右左。

红黑树

• 节点：红色或黑色。根节点：黑色。叶节点：黑色。红色节点的孩子为黑色。根节点到其每个叶子节点的所有路径包含相同数目的黑色节点。
• 等待补充

完全二叉树和满二叉树

• 完全二叉树，集中在左边
• 满二叉树，没有叶子节点

转载于:https://www.cnblogs.com/niuxu18/p/note_interview_8.html

总结

以上是生活随笔为你收集整理的C/C++程序基础 （八）数据结构的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。