新建 文本文档 (6).txt

该软件会在用户的使用过程中自动进行调整达到最佳状态

                        NodeStack.push(pNode->pRight);                                // 当前结点的右子树根结点入栈
                }
        }
}

// 中序遍历树
// 中序遍历输出的结果应该和用来初始化树的数组的排列顺序一致
void BinaryTree::InTraverseImpl(PTreeNode pTreenode)
{
        if (NULL == pTreenode)
                return;

        if (NULL != pTreenode->pLeft)
        {
                InTraverseImpl(pTreenode->pLeft);
        }

        std::cout << "Item = " << pTreenode->Node << std::endl;

        if (NULL != pTreenode->pRight)
        {
                InTraverseImpl(pTreenode->pRight);
        }
}

// 非递归中序遍历树
void BinaryTree::NoRecInTraverseImpl(PTreeNode pTreenode)
{
        if (NULL == pTreenode)
                return;

        TreeNodeStack NodeStack;
        PTreeNode pNode;
        NodeStack.push(pTreenode);

        while (!NodeStack.empty())
        {
                while (NULL != (pNode = NodeStack.top()))        // 向左走到尽头
                {
                        NodeStack.push(pNode->pLeft);
                }

                NodeStack.pop();

                if (!NodeStack.empty() && NULL != (pNode = NodeStack.top()))
                {
                        std::cout << "Item = " << pNode->Node << std::endl;
                        NodeStack.pop();
                        NodeStack.push(pNode->pRight);
                }
        }
}

// 后序遍历树
void BinaryTree::PostTraverseImpl(PTreeNode pTreenode)
{
        if (NULL == pTreenode)
                return;

        if (NULL != pTreenode->pLeft)
        {
                PostTraverseImpl(pTreenode->pLeft);
        }

        if (NULL != pTreenode->pRight)
        {
                PostTraverseImpl(pTreenode->pRight);
        }

        std::cout << "Item = " << pTreenode->Node << std::endl;
}

// 非递归后序遍历树
void BinaryTree::NoRecPostTraverseImpl(PTreeNode pTreenode)
{
        if (NULL == pTreenode)
                return;

        TreeNodeStack NodeStack;
        PTreeNode pNode1, pNode2;
        NodeStack.push(pTreenode);
        pNode1 = pTreenode->pLeft;
        
        bool bVisitRoot = false;                        // 标志位,是否访问过根结点
        while (!NodeStack.empty())
        {
                while (NULL != pNode1)                        // 向左走到尽头
                {
                        NodeStack.push(pNode1);
                        pNode1 = pNode1->pLeft;
                }

                pNode1 = NodeStack.top();
                NodeStack.pop();

                if (NULL == pNode1->pRight)                        // 如果没有右子树就是叶子结点
                {
                        std::cout << "Item = " << pNode1->Node << std::endl;
                        pNode2 = pNode1;
                        pNode1 = NodeStack.top();

                        if (pNode2 == pNode1->pRight)        // 如果这个叶子结点是右子树
                        {
                                std::cout << "Item = " << pNode1->Node << std::endl;
                                NodeStack.pop();
                                pNode1 = NULL;
                        }
                        else                                                        // 否则访问右子树
                        {
                                pNode1 = pNode1->pRight;
                        }
                }
                else                                                                // 访问右子树
                {
                        if (pNode1 == pTreenode && true == bVisitRoot)        // 如果已经访问过右子树那么就退出
                        {
                                std::cout << "Item = " << pNode1->Node << std::endl;
                                return;
                        }
                        else
                        {
                                if (pNode1 == pTreenode)
                                {
                                        bVisitRoot = true;
                                }

                                NodeStack.push(pNode1);
                                pNode1 = pNode1->pRight;
                        }
                }
        }
}

// 按照树的层次从左到右访问树的结点
void BinaryTree::LevelTraverseImpl(PTreeNode pTreenode)
{
        if (NULL == pTreenode)
                return;

        // 层序遍历用于保存结点的容器是队列
        std::queue<PTreeNode> NodeQueue;
        PTreeNode pNode;
        NodeQueue.push(pTreenode);

        while (!NodeQueue.empty())
        {
                pNode = NodeQueue.front();
                NodeQueue.pop();
                std::cout << "Item = " << pNode->Node << std::endl;

                if (NULL != pNode->pLeft)
                {
                        NodeQueue.push(pNode->pLeft);    
                }
                if (NULL != pNode->pRight)
                {
                        NodeQueue.push(pNode->pRight);
                }    
        }
}
[/code] 

converse 2006-7-8 06:51 
 
main.cpp
[code]
/********************************************************************
        created:        2006/07/04
        filename:         main.cpp
        author:                李创
                http://www.cppblog.com/converse/

        purpose:        测试二叉树的算法
*********************************************************************/

#include "BinaryTree.h"

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>

void DisplayArray(int array[], int length)
{
        int i;

        for (i = 0; i < length; i++)
        {
                printf("array[%d] = %d\n", i, array[i]);
        }
}

void CreateNewArray(int array[], int length)
{
        for (int i = 0; i < length; i++)
        {
                array[i] = rand() % 256 + i;
        }
}

int main()
{
        int array[10];
        srand(time(NULL));

        // 创建数组
        CreateNewArray(array, 10);
        DisplayArray(array, 10);

        BinaryTree *pTree = new BinaryTree(array, 10);

        // 测试前序遍历
        pTree->Traverse(BinaryTree::PREORDER);
        std::cout << "root = " << pTree->GetRoot()->Node << std::endl;
        std::cout << "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl;
        std::cout << "root->right = " << pTree->GetRoot()->pRight->Node << std::endl;
        pTree->Traverse(BinaryTree::PREORDER, false);
        
        // 测试中序遍历
        pTree->Traverse(BinaryTree::INORDER);
        std::cout << "root = " << pTree->GetRoot()->Node << std::endl;
        std::cout << "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl;
        std::cout << "root->right = " << pTree->GetRoot()->pRight->Node << std::endl;
        pTree->Traverse(BinaryTree::INORDER, false);
        // 测试后序遍历
        pTree->Traverse(BinaryTree::POSTORDER);
        std::cout << "root = " << pTree->GetRoot()->Node << std::endl;
        std::cout << "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl;
        std::cout << "root->right = " << pTree->GetRoot()->pRight->Node << std::endl;
        pTree->Traverse(BinaryTree::POSTORDER, false);
        // 测试层序遍历
        pTree->Traverse(BinaryTree::LEVELORDER);

        system("pause");
        
        delete pTree;

    return 0;
}

[/code]

[[i] 本帖最后由 converse 于 2006-7-8 14:54 编辑 [/i]]